Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables fast verification of long computations in many cryptographic constructions. Yet, despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these powerful cryptographic constructions from being used in practice. To address this problem, we present several results about the computational efficiency of PCPs.

We construct the first PCP where the prover and verifier time complexities are quasi-optimal (i.e., optimal up to poly-logarithmic factors). The prover and verifier are also higly-parallelizable, and these computational guarantees hold even when proving and verifying the correctness of random-access machine computations. Our construction is explicit and has the requisite properties for being used in the cryptographic applications mentioned above.

Next, to better understand the efficiency of our PCP, we propose a new efficiency measure for PCPs (and their major components, 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 is cheaper than performing naive verification (i.e., rerunning the computation); our definition accounts for both the prover and verifier complexity.

We then show that our PCP has a finite concrete-efficiency threshold. That such a PCP exists does not follow from existing works on PCPs with polylogarithmic-time verifiers.

As in [Ben-Sasson and Sudan, STOC ’05], PCPs of proximity for Reed–Solomon (RS) codes are the main component of our PCP. We construct a PCP of proximity that reduces the concrete-efficiency threshold for testing proximity to RS codes from $2^{683}$ in their work to $2^{43}$, which is tantalizingly close to practicality.

Revisions in the introductory sections. Also, in previous versions, we claimed threshold computations that were smaller for both [BSS08] and our construction, since we computed the threshold by dividing by the block length n(k) instead of the dimension k; this has been corrected.

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 \emph{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 \emph{both} the prover's and verifier's complexity.

We then show that there exists a PCP with a \emph{finite} concrete-efficiency threshold. This does not follow from existing works on PCPs with succinct verifiers. We provide an explicit 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. Our construction in fact also yields a PCP system for random-access machines where the (asymptotic) time complexity of both the prover and verifier are \emph{essentially optimal} and where both prover and verifier are \emph{highly-parallelizable}.

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 $2^{572}$ in their work to $2^{35}$, 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.

Thorough revisions for clarity and consistency in the technical sections.

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 $2^{572}$ in their work to $2^{35}$, 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.

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 $2^{572}$ in their work to $2^{35}$, 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.