Complexity Results for Security Protocols with Diffie-Hellman Exponentiation and Commuting Public Key Encryption
Y. Chevalier, R. Küsters, M. Rusinowitch, and M. Turuani
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.