Paper 2019/780

Statistical ZAP Arguments

Saikrishna Badrinarayan, Rex Fernando, Aayush Jain, Dakshita Khurana, and Amit Sahai


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 statistical privacy, assuming the learning with errors (LWE) assumption holds with an explicit, efficently computable upper bound on the adversary’s advantage. 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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
Witness Indistinguishability
Contact author(s)
saikrishna @ cs ucla edu
rex1fernando @ gmail com
aayushjainiitd @ gmail com
dakshkhurana @ gmail com
sahai @ cs ucla edu
2020-06-06: last of 3 revisions
2019-07-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayan and Rex Fernando and Aayush Jain and Dakshita Khurana and Amit Sahai},
      title = {Statistical {ZAP} Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2019/780},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.