CryptoDB
Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG
| Authors: |
|
|---|---|
| Download: | |
| 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
}