Complexity results for security protocols with Diffie-Hellman exponentiation and commuting public key encryption
Yannick Chevalier, Ralf Küsters, Michaël Rusinowitch, Mathieu Turuani · ACM Transactions on Computational Logic · 2008
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.