Paper 2022/638

Impossibilities in Succinct Arguments: Black-box Extraction and More

Matteo Campanelli
Chaya Ganesh
Hamidreza Khoshakhlagh
Janno Siim
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 extractability and to the preprocessing model. 1. We first ask the question “are there further barriers to SNARGs that are knowledge-sound (SNARKs) and with a black-box extractor?”. We show it is impossible to have such SNARKs in the standard model. This separates SNARKs in the random oracle model (which can have black-box extraction) and those in the standard model. 2. We find positive results regarding the same question in the non-adaptive setting. Under the existence of 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
succinct arguments black-box extraction preprocessing SNARG
Contact author(s)
matteo @ protocol ai
chaya @ iisc ac in
hamidreza @ cs au dk
janno @ simula no
History
2022-06-20: revised
2022-05-24: received
See all versions
Short URL
https://ia.cr/2022/638
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/638}},
      url = {https://eprint.iacr.org/2022/638}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.