Quadratic Span Programs and Succinct NIZKs without PCPs

By Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova. 2013

917 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Privacy & Security, Automated Theorem Proving & Formal Methods

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 Computer Networks and Communications

In Privacy & Security

In Automated Theorem Proving & Formal Methods

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “Most existing SNARK constructions leverage quadratic arithmetic programs [174, 317, 118] and are now available in open-source libraries, such as libsnark [5], and deployed in cryptocurrencies, such as Zcash [57].”
Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “While one could use succinct zero-knowledge proofs (SNARKs) [4], [5], they require a trusted setup, which means that everyone needs to trust that the setup was performed correctly.”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “Prio improves client performance as well: it is 50-100× faster than NIZKs and we estimate that it is three orders of magnitude faster than methods based on succinct non-interactive arguments of knowledge (SNARKs) [16,62,97].”
Geppetto: Versatile Verifiable Computation (2015, methodology): “Just as in a standard QAP proof [29], calculate h ( x ) such that h ( x ) δ ( x ) = v ( x ) w ( x ) − y ( x ) , that is, the polynomial that proves that δ ( x ) divides v ( x ) w ( x ) − y ( x ) .”
Verifying computations with state (2013, background): “The other two are looping and if-else statements: loops are unrolled at compile time, and the costs of an if-else statement combine the costs of the then-block and the else-block [20].”
ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (2015, methodology): “Lemma 1 (Constructing QAPs [11, 17]): There exist two polynomial time algorithms QAPInst and QAPwit such that, for any circuit C : Fn×Fh → F with u wires and v (bilinear) gates, QC = ( #„ a , #„ b , #„ c , z) = QAPInst(C) is a QAP of size m and degree d over F satisfying the following properties:”
Full Accounting for Verifiable Outsourcing (2017, background): “Thus, the following discussion should be understood to cover only the proposed application of SNARKs to verifiable outsourcing [27, 47, 66].”
Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes (2013, methodology): “We only mention that one can construct a related zap [8], and a related (public or designatedverifier) succinct non-interactive argument of knowledge (SNARK, see [22,6]) by using the techniques of [1,14].”
Arbitrum: Scalable, private smart contracts (2018, methodology): “Hawk [18] is a proposed system for private smart contracts using zkSNARKs [16, 27].”
Verifying computations without reexecuting them (2015, methodology): “Applying prior insights [12, 22, 41], BCGTV combines this circuit with proof machinery (transcript encoding, queries, etc.) from Pinocchio and GGPR. BCGTV’s circuit representation consists of the unrolled execution of a general-purpose MIPS-like CPU, called TinyRAM (and for convenience we sometimes…”
Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, background): “[26] introduced quadratic arithmetic programs (QAPs), which forms the basis of most recent implementations [11,14,19,23,25,40,46] including libSNARK [13].”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Reducing from BHRAM to sCSAT benefits many zero-knowledge argument systems, including [52, 51, 1, 48, 50, 49, 66, 35, 15].”
Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives (2017, background): “5Using SNARKS is reasonable in scenarios where provers are extremely powerful (such as verifiable computing [42]) or the runtime of the prover is not critical (such as Zerocash [14]).”