Zero-knowledge from secure multiparty computation

ABSTRACT

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.

Approaching the witness length. If C has constant depth over ∧,∨,⊕, - gates of unbounded fan-in, we get a zero-knowledge protocol with communication complexity m·poly(k)·polylog(s), where k is a security parameter. Such a protocol can be implemented in either the standard interactive model or, following a trusted setup, in a non-interactive model.

"Constant-rate" zero-knowledge. For an arbitrary circuit C of size s and a bounded fan-in, we geta zero-knowledge protocol with communication complexity O(s)+poly(k). Thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. This improves over the O(ks) complexity of the best previous protocols.

REFERENCES

• 1: O. Barkol and Y. Ishai. Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems. In Proc. Crypto 2005, pages 395--411.
• 2: M. Bellare , S. Micali , R. Ostrovsky, The (true) complexity of statistical zero knowledge, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.494-502, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100285]
• 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: M. Blum. Coin Flipping by Telephone - A Protocol for Solving Impossible Problems. In Proc. COMPCON 1982: 133--137.
• 5: Joan Boyar , Gilles Brassard , René Peralta, Subquadratic zero-knowledge, Journal of the ACM (JACM), v.42 n.6, p.1169-1193, Nov. 1995 [doi>10.1145/227683.227686]
• 6: J. Boyar, I. Damgård and R. Peralta. Short Non-interactive Cryptographic Proofs. J. Cryptology 13(4): 449--472 (2000).
• 7: R. Canetti. Security and composition of multiparty cryptographic protocols. In J. of Cryptology, 13(1), 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: H. Chen and R. Cramer. Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields. In Proc. Crypto 2006.
• 10: Ronald Cramer , Ivan Damgård, Linear zero-knowledge—a note on efficient zero-knowledge proofs and arguments, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.436-445, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258635]
• 11: Ronald Cramer , Ivan Damgård, Zero-Knowledge Proofs for Finite Field Arithmetic; or: Can Zero-Knowledge be for Free?, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.424-441, August 23-27, 1998
• 12: I. Damgård and Y. Ishai. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In CRYPTO 2005, Springer-Verlag (LNCS 3621), pages 378--394, 2005.
• 13: I. Damgård and Y. Ishai. Scalable Secure Multiparty Computation. In Proc. CRYPTO 2006, pages 501--520.
• 14: 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]
• 15: Matthew Franklin , Moti Yung, Communication complexity of secure computation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.699-710, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129780]
• 16: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 17: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 18: O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9(3): 167--190 (1996)
• 19: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 20: Oded Goldreich , Johan Håstad, On the complexity of interactive proofs with bounded communication, Information Processing Letters, v.67 n.4, p.205-214, Aug. 31, 1998 [doi>10.1016/S0020-0190(98)00116-1]
• 21: Oded Goldreich , Silvio Micali , Avi Wigderson, How to prove all NP-statements in zero-knowledge, and a methodology of cryptographic protocol design, Proceedings on Advances in cryptology---CRYPTO '86, p.171-185, January 1987, Santa Barbara, California, United States
• 22: 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]
• 23: J. Groth, R. Ostrovsky, and A. Sahai. Perfect Non-interactive Zero Knowledge for NP. In Proc. EUROCRYPT 2006, pages 339--358.
• 24: I. Haitner and O. Reingold. Statistically-Hiding Commitment from Any One-Way Function. These proceedings.
• 25: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 26: 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
• 27: Yuval Ishai , Eyal Kushilevitz , Yehuda Lindell , Erez Petrank, Black-box constructions for secure computation, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132531]
• 28: Yael Tauman Kalai , Ran Raz, Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.355-366, October 21-24, 2006 [doi>10.1109/FOCS.2006.74]
• 29: Y.T. Kalai and R. Raz. Interactive PCP. Manuscript, 2007.
• 30: 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]
• 31: 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]
• 32: J. Kilian and E. Petrank. An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions. J. Cryptology 11(1), pages 1--27, 1998.
• 33: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 34: M. Naor. Bit commitment using pseudorandomness. J. of Cryptology, 4:151--158, 1991.
• 35: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 36: 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]
• 37: Manoj Prabhakaran , Alon Rosen , Amit Sahai, Concurrent Zero Knowledge with Logarithmic Round-Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.366-375, November 16-19, 2002
• 38: M. Rabin. How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981.
• 39: 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]
• 40: A. Razborov. Lower bounds for the size of circuits of bounded depth with basis all(AND, XOR). Math. Notes of the Academy of Science of the USSR, all 41(4):333--338, 1987.
• 41: O. Reingold, L. Trevisan, and S. P. Vadhan. Notions of Reducibility between Cryptographic Primitives. TCC 2004: 1--20.
• 42: A. Rosen. A Note on Constant Round Zero Knowledge Proofs for NP. In Proc. 1st TCC, 2004.
• 43: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 44: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
• 45: A.C. Yao. How to generate and exchange secrets. In Proc. 27th FOCS, pp. 162--167, 1986.

INDEX TERMS

General Terms:
Security, Theory

Keywords:
black-box reductions, cryptography, secure computation, zero-knowledge