Complete fairness in secure two-party computation

ABSTRACT

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness, which guarantees that if either party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s.

In this paper, we demonstrate that this widely held folklore belief is false by showing completely-fair secure protocols for various non-trivial two-party functions including Boolean AND/OR as well as Yao's "millionaires' problem". Surprisingly, we show that it is even possible to construct completely-fair protocols for certain functions containing an "embedded XOR", although in this case we also prove a lower bound showing that a super-logarithmic number of rounds are necessary. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

REFERENCES

• 1: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 2: D. Beaver. Secure Multi-Party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. Journal of Cryptology 4(2):75--122, 1991.
• 3: D. Beaver , S. Goldwasser, Multiparty computation with faulty majority, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.468-473, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63520]
• 4: Amos Beimel , Tal Malkin , Silvio Micali, The All-or-Nothing Nature of Two-Party Secure Computation, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.80-97, August 15-19, 1999
• 5: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 6: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 7: . Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology 13(1): 143--202, 2000.
• 8: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 9: Benny Chor , Eyal Kushilevitz, A zero-one law for Boolean privacy, SIAM Journal on Discrete Mathematics, v.4 n.1, p.36-47, Feb. 1991 [doi>10.1137/0404004]
• 10: R Cleve, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.364-369, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12168]
• 11: D. Dolev and H. Strong. Authenticated Algorithms for Byzantine Agreement. SIAM Journal on Computing, 12(4):656--666, 1983.
• 12: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 13: Zvi Galil , Stuart Haber , Moti Yung, Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.135-155, August 16-20, 1987
• 14: J. Garay, P. MacKenzie, M. Prabhakaran, and K. Yang. Resource Fairness and Composability of Cryptographic Protocols. In 3rd TCC, Springer-Verlag (LNCS 3876), pages 404--428, 2006.
• 15: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 16: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 17: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 18: Dov S. Gordon , Hazay Carmit , Jonathan Katz , Yehuda Lindell, Complete fairness in secure two-party computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374436]
• 19: Joe Kilian, A general completeness theorem for two party games, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.553-560, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103475]
• 20: Joe Kilian, More general completeness theorems for secure two-party computation, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.316-324, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335342]
• 21: Y. Lindell. Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. Journal of Cryptology 16(3): 143--184, 2003.
• 22: Michael Luby , Silvio Micali , Charles Rackoff, How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin, Proceedings of the 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), p.11-22, November 07-09, 1983 [doi>10.1109/SFCS.1983.25]
• 23: S. Micali and P. Rogaway. Secure Computation. Unpublished manuscript, 1992. Preliminary version in Crypto '91, Springer-Verlag (LNCS 576),pages 392--404, 1991.
• 24: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 25: . Pinkas. Fair Secure Two-Party Computation. In Eurocrypt 2003, Springer-Verlag (LNCS 2656), pages 87--105, 2003.
• 26: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 27: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Security, Theory

Keywords:
cryptography, fairness, secure computation