Succinct NP Proofs from an Extractability Assumption

DOI10.1007/978-3-540-69407-6_21zbMath1142.68370OpenAlexW2137467444MaRDI QIDQ3507432

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)

Related Items (12)

Succinct non-interactive arguments via linear interactive proofs ⋮ On the (In)Security of SNARKs in the Presence of Oracles ⋮ Refereed delegation of computation ⋮ On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ The hunting of the SNARK ⋮ Unnamed Item ⋮ Cryptographic Assumptions: A Position Paper ⋮ On subversion-resistant SNARKs ⋮ On the Existence of Extractable One-Way Functions ⋮ On succinct arguments and witness encryption from groups ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation

Cites Work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Minimum disclosure proofs of knowledge
• Necessary and sufficient conditions for collision-free hashing
• Proof verification and the hardness of approximation problems
• A PCP characterization of NP with optimal amortized query complexity
• On the Feasibility of Consistent Computations
• Universal Arguments and their Applications
• The Knowledge Complexity of Interactive Proof Systems
• Probabilistic checking of proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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