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

DOI10.1145/2090236.2090263zbMath1347.68129OpenAlexW2166670067MaRDI QIDQ2826067

Nir Bitansky, Eran Tromer, Ran Canetti, Alessandro Chiesa

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2090236.2090263

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Toward RSA-OAEP Without Random Oracles ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Composition with knowledge assumptions ⋮ Non-interactive batch arguments for NP from standard assumptions ⋮ On the (In)Security of SNARKs in the Presence of Oracles ⋮ SoK: communication across distributed ledgers ⋮ Families of SNARK-friendly 2-chains of elliptic curves ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ Refereed delegation of computation ⋮ On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption ⋮ Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation ⋮ Batch verifiable computation of outsourced functions ⋮ Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge ⋮ HyperPlonk: Plonk with linear-time prover and high-degree custom gates ⋮ A survey of elliptic curves for proof systems ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Oblivious message retrieval ⋮ Batch arguments for \textsf{NP} and more from standard bilinear group assumptions ⋮ Efficient zero-knowledge arguments in discrete logarithm setting: sublogarithmic proof or sublinear verifier ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ Onion routing with replies ⋮ \(\mathcal{Lunar}\): a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions ⋮ Succinct publicly-certifiable proofs. Or, can a blockchain verify a designated-verifier proof? ⋮ Nova: recursive zero-knowledge arguments from folding schemes ⋮ Threshold signatures with private accountability ⋮ Unnamed Item ⋮ Fully succinct batch arguments for \textsf{NP} from indistinguishability obfuscation ⋮ The hunting of the SNARK ⋮ Revisiting cycles of pairing-friendly elliptic curves ⋮ Non-interactive zero-knowledge from non-interactive batch arguments ⋮ \textsf{Orbweaver}: succinct linear functional commitments from lattices ⋮ Algebraic reductions of knowledge ⋮ Trojan-resilience without cryptography ⋮ Unnamed Item ⋮ An Introduction to the Use of zk-SNARKs in Blockchains ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Practical homomorphic message authenticators for arithmetic circuits ⋮ Generic hardness of inversion on ring and its relation to self-bilinear map ⋮ On the Connection between Leakage Tolerance and Adaptive Security ⋮ Chosen-Ciphertext Secure Fully Homomorphic Encryption ⋮ Multi-server verifiable delegation of computations: unconditional security and practical efficiency ⋮ SPARKs: succinct parallelizable arguments of knowledge ⋮ The Feasibility of Outsourced Database Search in the Plain Model ⋮ On the Existence of Extractable One-Way Functions ⋮ Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems ⋮ Constrained pseudorandom functions for Turing machines revisited: how to achieve verifiability and key delegation ⋮ Outsourcing computation: the minimal refereed mechanism ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ An Efficient Self-blindable Attribute-Based Credential Scheme ⋮ On succinct arguments and witness encryption from groups ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs

Cites Work