Complexity results for security protocols with Diffie-Hellman exponentiation and commuting public key encryption

Yannick Chevalier 1, 2 Ralf Kuesters Michael Rusinowitch 2 Mathieu Turuani 2
2 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 show that the insecurity problem for protocols with modular exponentiation and arbitrary products allowed in exponents is NP-complete. This result is based on a protocol and intruder model which is powerful enough to uncover known attacks on the Authenticated Group Diffie-Hellman (A-GDH.2) protocol suite. To prove our results, we develop a general framework in which the Dolev-Yao intruder is extended by generic intruder rules. This framework is also applied to obtain complexity results for protocols with commuting public key encryption.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00329740
Contributor : Michaël Rusinowitch <>
Submitted on : Monday, October 13, 2008 - 12:19:11 PM
Last modification on : Thursday, June 27, 2019 - 4:27:42 PM

Identifiers

Citation

Yannick Chevalier, Ralf Kuesters, Michael Rusinowitch, Mathieu Turuani. Complexity results for security protocols with Diffie-Hellman exponentiation and commuting public key encryption. ACM Transactions on Computational Logic, Association for Computing Machinery, 2008, 9 (4), pp.Article 24. ⟨10.1145/1380572.1380573⟩. ⟨inria-00329740⟩

Share

Metrics

Record views

322