Statistical zapr arguments from bilinear maps

Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

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

3 Scopus citations

Abstract

Dwork and Naor (FOCS ’00) defined ZAPs as 2-message witness-indistinguishable proofs that are public-coin. We relax this to ZAPs with private randomness (ZAPRs), where the verifier can use private coins to sample the first message (independently of the statement being proved), but the proof must remain publicly verifiable given only the protocol transcript. In particular, ZAPRs are reusable, meaning that the first message can be reused for multiple proofs without compromising security. Known constructions of ZAPs from trapdoor permutations or bilinear maps are only computationally WI (and statistically sound). Two recent results of Badrinarayanan-Fernando-Jain-Khurana-Sahai and Goyal-Jain-Jin-Malavolta [EUROCRYPT ’20] construct the first statistical ZAP arguments, which are statistically WI (and computationally sound), from the quasi-polynomial LWE assumption. Here, we construct statistical ZAPR arguments from the quasi-polynomial decision-linear (DLIN) assumption on groups with a bilinear map. Our construction relies on a combination of several tools, including the Groth-Ostrovsky-Sahai NIZK and NIWI [EUROCRYPT ’06, CRYPTO ’06, JACM ’12], “sometimes-binding statistically hiding commitments” [Kalai-Khurana-Sahai, EUROCRYPT ’18] and the “MPC-in-the-head” technique [Ishai-Kushilevitz-Ostrovsky-Sahai, STOC ’07].

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
Pages620-641
Number of pages22
ISBN (Print)9783030457266
DOIs
StatePublished - 2020
Externally publishedYes
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
Country/TerritoryCroatia
CityZagreb
Period5/10/205/14/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Statistical zapr arguments from bilinear maps'. Together they form a unique fingerprint.

Cite this