ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation.

Abstract

We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: • ZAPs (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions. • NIWIs from indistinguishability obfuscation and one-way permutations. The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06]. ∗MIT. Email: [email protected]. Part of this work was done while at Tel Aviv University. †Boston University. Email: [email protected]. Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.