On the Security of Ping-Pong Protocols

Consider the class of protocols, for two participants, in which the initiator applies a sequence of operators to a message M and sends it to the other participant; in each step, one of the participants applies a sequence of operators to the message received last, and sends it back. This “ping-pong” action continues several times, using sequences of operators as specified by the protocol. The set of operators may include public-key encryptions and decryptions.We present an O(n3) algorithm which determines the security of a given protocol (of length n). This is an improvement of the algorithm of Dolev and Yao [DY].