Article

Are PCPs Inherent in Efficient Arguments?

Authors:

Guy N. Rothblum,

Salil VadhanAuthors Info & Claims

CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity

Pages 81 - 92

https://doi.org/10.1109/CCC.2009.40

Published: 15 July 2009 Publication History

Publisher Site

Abstract

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs are inherent in efficient arguments, and to what extent. We give evidence that they are, by showing how to convert any argument system whose soundness is reducible to the security of some cryptographic primitive into a PCP system whose efficiency is related to that of the argument system and the reduction (under certain complexity assumptions).

Cited By

View all

Goldwasser SKalai YRothblum G(2015)Delegating ComputationJournal of the ACM10.1145/269943662:4(1-64)Online publication date: 11-Sep-2015
https://dl.acm.org/doi/10.1145/2699436
Bitansky NCanetti RChiesa ATromer EBoneh DRoughgarden TFeigenbaum J(2013)Recursive composition and bootstrapping for SNARKS and proof-carrying dataProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488623(111-120)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488623
Bitansky NChiesa A(2012)Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency BenefitsProceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 741710.1007/978-3-642-32009-5_16(255-272)Online publication date: 19-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32009-5_16
Show More Cited By

Recommendations

Combinatorial PCPs with Efficient Verifiers

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...
Are PCPs Inherent in Efficient Arguments?
Selected papers from the 24th Annual IEEE Conference on Computational Complexity (CCC 2009)

Starting with Kilian (STOC ‘92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound ...
Combinatorial PCPs with Efficient Verifiers
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity

July 2009

377 pages

ISBN:9780769537177

Publisher

IEEE Computer Society

United States

Publication History

Published: 15 July 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Goldwasser SKalai YRothblum G(2015)Delegating ComputationJournal of the ACM10.1145/269943662:4(1-64)Online publication date: 11-Sep-2015
https://dl.acm.org/doi/10.1145/2699436
Bitansky NCanetti RChiesa ATromer EBoneh DRoughgarden TFeigenbaum J(2013)Recursive composition and bootstrapping for SNARKS and proof-carrying dataProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488623(111-120)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488623
Bitansky NChiesa A(2012)Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency BenefitsProceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 741710.1007/978-3-642-32009-5_16(255-272)Online publication date: 19-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32009-5_16
Gennaro RGentry CParno B(2010)Non-interactive verifiable computingProceedings of the 30th annual conference on Advances in cryptology10.5555/1881412.1881445(465-482)Online publication date: 15-Aug-2010
https://dl.acm.org/doi/10.5555/1881412.1881445

Abstract

Cited By

Recommendations

Combinatorial PCPs with Efficient Verifiers