International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Statistical ZAP Arguments

Saikrishna Badrinarayanan , VISA Research
Rex Fernando , UCLA
Aayush Jain , UCLA
Dakshita Khurana , UIUC
Amit Sahai , UCLA
DOI: 10.1007/978-3-030-45727-3_22 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: Dwork and Naor (FOCS'00) first introduced and constructed two message public coin 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. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with {\em statistical} privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.
Video from EUROCRYPT 2020
  title={Statistical ZAP Arguments},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={ZAPs;witness indistinguishable arguments;LWE.},
  author={Saikrishna Badrinarayanan and Rex Fernando and Aayush Jain and Dakshita Khurana and Amit Sahai},