On The Security of Multi-Party Ping-Pong Protocols

by Shimon Even and Oded Goldreich (1983)

A full version of this work has appeared as Technical Report No. 285, Computer Science Dept., Technion, Haifa, Israel, June 1983, 61 pages. An extended abstract has appeared in the Proc. of the 24th FOCS, pages 34-39, 1983. This work was the center-piece of Oded Goldreich's D.Sc. Thesis, supervised by Shimon Even, and submitted to the Senate of the Technion in June 1983.

The work refers to a restricted notion of insecurity (i.e., breakability under a syntactically restricted type of attacks) and to restricted classes of protocols. These classes extend the model of Dolev and Yao in two ways. First, the work considers multi-party protocols rather than two-party ones. Next, the work considers protocols in which each message consists of a pair of strings and possibly different operations are applied to each element in the pair (rather than allowing only operations that are applied to the message as a whole). The focus of the work is on the complexity (or even decidability) of the computational task of testing whether or not such protocols are insecurity (under the aforementioned type of attacks). The results include:

Following is the abstract (as revised in 1985).

Abstract: This paper is concerned with the model for security of cryptographic protocols suggested by Dolev and Yao. The Dolev and Yao model deals with a restricted class of protocols, known as Two-Party Ping-Pong Protocols. In such a protocol, messages are exchanged in a memoryless manner. That is, the message sent by each party results from applying a predetermined operator to the message he has received.
The Dolev and Yao model is presented, generalized in various directions and the affect of these generalizations is extensively studied. First, the model is trivially generalized to deal with multi-party ping-pong protocols. However, the problems which arise from this generalization are very far from being trivial. In particular, it is no longer clear how many saboteurs (adversaries) should be considered when testing the security of p-party ping-pong protocols. We demonstrate an upper bound of 3(p-2)+2 and a lower bound of 3(p-2)+1 on this number. Thus, for every fixed p, the security of p-party ping-pong protocols can be tested in polynomial time. In contrast, we show that testing the security of multi-party protocols (i.e. the number of participants is part of the input) is NP-Hard. A different extension of the Dolev and Yao model, obtained by allowing operators to operate on ``half words'', is shown to have an undecidable security problem.

Material available on-line

Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers