Probabilistically checkable arguments for all NP

DOI10.1007/978-3-031-58734-4_12MaRDI QIDQ6637335zbMATH OpenFDO

Authors Shany Ben-David

Publication date 13 November 2024

Full work available at URL https://doi.org/10.1007/978-3-031-58734-4_12

zbMATH Keywords

PCAsuccinct probabilistically checkable argument

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• Probabilistically Checkable Arguments
• Are PCPs inherent in efficient arguments?
• Interactive PCP
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Proving as fast as computing: succinct arguments with constant prover overhead

Cites work

• Advances in Cryptology - EUROCRYPT 2004
• Correlation intractability and SNARGs from sub-exponential DDH
• Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
• How to delegate computations publicly
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 7829262 (Why is no real title available?)
• New limits to classical and quantum instance compression
• On problems without polynomial kernels
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• Probabilistically Checkable Arguments
• Proof verification and the hardness of approximation problems
• SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
• Somewhere statistical soundness, post-quantum security, and SNARGs

Cited in

(3)

• Rate-1 statistical non-interactive zero-knowledge
• Instance compression, revisited
• Untangling the security of Kilian's protocol: upper and lower bounds

This page was built for publication: Probabilistically checkable arguments for all NP

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