CWI Cryptology Group

Abstract: A zero-knowledge proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows $n$ mutually suspicious parties to jointly compute a function of their local inputs without revealing to any $t$ corrupted parties additional information beyond the output of the function.
We present a new general connection between these two fundamental notions. Specifically, we show that a zero-knowledge proof for a given NP language can be obtained by making a black-box use of any $n$-party protocol for a related function. The latter protocol only needs to be secure against a small number of "honest-but-curious" parties. This new connection allows us to draw on a large body of techniques for secure multiparty computation with honest majority ($t < n/2$) in order to improve the efficiency of zero-knowledge proofs.
Joint work with Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai (STOC '07).