International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG

Authors:
Helger Lipmaa , Simula UiB, Norway
Kateryna Pavlyk , Simula UiB, Norway
Download:
DOI: 10.1007/978-3-030-92078-4_2
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: By the impossibility result of Gentry and Wichs, non-falsifiable assumptions are needed to construct (even non-zero-knowledge) adaptively sound succinct non-interactive arguments (SNARGs) for hard languages. It is important to understand whether this impossibility result is tight. While it is known how to construct adaptively sound non-succinct non-interactive arguments for $\mathsf{NP}$ from falsifiable assumptions, adaptively sound SNARGs for $\mathsf{NP}$ from non-falsifiable assumptions, and adaptively sound SNARGs for $\mathsf{P}$ from falsifiable assumptions, there are no known non-adaptively sound SNARGs for $\mathsf{NP}$ from falsifiable assumptions. We show that Gentry-Wichs is tight by constructing the latter. In addition, we prove it is non-adaptively knowledge-sound in the algebraic group model and Sub-ZK (i.e., zero-knowledge even if the CRS is subverted) under a non-falsifiable assumption.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31492,
  title={Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92078-4_2},
  author={Helger Lipmaa and Kateryna Pavlyk},
  year=2021
}