Completeness in two-party secure computation: a computational view

ABSTRACT

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

REFERENCES

• 1: 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
• 2: Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
• 3: 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]
• 4: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 5: 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]
• 6: Claude Crépeau, Equivalence Between Two Flavours of Oblivious Transfers, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.350-354, August 16-20, 1987
• 7: I. Damgard, J. Kilian, and L. Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Eurocrypt '99, volume 1592, pages 56--73, 1999.
• 8: 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]
• 9: Matthias Fitzi , Juan A. Garay , Ueli M. Maurer , Rafail Ostrovsky, Minimal Complete Primitives for Secure Multi-party Computation, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.80-100, August 19-23, 2001
• 10: Y. Gertner , S. Kannan , T. Malkin , O. Reingold , M. Viswanathan, The relationship between public key encryption and oblivious transfer, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.325, November 12-14, 2000
• 11: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 12: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 13: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 14: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 15: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 16: O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR-lemma. In ECCC (50), volume 2, 1995.
• 17: D. Harnik, M. Naor, O. Reingold, and A. Rosen. Completeness in two-party secure computation - a computational view. ECCC, TR03-060, 2003.
• 18: R. Impagliazzo, A personal view of average-case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.134, June 19-22, 1995
• 19: R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In 30th FOCS, pages 230--235, 1989.
• 20: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 21: Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
• 22: 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]
• 23: 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]
• 24: Joe Kilian , Eyal Kushilevitz , Silvio Micali , Rafail Ostrovsky, Reducibility and Completeness in Private Computations, SIAM Journal on Computing, v.29 n.4, p.1189-1208, Feb. 2000 to March 2000 [doi>10.1137/S0097539797321742]
• 25: Eyal Kushilevitz, Privacy and communication complexity, SIAM Journal on Discrete Mathematics, v.5 n.2, p.273-284, May 1992 [doi>10.1137/0405021]
• 26: E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and completeness in multi-party private computations. In 35th FOCS, pages 478--489, 1994.
• 27: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 28: R. Ostrovsky and A. Wigderson. One-way fuctions are essential for non-trivial zero-knowledge. In Second Israel Symposium on Theory of Computing Systems, ISTCS 93, Proceedings. IEEE Computer Society, pages 3--17, 1993.
• 29: M. O. Rabin. How to exchange secrets by oblivious transfer. TR-81, Harvard, 1981.
• 30: A. C. Yao. Theory and application of trapdoor functions. In 23rd FOCS, pages 80--91, 1982.
• 31: A. C. Yao. How to generate and exchange secrets. In 27th FOCS, pages 162--167, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
completeness, oblivious tansfer, secure computation