Efficient Secure Two-Party Protocols: Techniques and Constructions

Carmit Hazay and Yehuda Lindell

Book Jacket for Efficient Secure Two-Party Protocols

Information About the Book

Efficient Secure Two-Party Protocols: Techniques and Constructions, published in November 2010 by Springer, presents a comprehensive study of efficient protocols and techniques for secure two-party computation both general constructions that can be used to securely compute any functionality, and protocols for specific problems of interest. The book focuses on techniques for constructing efficient protocols and proving them secure. In addition, we study different definitional paradigms and compare the efficiency of protocols achieved under these different definitions.

This book is useful for practitioners and researchers in the field of secure protocols, particularly those with a focus on efficiency, and for researchers in the area of privacy-preserving data mining. This book can also be used as a textbook for an advanced course on secure protocols.

The preface, table of contents and introduction are available for perusal, and a review of the book that appeared in SIGACT NEWS can be found here..


Purchase Information

Those with access to SpringerLink can read the book online here. The book can be purchased directly from the publisher or from Amazon.


Comments and Errata

Errata:

  1. Page 34, "Send input to trusted party": the adversary can send cheati, as well as aborti and corruptedi.
  2. Page 59, Definition 3.2.2: the definition should say for every positive polynomial.
We thank Ran Cohen for pointing out the above errata.

Comments:

  1. Semi-honest Yao with OT that is secure for malicious adversaries: Consider the following two changes to the semi-honest construction of Yao as described in Chapter 3 (Protocol 3.4.1). First, replace the oblivious transfer with one that is secure in the presence of malicious adversaries, and then change the order of the protocol so that the garbled circuit is sent after the oblivious transfers are finished. Then, it holds that this protocol meets the definition of one-sided simulatability (see Section 2.6.2). This is of interest since the resulting construction is highly efficient (essentially the same as the semi-honest), and yet it achieves a meaningful level of security even for malicious adversaries. We stress that the order of the protocol must be changed - the garbled circuit being sent only after the oblivious transfers - in order to enable the simulator for the case that Party 2 is corrupted to extract the party's input (and thus output) before constructing the fake garbled circuit. We also stress that one-sided simulatability is a meaningful notion but it has its weaknesses; see the discussion in Section 2.6.2.
  2. Making Yao more efficient: The presentation of Yao's protocol in Chapter 3 uses a method of encrypting redundant zeroes in order to enable the circuit computer to detect which decryption is correct. This has two disadvantages: first, it potentially blows up the size of the ciphertexts; and second it requires the circuit computer to carry out an expected 5 decryptions per gate (2 decryptions per ciphertext, and an expected 2.5 ciphertexts need to be decrypted), rather than just two decryptions when you know exactly which ciphertext to decrypt. It is possible to improve this by choosing a random "signal" or "permutation" bit on every wire. Then, the encryption in each gate includes the identity of the key XORed with the signal bit. Furthermore, the garbled gates are constructed in a correct order based on the signal bits, so that the computer can immediately know which ciphertext to decrypt. This reveals nothing since the signal bit is random and independent for each wire. A detailed description of this optimization can be found in the paper "Privacy Preserving Auctions and Mechanism Design" by Naor, Pinkas and Sumner (in the 1st ACM conference on Electronic Commerce, 1999).