Paper 2019/780
Statistical ZAP Arguments
Saikrishna Badrinarayan, Rex Fernando, Aayush Jain, Dakshita Khurana, and Amit Sahai
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 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2020
- Keywords
- Witness Indistinguishability
- Contact author(s)
-
saikrishna @ cs ucla edu
rex1fernando @ gmail com
aayushjainiitd @ gmail com
dakshkhurana @ gmail com
sahai @ cs ucla edu - History
- 2020-06-06: last of 3 revisions
- 2019-07-09: received
- See all versions
- Short URL
- https://ia.cr/2019/780
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/780,
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},
url = {https://eprint.iacr.org/2019/780}
}