Rafail Ostrovsky - Publications

Zero-Knowledge from Secure Multiparty Computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

Abstract:

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a protocol for a related multi-party functionality 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 protocols. 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 \wedge,\vee,\oplus,\neg gates of unbounded fan-in, we get a zero-knowledge protocol with communication complexity m\cdot\poly(k)\cdot\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 get a 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.

comment: Preliminary version appeared In Proceedings of ACM Symposium on Theory of Computing (STOC-2007). Full version invited and accepted to SIAM Journal of Computing (SICOMP) special issue devoted to STOC-2007.

Fetch PostScript file of the paper     Fetch PDF file of the paper