Symbolic protocol analysis with an Abelian group operator or Diffie–Hellman exponentiation

Abstract

We demonstrate that for any well-defined cryptographic protocol, the symbolic trace reachability problem in the presence of an Abelian group operator (e.g., multiplication) can be reduced to solvability of a decidable system of quadratic Diophantine equations. This result enables complete, fully automated formal analysis of protocols that employ primitives such as Diffie–Hellman exponentiation, multiplication, and xor, with a bounded number of role instances, but without imposing any bounds on the size of terms created by the attacker.