文章基本信息

标题：On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs
本地全文：下载
作者：Eli Ben-Sasson ; Alessandro Chiesa ; Daniel Genkin 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data. Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects a lack of understanding of how to study and improve the concrete (as opposed to asymptotic) efficiency of PCPs. We propose a new efficiency measure for PCPs (and its major component: locally-testable codes and PCPs of proximity). We define a concrete-efficiency threshold that indicates the smallest problem size beyond which the PCP becomes “useful”, in the sense that using it actually pays off relative to naive verification by simply rerunning the computation; our definition takes into account both the prover’s and verifier’s complexity. We then show that there exists a PCP with a finite concrete-efficiency threshold. This does not follow from existing works on PCPs with succinct verifiers. We provide a PCP construction where the prover and verifier are efficient enough to achieve a finite threshold, and further show that this PCP has the requisite properties for being used in the cryptographic applications mentioned above. Moreover, we extend and improve the Reed-Solomon PCPs of proximity over fields of characteristic 2, which constitute the main component in the quasilinear-size construction of [Ben-Sasson and Sudan, STOC ’05] as well as our construction. Our improvements reduce the concrete-efficiency threshold for testing proximity to Reed-Solomon codes from 2572 in their work to 235, which is tantalizingly close to practicality. We hope this will motivate the search for even better constructions, ultimately leading to practical PCPs for succinct verification of long computations.