Efficient Secure Two-Party Protocols: Techniques and Constructions

Carmit Hazay and Yehuda Lindell

Information About the Book

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 12, "every circuit of the gate": it should say "every gate of the circuit". In addition, it is actually every AND gate (XOR gates are computed without any interaction).
2. Page 34, "Send input to trusted party": the adversary can send cheat_i, as well as abort_i and corrupted_i.
3. Page 39, 9th line of second paragraph: the deterministic functionality should be f' and not g.
4. Page 59, Definition 3.2.2: the definition should say for every positive polynomial.
5. Page 62, step 2 of the protocol: the value w_{1-\sigma} is chosen from the range of f (note that the domain equals the range since f is a permutation, but conceptually we choose this from the range).
6. Page 79, lines 6-7 from the top: P1 and P2 should be reversed.
7. Page 79, paragraph titled "symmetric computations": the expected number of decryptions is 5 per gate, and not 4 (the average of 2,4,6,8).
8. Page 154, first line of the proof: it should say "we now prove" and not "we know prove".
9. Pages 161-163: There is an error in the analysis in the proof of Theorem 6.5.2. The fix, as well as a (lengthy) explanation of what the problem was appears here.
10. Page 164, line 4 after the protocol description: it should say (x,r),(x',r') and not (x,r),(x',r).
11. Page 184, 3rd paragraph of the proof: it should say "Let R* be an arbitrary receiver" and not sender.
12. Pages 214-216: there is confusion caused by an ambiguous definition of which value to take when the size of the list is even.

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).