Oded Goldreich's D.Sc Thesis (Technion, June 1983) TITLE: On the Security of Cryptographic Protocols and Cryptosystems ACKNOWLEDGEMENTS This research was carried out in the Faculty of Computer Science under the supervision of Professor Shimon Even. My deepest gratitude to Prof. Shimon Even for his judgment, for his encouragement and for his devoted guidance. I wish to thank Prof. Abraham Lempel for his contributions to this research and for his advice. TABLE OF CONTENTS Page Abstract........................................ 1 List of Symbols and Abbreviations .............. 3 Chapter One: Background ........................ 4 1.1 At the Dawn of Modern Cryptography ........ 4 1.2 Conventional Cryptosystems (the DES)....... 4 1.3 Public Key Cryptosystem (PKCS)............. 5 1.4 Protocols for Distributed Problems......... 6 1.5 On the Security of Cryptographic Protocols.................................. 6 Chapter Two: On the Permutations Realizable by the DES................................. 7 Chapter Three: On the Power of Cascade Ciphers.. 9 Chapter Four: Protocols for Signing Contracts and Other Problems......................... 12 Chapter Five: On the Security of Ping-Pong Protocols.................................. 14 References...................................... 16 Appendices...................................... 19 The work itself appears in the appendices, which are detailed below. A: DES-Like Functions Can Generate the Alternating Group B: On the Generating Power of q-ary Block Ciphers C: On the Power of Cascade Ciphers D: The Minimum-Length Generator Sequence Problem is NP-Hard E: An Approximation Protocol for Signing Contracts F: A Protocol for Sending Certified Mail G: A Randomized Protocol for Signing Contracts H: Sending Certified Mail using the ESS I: On the Security of Multi-Party Ping-Pong Protocols Further details follow. ======================================================================= APPENDIX A: DES-Like Functions Can Generate the Alternating Group A set of transformation on binary vectors of length n is defined. These transformation are similar to those of the DES and therefore are called DES-like-functions. It is proved that the group of permutations generated by the DES-like-functions is exactly the Alternating Group of the set of binary n-vectors. Technical Report #258 by S. Even and O. Goldreich. (This is a revised version of Report #207) Published in IEEE Trans. on Inform. Theory, Vol. IT-29, No. 6, pp. 863--865, 1983. ======================================================================= APPENDIX B: On the Generating Power of q-ary Block Ciphers Two sets of transformations on q-ary vectors of length n are defined. It is shown that each of these sets can generate any even permutation on the set of q-ary n-vectors. (This study refers to a generalization of the work in Apdx A.) Technical Report #264 by O. Goldreich. ======================================================================= APPENDIX C: On the Power of Cascade Ciphers A cascade cipher is defined as a concatenation of block cipher systems called its stages. We present an algorithm, with time-space trade-off, for finding the key of a cascade cipher given pairs of plaintext-ciphertext. We conjecture that the strength of a cascade cipher is exponential in its length (i.e. 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 results about cascades 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 ciphertext. Technical Report #275 by S. Even and O. Goldreich. Published in ACM Trans. on Computer Systems, Vol. 3, No. 2, pp. 108--116, 1985. Preliminary version appeared in the proceedings of Crypto83. ======================================================================= APPENDIX D: The Minimum-Length Generator Sequence Problem is NP-Hard A natural problem which arises in connection with the isomorphism problem for graphs of bounded degree [1], and in connection with the Rubic-color-cube puzzle [2] is the following. Given a set of generators of a permutation group, determine whether a given permutation is in the group. This problem was solved by Sims [3] and the solution was investigated and shown to be polynomial by Furst et al. [4]. We examine the following question: (1) Given a set of generators of a permutation group G and a target permutation P, find (the length of) a shortest generator sequence realizing P. (2) Given a set of generators of a permutation group G, find the minimum upper bound on the length of generator sequences needed to realize any permutation in G. We show that both problems are NP-Hard by reducing the 3XC problem to each of them. The reductions we use show that these results hold even if the given set of generators is restricted to contain for each generator its inverse too. By S. Even and O. Goldreich. Published in Journal of Algorithms, Vol. 2, pages 311-313, 1981. ======================================================================= APPENDIX E: An Approximation Protocol for Signing Contracts An approximation protocol for signing contracts is presented. This protocol is a simplification of Even's protocol [3] and demonstrates that the randomization in that protocol is not essential. The main advantage of the protocol is its simplicity. Technical Report #259 by O. Goldreich. Appeared in the proceedings of Crypto83. ======================================================================= APPENDIX F: A Protocol for Sending Certified Mail A protocol for sending certified mail is presented. Using this protocol, the sender can prove an upper bound on the amount of work the receiver must invest in order to read the message. The protocol uses any public-key cryptosystem and can be used to mail disclosures or sign contracts. Technical Report #239 by O. Goldreich. ======================================================================= APPENDIX G: A Randomized Protocol for Signing Contracts A randomized protocol for signing contracts, using an arbitrary public key cryptosystem, is presented. The protocol uses an Oblivious Transfer subprotocol, 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 any public-key cryptosystem is presented. By S. Even, O. Goldreich and A. Lempel Published in Comm. of the ACM, Vol. 28, No. 6, pp. 637--647, 1985. Preliminary version appeared in the proceedings of Crypto82. ======================================================================= APPENDIX H: Sending Certified Mail using the ESS (This is an unpublished technical memo, which describes a small variant on some of the appplications described in Apdx G.) By O. Goldreich ======================================================================= APPENDIX I: On the Security of Multi-Party Ping-Pong Protocols (This is the main part of the thesis. It is described in webpage http://www.wisdom.weizmann.ac.il/~oded/eg83.html) Appeared in the proceedings of the 24th FOCS, pp. 34-39, 1983. By S. Even and O. Goldreich =======================================================================