Impossibilities in Succinct Arguments: Black-box Extraction and More

Matteo Campanelli; Chaya Ganesh; Hamidreza Khoshakhlagh; Janno Siim

Paper 2022/638

Impossibilities in Succinct Arguments: Black-box Extraction and More

Matteo Campanelli, Protocol Labs

Chaya Ganesh, Indian Institute of Science Bangalore

Hamidreza Khoshakhlagh, Concordium

Janno Siim, Simula UiB

Abstract

The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages, we must assume non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to the proof size. 1. We start by formalizing a folklore lower bound for the proof size of black-box extractable arguments based on the hardness of the language. This separates knowledge-sound SNARGs (SNARKs) in the random oracle model (that can have black-box extraction) and those in the standard model. 2. We find a positive result in the non-adaptive setting. Under the existence of non-adaptively sound SNARGs (without extractability) and from standard assumptions, it is possible to build SNARKs with black-box extractability for a non-trivial subset of NP. 3. On the other hand, we show that (under some mild assumptions) all NP languages cannot have SNARKs with black-box extractability even in the non-adaptive setting. 4. The Gentry-Wichs result does not account for the preprocessing model, under which fall several efficient constructions. We show that also, in the preprocessing model, it is impossible to construct SNARGs that rely on falsifiable assumptions in a black-box way. Along the way, we identify a class of non-trivial languages, which we dub “trapdoor languages”, that bypass some of these impossibility results.

Note: Corrected issues pointed out in https://eprint.iacr.org/2024/227

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. Africacrypt 2023
Keywords: succinct arguments black-box extraction preprocessing SNARG
Contact author(s): matteo @ protocol ai
chaya @ iisc ac in
hk @ concordium com
janno @ simula no
History: 2024-08-06: last of 5 revisions; 2022-05-24: received; See all versions
Short URL: https://ia.cr/2022/638
License: CC BY

BibTeX

@misc{cryptoeprint:2022/638,
      author = {Matteo Campanelli and Chaya Ganesh and Hamidreza Khoshakhlagh and Janno Siim},
      title = {Impossibilities in Succinct Arguments: Black-box Extraction and More},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/638},
      year = {2022},
      url = {https://eprint.iacr.org/2022/638}
}