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.
Type de document :
Article dans une revue
ACM Transactions on Computational Logic, Association for Computing Machinery, 2008, 9 (4), pp.Article 24. 〈10.1145/1380572.1380573〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00329740
Contributeur : Michaël Rusinowitch <>
Soumis le : lundi 13 octobre 2008 - 12:19:11
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09

Identifiants

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〉

Partager

Métriques

Consultations de la notice

230