2022-09-09
/
Report
Impossibilities in succinct arguments: Black-box extraction and more
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.
Matteo Campanelli
,
Chaya Ganesh,
Hamidreza Khoshakhlagh,
Janno Siim