In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor '03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption.
Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sublinear in the statement and witness size.
Category / Keywords: foundations / black-box separation, computationally sound proofs Date: received 29 Nov 2010, last revised 2 Jun 2011 Contact author: wichs at cs nyu edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Revised 6/02/11 with minor edits. Version: 20110602:171542 (All versions of this report) Discussion forum: Show discussion | Start new discussion