From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again

By Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer. 2012

588 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

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 Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Succinct non-interactive zero-knowledge proofs (SNARKs) [65] are a type of ZKP that provides constant proof size and verification that depends only on the input size, linearly.”
Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “Zero-knowledge SNARKs have been the subject of extensive research [Gro10,BCCT12,GGPR13, BCCT13,PHGR16,BSCG ` 13,Gro16].”
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].”
Verifying computations with state (2013, methodology): “Of course, Pantry’s general approach is known [11, 15, 32, 41].”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “Our protocol is public coin; we compile it into Hyrax, a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) [20] in the random oracle model [7], via the FiatShamir heuristic [41] (§7).”
PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations (2016, background): “SNARK constructions are known, and some are implemented, on the basis of knowledge-of-exponent assumptions [25], [35], [10], [43], [6], [4], [22] and extractable collision resistant hashes [8], [39], [10].”
ALITHEIA: Towards Practical Verifiable Graph Processing (2014, methodology): “A VC protocol for graph algorithms can be derived in theory via black-box use of existing general-purpose VC schemes [18, 14, 24, 9, 10, 19, 11], or one of the systems that have been built to apply these techniques [33, 32, 30, 7, 12, 36].”
On the Size of Pairing-Based Non-interactive Arguments (2016, background): “Gentry and Wichs [GW11] showed that SNARGs must necessarily rely on non-falsiﬁable assumptions, and Bitansky et al. [BCCT12] proved designated veriﬁer SNARKs exist if and only if extractable collision-resistant hash functions exist.”
On the existence of extractable one-way functions (2014, methodology): “the uniform distribution, required in [7].”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “All known PCP-based succinct argument constructions [61, 71, 5, 30, 22, 14, 29, 47] inherit these problem representations.”
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.”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “SHA-3, via the Fiat-Shamir heuristic [39] (or via an extractable collision resistant hash function [27]).”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, background): “As short PCPs are often a bottleneck in the development of efficient argument systems, other works have focused on avoiding their use [3,6,7,19].”
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].”