Succinct NP Proofs from an Extractability Assumption

DOI10.1007/978-3-540-69407-6_21MaRDI QIDQ3507432zbMATH OpenOpenAlexFDO

Authors Giovanni Di Crescenzo, Helger Lipmaa

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• An efficient noninteractive zero-knowledge proof system for NP with general assumptions
• Spooky interaction and its discontents: compilers for succinct two-message argument systems
• Separating succinct non-interactive arguments from all falsifiable assumptions
• The hunting of the SNARK
• Theory of Cryptography

Cites work

• A PCP characterization of NP with optimal amortized query complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• scientific article; zbMATH DE number 1670844 (Why is no real title available?)
• scientific article; zbMATH DE number 176566 (Why is no real title available?)
• scientific article; zbMATH DE number 1302862 (Why is no real title available?)
• scientific article; zbMATH DE number 1304086 (Why is no real title available?)
• Minimum disclosure proofs of knowledge
• Necessary and sufficient conditions for collision-free hashing
• On the feasibility of consistent computations
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• The Knowledge Complexity of Interactive Proof Systems
• Universal Arguments and their Applications

Cited in

(20)

• The hunting of the SNARK
• On subversion-resistant SNARKs
• On succinct arguments and witness encryption from groups
• Succinct non-interactive arguments via linear interactive proofs
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
• Cryptographic assumptions: a position paper
• On the existence of extractable one-way functions
• Spooky interaction and its discontents: compilers for succinct two-message argument systems
• On constant-round concurrent zero-knowledge from a knowledge assumption
• On the (in)security of SNARKs in the presence of oracles
• Refereed delegation of computation
• Multikey fully homomorphic encryption and applications
• Succinct Permanent Is NEXP-Hard with Many Hard Instances
• Lattice-based SNARGs and their application to more efficient obfuscation
• Theory of Cryptography
• scientific article; zbMATH DE number 7746256 (Why is no real title available?)
• Locally verifiable distributed SNARGs
• Polymath: Groth16 is not the limit
• On knowledge-soundness of Plonk in ROM from falsifiable assumptions
• Plonk is simulation extractable in ROM under falsifiable assumptions

This page was built for publication: Succinct NP Proofs from an Extractability Assumption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507432)