TY - GEN
T1 - Statistical zap arguments
AU - Badrinarayanan, Saikrishna
AU - Fernando, Rex
AU - Jain, Aayush
AU - Khurana, Dakshita
AU - Sahai, Amit
N1 - Funding Information:
Rex Fernando, Aayush Jain and Amit Sahai were supported in part by the following: a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, NSF grants 1619348, 1228984, 1136174, and 1065276, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. Aayush Jain was also supported by a Google PhD Fellowship (2018) in the area of Privacy and Security. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government, or Google.
Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - 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 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.
AB - 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 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.
UR - http://www.scopus.com/inward/record.url?scp=85089721779&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089721779&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-45727-3_22
DO - 10.1007/978-3-030-45727-3_22
M3 - Conference contribution
AN - SCOPUS:85089721779
SN - 9783030457266
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 642
EP - 667
BT - Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Canteaut, Anne
A2 - Ishai, Yuval
PB - Springer
T2 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
Y2 - 10 May 2020 through 14 May 2020
ER -