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
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 |