Skip to Main content Skip to Navigation
Journal articles

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

Michaël Rusinowitch 1 Mathieu Turuani 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We investigate the complexity of the protocol insecurity problem for a finite number of sessions (fixed 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 fixed number of sessions the intruder needs only to forge messages of linear size, provided that they are represented as dags.
Document type :
Journal articles
Complete list of metadatas
Contributor : Mathieu Turuani <>
Submitted on : Thursday, October 5, 2006 - 3:49:25 PM
Last modification on : Thursday, November 12, 2020 - 9:42:03 AM



Michaël Rusinowitch, Mathieu Turuani. Protocol insecurity with a finite number of sessions, composed keys is NP-complete.. Theoretical Computer Science, Elsevier, 2003, Theoretical Computer Science, 1-3 (299), pp.451-475. ⟨10.1016/S0304-3975(02)00490-5⟩. ⟨inria-00103985⟩



Record views