Separating succinct non-interactive arguments from all falsifiable assumptions

By Craig Gentry, Daniel Wichs. 2011

531 citations recorded by the source corpus.

An argument system for NP is succinct, if its communication complexity is polylogarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. However, we currently do not have any construction of succinct non-interactive arguments (SNARGs) in the standard model with a proof of security under any simple cryptographic assumption. 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Zerocash: Decentralized Anonymous Payments from Bitcoin (2014, background): “While knowledge-of-exponent assumptions are fairly strong, there is evidence that such assumptions may be inherent for constructing zk-SNARKs [24, 25].”
Pinocchio: Nearly Practical Verifiable Computation (2013, background): “Gentry and Wichs recently showed that assumptions from this class are likely to be inherent for efficient, non-interactive arguments for NP relations [39].”
Verifying computations with state (2013, methodology): “The second variant is instantiated by Pinocchio [59] and known as a non-interactive argument [32, 33]: V preencrypts queries and sends them to P .”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Buffet allows the programmer to express programs in an expansive subset of C (disallowing only “goto” and function pointers), can handle essentially any example in the verifiable computation literature, and achieves the best performance in the area by multiple orders of magnitude.”
Aurora: Transparent Succinct Arguments for R1CS (2019, background): “Constructions that satisfy these properties are known as (publicly verifiable) succinct non-interactive arguments (SNARGs) [46].”
Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments (2012, unknown): “(See also [11].”
Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings (2019, background): “It is so far unknown how the AGM relates to knowledge-ofexponent (KOE) assumptions, which have been used to build every known SNARK that has been proven secure in the standard model (and indeed it is known that SNARKs cannot be proven secure under more standard falsifiable assumptions [41]).”
Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019, background): “Besides zkSNARKS might be subject to non-falsifiable cryptographic hardness assumptions [245].”
Homomorphic Signatures for Polynomial Functions (2011, background): “Moreover, anyone can further compute t := g(t) = g(f (D)) for some function g and use σ to derive a signature on t and the function g(f (·)).”
A Survey of Verifiable Computation (2017, background): “Recently, Gentry and Wichs [69] showed that no falsifiable cryptographic assumption can support CS proofs, which means it almost infeasible to use CS proofs in the real world.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “It avoids the issues listed above for Zaatar and IKO—at the cost of making q-type, knowledge of exponent (KOE) assumptions, which are non-standard and non-falsifiable (Zaatar does not need such assumptions, but it is worth noting that such assumptions are inherent for achieving non-interactivity in ”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “) For security, we require a non-falsifiable “knowledge” assumption which, as noted above, is necessary [1, 23].”