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 {\em black-box} use of a secure protocol for a related {\em 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 {\em 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: Appeared In Proceedings of ACM Symposium on Theory of Computing (STOC-2007)

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