Black-box constructions for secure computation

ABSTRACT

It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.

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: 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]
• 3: Coin Flipping by Phone. In IEEE Spring COMPCOM, pages 133--137, 1982.
• 4: R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 5: 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]
• 6: I. Damgard and Y. Ishai. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In CRYPTO 2005, Springer-Verlag (LNCS 3621), pages 378--394, 2005.
• 7: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 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: R. Gennaro, Y. Lindell and T. Malkin. Enhanced versus Plain Trapdoor Permutations for Non-Interactive Zero-Knowledge and Oblivious Transfer. Manuscript in preparation, 2006.
• 10: R. Gennaro , L. Trevisan, Lower bounds on the efficiency of generic cryptographic constructions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.305, November 12-14, 2000
• 11: 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
• 12: Y. Gertner , T. Malkin , O. Reingold, On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.126, October 14-17, 2001
• 13: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 14: 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]
• 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: Russell Impagliazzo , Steven Rudich, Limits on the Provable Consequences of One-way Permutations, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.8-26, August 21-25, 1988
• 17: Y.T. Kalai. Smooth Projective Hashing and Two-Message Oblivious Transfer. In EUROCRYPT 2005, Springer-Verlag (LNCS 3494) pages 78--95, 2005.
• 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, Uses of randomness in algorithms and protocols, MIT Press, Cambridge, MA, 1990
• 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: Jeong Han Kim , Daniel R. Simon , Prasad Tetali, Limits on the Efficiency of One-Way Permutation-Based Hash Functions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.535, October 17-18, 1999
• 22: 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
• 23: Y. Lindell. A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions. In EUROCRYPT 2003, Springer-Verlag (LNCS 2656), pages 241--254, 2003.
• 24: T. Malkin and O. Reingold. Personal communication, 2006.
• 25: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 26: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 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: M. Rabin. How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Harvard University, 1981.
• 29: O. Reingold, L. Trevisan, and S. Vadhan. Notions of Reducibility between Cryptographic Primitives. In 1st TCC, pages 1--20, 2004.
• 30: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999
• 31: S. Wolf and J. Wullschleger. Oblivious Transfer Is Symmetric. To appear in EUROCRYPT 2006. Appears at Cryptology ePrint Archive, Report 2004/336, 2004.
• 32: A. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages 162--167, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

General Terms:
Algorithms, Theory

Keywords:
black-box reductions, oblivious transfer, secure computation, theory of cryptography