Oded Goldreich

Abstract of D.Sc Thesis (Technion, 1983)

Title: On the Security of Cryptographic Protocols and Cryptosystems


This thesis deals with various aspects of the security of cryptographic protocols and cryptosystems.

A p-party ping-pong protocol and its security problem are defined along the lines of Dolev and Yao's definitions for two-party ping-pong protocols. In the case of two parties it was assumed, with no loss of generality, that there exists a single saboteur in the net and the protocol was defined to be secure if it was secure against the active interventions of one saboteur. It is shown that for more than 2 parties this assumption can no longer be made, and that for p parties, 3(p-2)+1 is a lower bound on the number of saboteurs which should be considered for the security problem. On the other hand a 3(p-2)+2 upper bound on the number of saboteurs which should be considered is established. It is concluded that for a fixed p, p-party ping-pong protocols can be tested for security in cubic time and quadratic space. It is shown that if p, the number of participants in the protocol, is part of the input then the security problem becomes NP-Hard. Relaxing the definition of a ping-pong protocol so that operators can operate on half words (thus introducing commutativity of the operators) causes the security problem to become undecidable.

Another group of results presented in this thesis deals with the power of cascade ciphers. A cascade cipher is defined as a concatenation of block- cipher systems, called its stages. An algorithm, with time-space trade-off, for finding the key of a cascade cipher given plaintext-ciphertext pairs is presented. We conjecture that the strength of a cascade cipher is exponential in its length (i.e. in the number of its stages) and explain why we despair of proving this conjecture. We prove that a cascade cipher is not weaker than its stages. We conclude with some enumeration results which deal with cascade ciphers the stages of which are random ciphers. One of the results is that if one picks enough plaintext-ciphertext pairs then there is at most one key by which each of the plaintexts is transferred to its corresponding cipehrtext.

In another chapter of this thesis we develop protocols for various distributed problems and especially for signing a contract. A randomized protocol for signing contracts, using an arbitrary Public Key Cryptosystem, is presented. The protocol uses an Oblivious Transfer sub-protocol, which allows one party to transfer a message to another with probability one half and without knowing whether the other party received it. An implementation of the Oblivious Transfer by Public Key Cryptosystem is presented.

In another chapter of this thesis it is proven that DES-like functions can generate the alternating group, thus removing the apprehension that the group of permutation generated by these functions is small.

Submitted to the Senate of the Technion, June 1983.

Available on-line: a more detailed description.


Back to Oded Goldreich's homepage.