Communication preserving protocols for secure function evaluation

ABSTRACT

A secure function evaluation protocol allows two parties to jointly compute a function f(x,y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: “any function f that can be computed using polynomial resources can be computed securely using polynomial resources” (where “resources” refers to communication and computation). This result follows by a general transformation from any circuit for f to a secure protocol that evaluates f. Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f.We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f. We start with an efficient (insecure) protocol for f and transform it into a secure protocol. In other words, ``any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter''. We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the Millionaires problem, where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.

REFERENCES

• 1: William Aiello , Yuval Ishai , Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.119-135, May 06-10, 2001
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72995]
• 4: Paul Beame , Martin Tompa , Peiyuan Yan, Communication-Space Tradeoffs for UnrestrictedProtocols, SIAM Journal on Computing, v.23 n.3, p.652-661, June 1994 [doi>10.1137/S0097539791196883]
• 5: Donald Beaver , Joan Feigenbaum , Joe Kilian , Phillip Rogaway, Security with Low Communication Overhead, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.62-76, August 11-15, 1990
• 6: 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]
• 7: C. Cachin, S. Micali and M. Stadler, Computationally Private Information Retrieval With Polylogarithmic Communication, Advances in Cryptology - Euorocrypt '99, LNCS 1592, Springer, pp. 402-414.
• 8: R. Canetti, Security and Composition of Multiparty Cryptographic Protocols, Journal of Cryptology 13(1), pp. 143-202, 2000.
• 9: Cynthia Dwork , Jeffrey Lotspiech , Moni Naor, Digital signets: self-enforcing protection of digital information (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.489-498, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237997]
• 10: Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195408]
• 11: J. Feigenbaum, J. Fong, M. Strauss, and R.N. Wright, Secure multiparty computation of approximations, DIMACS workshop on Cryptography andIntractability, March 20-22, 2000.
• 12: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 13: M. Furer, The power of randomness for communication complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.178-181, January 1987, New York, New York, United States [doi>10.1145/28395.28415]
• 14: O. Goldreich, Secure multi-party Computation, Theory of Cryptography Library, 1998,http://philby.ucsd.edu/cryptolib/
• 15: 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]
• 16: Yuval Ishai , Eyal Kushilevitz, Private Simultaneous Messages Protocols with Applications, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.174, June 17-19, 1997
• 17: Y. Ishai , E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.294, November 12-14, 2000
• 18: 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]
• 19: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 20: Joe Kilian, Improved Efficient Arguments (Preliminary Version), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.311-324, August 27-31, 1995
• 21: Sanjeev Khanna , Rajeev Motwani , Madhu Sudan , Umesh Vazirani, On Syntactic versus Computational Views of Approximability, SIAM Journal on Computing, v.28 n.1, p.164-191, Feb. 1999 [doi>10.1137/S0097539795286612]
• 22: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 23: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 24: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 25: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 26: 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
• 27: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 28: A.C. Yao, Protocols for Secure Computations, Proc. of the IEEE Symp. on Found. of Computer Science, 1982, pp. 160-164.
• 29: A.C. Yao, How to generate and exchange secrets, Proc. of the IEEE Symp. on Found. of Computer Science, 1986, pp. 162-167.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Design, Performance, Security, Standardization, Theory