Dwork and Naor (FOCS'00) first introduced and constructed two message witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives.

In this talk, we will describe the first constructions of two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of standard cryptographic assumptions. We will also describe how to obtain somewhat stronger privacy guarantees than witness indistinguishability, and how to achieve public verification.

This talk is based on joint works with Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Yael Kalai and Amit Sahai.