Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments

By Helger Lipmaa. 2012

257 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

1. Srinath T. V. Setty
2. Eli Ben-Sasson
3. Michael Walfish
4. Dan Boneh
5. Andrew Justin Blumberg
6. Justin Thaler
7. Eran Tromer
8. Alessandro Chiesa

In Computational Theory and Mathematics

1. Srinath T. V. Setty
2. Eli Ben-Sasson
3. Michael Walfish
4. Andrew Justin Blumberg
5. Justin Thaler
6. Eran Tromer
7. Michael Riabzev
8. Alessandro Chiesa

Citations in the corpus

• Zerocash: Decentralized Anonymous Payments from Bitcoin (2014, methodology): “Specifically, it uses zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) [9, 10, 11, 12, 13, 14, 15, 16].”
• Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting (2016, background): “An exciting line of research [22, 30, 6, 13, 7, 34, 4, 5, 24] has developed many proposals for succinct non-interactive arguments (SNARGs) yielding pairingbased constructions where the arguments consist of a constant number of group elements.”
• Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, methodology): “Following earlier work of Ishai [34], Groth [33] and Lipmaa [38], Gennaro et al.”
• Succinct Malleable NIZKs and an Application to Compact Shuffles (2013, methodology): “More recently, Groth provided a construction using pairings [22] which was improved by Lipmaa [26], Bitansky et al. [3] constructed designated-verifier SNARGs using the new notion of extractable collision-resistant hash functions, and Gennaro et al. [17] constructed constant-sized SNARGs with a rela”
• Resolving the conflict between generality and plausibility in verified computation (2013, background): “Unfortunately, despite advances in the ef.ciency of FHE [29], it remains highly impractical.”
• 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].”
• Scalable, transparent, and post-quantum secure computational integrity (2018, background): “al [53] (see [64, 52, 81, 30, 62, 63] for related work and further improvements).”
• Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes (2013, methodology): “Very recently, Fauzi, Lipmaa and Zhang [10] constructed arguments for NP-complete languages Set Partition, Subset Sum and Decision Knapsack with the CRS length Θ(r−13 (s)) and prover’s computation Θ(r−13 (s) log s).”
• Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “KOE-based: A sequence of works [47, 41, 59, 29, 42] improved on [52] by relying on Knowledge Of Exponent (KOE) assumptions and bilinear pairings over elliptic curves.”
• Time-Optimal Interactive Proofs for Circuit Evaluation (2013, methodology): “[19], building on work of Groth [22] and Lipmaa [28], develop a model of computation called Quadratic Span Programs (QSPs) that is amenable to fast checking using cryptographic tools, but that also allows for fast reductions from a more practical model of computation (namely, circuit satisfiability)”