Rafail Ostrovsky - Publications

Zero-Knowledge from Secure Multiparty Computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai


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:

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

Back to Publications List