Statistical zap arguments

Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Dakshita Khurana, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsAnne Canteaut, Yuval Ishai
PublisherSpringer
Pages642-667
Number of pages26
ISBN (Print)9783030457266
DOIs
StatePublished - 2020
Event39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia
Duration: May 10 2020May 14 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12107 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
CountryCroatia
CityZagreb
Period5/10/205/14/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Statistical zap arguments'. Together they form a unique fingerprint.

Cite this