✦ LIBER ✦

Protocol insecurity with a finite number of sessions and composed keys is NP-complete

✍ Scribed by Michaël Rusinowitch; Mathieu Turuani

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 341 KB
Volume: 299
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00490-5

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate the complexity of the protocol insecurity problem for a ÿnite number of sessions (ÿxed number of interleaved runs). We show that this problem is NP-complete with respect to 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 ÿxed number of sessions the intruder needs only to forge messages of linear size, provided that they are represented as dags.