{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T09:36:36Z","timestamp":1773653796110,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1380572.1380573","type":"journal-article","created":{"date-parts":[[2008,9,4]],"date-time":"2008-09-04T12:51:35Z","timestamp":1220532695000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Complexity results for security protocols with Diffie-Hellman exponentiation and commuting public key encryption"],"prefix":"10.1145","volume":"9","author":[{"given":"Yannick","family":"Chevalier","sequence":"first","affiliation":[{"name":"IRIT-Universit\u00e9 Paul Sabatier, Toulouse Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"K\u00fcsters","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Trier, Trier, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u00ebl","family":"Rusinowitch","sequence":"additional","affiliation":[{"name":"LORIA-INRIA-Universit\u00e9 Henri Poincar\u00e9, Villers les Nancy Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Turuani","sequence":"additional","affiliation":[{"name":"LORIA-INRIA-Universit\u00e9 Henri Poincar\u00e9, Vandoeuvre-l\u00e8s-Nancy Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00090-7"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 8th European Symposium on Research in Computer Security (ESORICS","volume":"2808","author":"Basin D.","year":"2003","unstructured":"Basin , D. , M\u00f6dersheim , S. , and Vigan\u00f2 , L . 2003. An on-the-fly model-checker for security protocol analysis . In Proceedings of the 8th European Symposium on Research in Computer Security (ESORICS 2003 ), E. Snekkenes and D. Gollmann, Eds. Lecture Notes in Computer Science , vol. 2808 . Springer, Berlin, Germany, 253--270. Basin, D., M\u00f6dersheim, S., and Vigan\u00f2, L. 2003. An on-the-fly model-checker for security protocol analysis. In Proceedings of the 8th European Symposium on Research in Computer Security (ESORICS 2003), E. Snekkenes and D. Gollmann, Eds. Lecture Notes in Computer Science, vol. 2808. Springer, Berlin, Germany, 253--270."},{"key":"e_1_2_1_3_1","first-page":"751","article-title":"Solving numerical constraints. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, Eds. Vol. I. Elsevier Science, Amsterdam, The Netherlands","volume":"12","author":"Bockmayr A.","year":"2001","unstructured":"Bockmayr , A. and Weispfenning , V. 2001 . Solving numerical constraints. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, Eds. Vol. I. Elsevier Science, Amsterdam, The Netherlands , Chapter 12 , 751 -- 842 . Bockmayr, A. and Weispfenning, V. 2001. Solving numerical constraints. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, Eds. Vol. I. Elsevier Science, Amsterdam, The Netherlands, Chapter 12, 751--842.","journal-title":"Chapter"},{"key":"e_1_2_1_4_1","volume-title":"28th International Colloquium (ICALP","volume":"2076","author":"Boreale M.","year":"2001","unstructured":"Boreale , M. 2001 . Symbolic trace analysis of cryptographic protocols. In Automata, Languages and Programming , 28th International Colloquium (ICALP 2001). Lecture Notes in Computer Science , vol. 2076 . Springer-Verlag, Berlin, Germany, 667--681. Boreale, M. 2001. Symbolic trace analysis of cryptographic protocols. In Automata, Languages and Programming, 28th International Colloquium (ICALP 2001). Lecture Notes in Computer Science, vol. 2076. Springer-Verlag, Berlin, Germany, 667--681."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Workshop on Foundations of Computer Security (FCS","author":"Boreale M.","year":"2003","unstructured":"Boreale , M. and Buscemi , M . 2003. On the symbolic analysis of low-level cryptographic primitives: modular exponentiation and the Diffie-Hellman Protocol . In Proceedings of the Workshop on Foundations of Computer Security (FCS 2003 ). Boreale, M. and Buscemi, M. 2003. On the symbolic analysis of low-level cryptographic primitives: modular exponentiation and the Diffie-Hellman Protocol. In Proceedings of the Workshop on Foundations of Computer Security (FCS 2003)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1976-0396605-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Boyd C. and Mathuria A. 2003. Protocols for Authentication and Key Establishment. Springer Berlin Germany.   Boyd C. and Mathuria A. 2003. Protocols for Authentication and Key Establishment. Springer Berlin Germany.","DOI":"10.1007\/978-3-662-09527-0"},{"key":"e_1_2_1_8_1","unstructured":"Bull J. and Otway D. 1997. The authentication protocol. Tech. rep. DRA\/CIS3\/PROJ\/CORBA\/SC\/1\/CSM\/436-04\/03. Defence Research Agency Malvern U.K.  Bull J. and Otway D. 1997. The authentication protocol. Tech. rep. DRA\/CIS3\/PROJ\/CORBA\/SC\/1\/CSM\/436-04\/03. Defence Research Agency Malvern U.K."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789058"},{"key":"e_1_2_1_10_1","volume-title":"FSTTCS 2003: Foundations of Software Technology and Theoretical Computer Science, P. Pandya and J. Radhakrishnan, Eds. Lecture Notes in Computer Science","volume":"2914","author":"Chevalier Y.","unstructured":"Chevalier , Y. , K\u00fcsters , R. , Rusinowitch , M. , and Turuani , M . 2003b. Deciding the security of protocols with Diffie-Hellman exponentiation and products in exponents . In FSTTCS 2003: Foundations of Software Technology and Theoretical Computer Science, P. Pandya and J. Radhakrishnan, Eds. Lecture Notes in Computer Science , vol. 2914 . Springer, Berlin, Germany, 124--135. Chevalier, Y., K\u00fcsters, R., Rusinowitch, M., and Turuani, M. 2003b. Deciding the security of protocols with Diffie-Hellman exponentiation and products in exponents. In FSTTCS 2003: Foundations of Software Technology and Theoretical Computer Science, P. Pandya and J. Radhakrishnan, Eds. Lecture Notes in Computer Science, vol. 2914. Springer, Berlin, Germany, 124--135."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IJCAR 2004 Workshop W6 ARSPA Automated Reasoning for Security Protocol Analysis.","author":"Chevalier Y.","unstructured":"Chevalier , Y. , K\u00fcsters , R. , Rusinowitch , M. , and Turuani , M . 2004. Deciding the security of protocols with commuting public key encryption . In Proceedings of the IJCAR 2004 Workshop W6 ARSPA Automated Reasoning for Security Protocol Analysis. Chevalier, Y., K\u00fcsters, R., Rusinowitch, M., and Turuani, M. 2004. Deciding the security of protocols with commuting public key encryption. In Proceedings of the IJCAR 2004 Workshop W6 ARSPA Automated Reasoning for Security Protocol Analysis."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 16th IEEE Conference on Automated Software Engineering (ASE","author":"Chevalier Y.","year":"2001","unstructured":"Chevalier , Y. and Vigneron , L . 2001. A tool for lazy verification of security protocols . In Proceedings of the 16th IEEE Conference on Automated Software Engineering (ASE 2001 ). IEEE Computer Society Press, Los alamitos, CA, 373--376. Chevalier, Y. and Vigneron, L. 2001. A tool for lazy verification of security protocols. In Proceedings of the 16th IEEE Conference on Automated Software Engineering (ASE 2001). IEEE Computer Society Press, Los alamitos, CA, 373--376."},{"key":"e_1_2_1_13_1","unstructured":"Clark J. and Jacob J. 1997. A Survey of Authentication Protocol Literature. Web Draft Version 1.0. Available online at http:\/\/citeseer.nj.nec.com\/.  Clark J. and Jacob J. 1997. A Survey of Authentication Protocol Literature. Web Draft Version 1.0. Available online at http:\/\/citeseer.nj.nec.com\/."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS","author":"Comon-Lundh H.","year":"2003","unstructured":"Comon-Lundh , H. and Shmatikov , V . 2003. Intruder deductions, constraint solving and insecurity decision in presence of exclusive or . In Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003 ). IEEE, Computer Society Press, Los Alamitos, CA, 271--280. Comon-Lundh, H. and Shmatikov, V. 2003. Intruder deductions, constraint solving and insecurity decision in presence of exclusive or. In Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003). IEEE, Computer Society Press, Los Alamitos, CA, 271--280."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th International Symposium on Static Analysis (SAS","volume":"2477","author":"Corin R.","year":"2002","unstructured":"Corin , R. and Etalle , S . 2002. An improved constraint-based system for the verification of security protocols . In Proceedings of the 9th International Symposium on Static Analysis (SAS 2002 ), M. Hermenegildo and G. Puebla, Eds. Lecture Notes in Computer Science , vol. 2477 . Springer, Berlin, Germany, 326--341. Corin, R. and Etalle, S. 2002. An improved constraint-based system for the verification of security protocols. In Proceedings of the 9th International Symposium on Static Analysis (SAS 2002), M. Hermenegildo and G. Puebla, Eds. Lecture Notes in Computer Science, vol. 2477. Springer, Berlin, Germany, 326--341."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056650"},{"key":"e_1_2_1_17_1","volume-title":"AC: How to verify Diffie-Hellman-like protocols automatically. J. Log. Alg. Program. To appear.","author":"Goubault-Larrecq J.","year":"2005","unstructured":"Goubault-Larrecq , J. , Roger , M. , and Verma , K . 2005 . Abstraction and resolution modulo AC: How to verify Diffie-Hellman-like protocols automatically. J. Log. Alg. Program. To appear. Goubault-Larrecq, J., Roger, M., and Verma, K. 2005. Abstraction and resolution modulo AC: How to verify Diffie-Hellman-like protocols automatically. J. Log. Alg. Program. To appear."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 14th International Conference on Rewriting Techniques and Applications (RTA","volume":"2706","author":"Kapur D.","year":"2003","unstructured":"Kapur , D. , Narendran , P. , and Wang , L . 2003. Analyzing protocols that use modular exponentiation: Semantic unification techniques . In Proceedings of the 14th International Conference on Rewriting Techniques and Applications (RTA 2003 ), R. Nieuwenhuis, Ed. Lecture Notes in Computer Science , vol. 2706 . Springer, Berlin, Germany, 165--179. Kapur, D., Narendran, P., and Wang, L. 2003. Analyzing protocols that use modular exponentiation: Semantic unification techniques. In Proceedings of the 14th International Conference on Rewriting Techniques and Applications (RTA 2003), R. Nieuwenhuis, Ed. Lecture Notes in Computer Science, vol. 2706. Springer, Berlin, Germany, 165--179."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of DISCEX","author":"Meadows C.","year":"2000","unstructured":"Meadows , C. 2000 . Open issues in formal methods for cryptographic protocol analysis . In Proceedings of DISCEX 2000. IEEE Computer Society Press, Los Alamitos, CA, 237--250. Meadows, C. 2000. Open issues in formal methods for cryptographic protocol analysis. In Proceedings of DISCEX 2000. IEEE Computer Society Press, Los Alamitos, CA, 237--250."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Workshop on Issues in the Theory of Security (WITS","author":"Meadows C.","year":"2002","unstructured":"Meadows , C. and Narendran , P . 2002. A unification algorithm for the group Diffie-Hellman protocol . In Proceedings of the Workshop on Issues in the Theory of Security (WITS 2002 ). Meadows, C. and Narendran, P. 2002. A unification algorithm for the group Diffie-Hellman protocol. In Proceedings of the Workshop on Issues in the Theory of Security (WITS 2002)."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW 16)","author":"Millen J.","unstructured":"Millen , J. and Shmatikov , V . 2003. Symbolic protocol analysis with products and Diffie-Hellman exponentiation . In Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW 16) . IEEE Computer Society, Los Alamitos, CA, 47--61. Millen, J. and Shmatikov, V. 2003. Symbolic protocol analysis with products and Diffie-Hellman exponentiation. In Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW 16). IEEE Computer Society, Los Alamitos, CA, 47--61."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/501983.502007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/794197.795078"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14)","author":"Pereira O.","unstructured":"Pereira , O. and Quisquater , J . -J. 2001. A security analysis of the Cliques Protocols Suites . In Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14) . 73--81. Pereira, O. and Quisquater, J.-J. 2001. A security analysis of the Cliques Protocols Suites. In Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14). 73--81."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009380.1009688"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14)","author":"Rusinowitch M.","unstructured":"Rusinowitch , M. and Turuani , M . 2001. Protocol insecurity with finite number of sessions is NP-complete . In Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14) . IEEE Computer Society, Los Alamitos, CA, 174--190. Rusinowitch, M. and Turuani, M. 2001. Protocol insecurity with finite number of sessions is NP-complete. In Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW-14). IEEE Computer Society, Los Alamitos, CA, 174--190."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00180-4"},{"key":"e_1_2_1_28_1","volume-title":"Applied Cryptography","author":"Schneier B.","unstructured":"Schneier , B. 1996. Applied Cryptography . John Wiley & Sons , New York, NY . Schneier, B. 1996. Applied Cryptography. John Wiley & Sons, New York, NY."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24725-8_25"},{"key":"e_1_2_1_30_1","volume-title":"CLIQUES: A new approach to key agreement. In Proceedings of the IEEE International Conference on Distributed Computing Systems","author":"Steiner M.","year":"1998","unstructured":"Steiner , M. , Tsudik , G. , and Waidner , M . 1998 . CLIQUES: A new approach to key agreement. In Proceedings of the IEEE International Conference on Distributed Computing Systems . IEEE Computer Society Press , Los Alamitos, CA , 380--387. Steiner, M., Tsudik, G., and Waidner, M. 1998. CLIQUES: A new approach to key agreement. In Proceedings of the IEEE International Conference on Distributed Computing Systems. IEEE Computer Society Press, Los Alamitos, CA, 380--387."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1380572.1380573","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1380572.1380573","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:45Z","timestamp":1750255065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1380572.1380573"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1380572.1380573"],"URL":"https:\/\/doi.org\/10.1145\/1380572.1380573","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2005-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}