Abstract: Succinct non-interactive arguments (or SNARGs) are
computationally sound proofs whose communication complexity is
polylogarithmic the instance and witness sizes. Unfortunately, we
currently do not know of any construction of SNARGs with a formal
proof of security under any simple assumption. My talk will give a
broad black-box separation result, showing that the security of SNARGs
cannot be proven via a black-box reduction from any falsifiable
cryptographic assumption. This includes essentially all common
assumptions used in cryptography (one-way functions, trapdoor
permutations, DDH, RSA, LWE etc.). The 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.
Joint work with Craig Gentry