Protocol Insecurity with Finite Number of Sessions is NP-complete Michaël Rusinowitch and Mathieu Turuani

We investigate the complexity of the protocol insecurity problem for a finite number of sessions (fixed number of in-terleaved runs). We show that this problem is NP-complete in a Dolev-Yao model of intruders. The result does not assume a limit on the size of messages and supports non-atomic symmetric encryption keys. We also prove that in order to build an attack with a fixed number of sessions the intruder needs only to forge messages of polynomial size, provided that they are represented as dags