Introducing Commutative and Associative Operators in Cryptographic Protocol Analysis

Many formal techniques for the verification of cryptographic protocols rely on the abstract definition of cryptographic primitives, such as shared, private and public key encryption. This approach prevents the analysis of those protocols that explicitly use commutative and associative algebraic operators to build their messages such as, for example, the Diffie-Hellman key-exchange protocol. This paper investigates the possibility of handling operators which exhibit special properties by considering a stand-alone extension to the way most known popular techniques handle messages exchanged during the protocol sessions. Such an extension makes the new operators tractable by automatic model checking techniques. The properties examined in this paper are commutativity and associativity.