CS Faculty Talks
Date: Wednesday, 9 October 2024
Time: 11:00 - 11:50 AM
Insecurity for protocols with assertions
S. P. Suresh
Chennai Mathematical Institute.
09-10-24

---

Abstract

Security protocols are short programs which prescribe patterns of mes- sage exchange (with messages typically constructed using cryptographic operations). They are used for a range of applications from e-commerce to electronic voting, and also form the backbone of the Internet. The formal (logical) modelling and analysis of such protocols has a long history. The basic problems are undecidable, but a seminal result by Rusinowitch & Turuani (2001) shows that a bounded version of the basic insecurity problem is NP-complete. When we consider protocols where the messages exchanged include some simple assertions, then this analysis becomes much more complicated. We show that the above version of the insecurity problem remains NP even with communicated assertions.