Cryptology ePrint Archive: Report 2019/780

Statistical ZAP Arguments

Saikrishna Badrinarayan and Rex Fernando and Aayush Jain and 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 quasi-polynomial hardness of the learning with errors (LWE) assumption. 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.

Category / Keywords: cryptographic protocols / Witness Indistinguishability

Date: received 3 Jul 2019, last revised 3 Jul 2019

Contact author: saikrishna at cs ucla edu,rex1fernando@gmail com,aayushjainiitd@gmail com,dakshkhurana@gmail com,sahai@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20190709:182216 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]