Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC 91; Kilian STOC `92; Micali SICOMP `00]. Though PCP constructions are asymptotically efficient, it is still far from clear how well they perform in practice on concrete input sizes. One of the most important parameters to study in this context is PCP soundness, defined as the probability of rejecting false statements; this parameter determines to a large extent the communication complexity of PCP based protocols, as well as prover and verifier running time. Of particular importance is studying soundness for concrete, non-asymptotic, input sizes. This underlies the definition of the concrete efficiency threshold of PCP (and related systems) [Ben-Sasson et al. STOC '13], defined informally as the smallest instance size for which using a PCP verifier is more efficient than naive verification via re-execution.
To further advance the study of concrete PCP efficiency we initiate a security analysis of PCPs and two related systems: PCPs of Proximity (PCPP) [Dinur and Reingold, FOCS 2004; Ben-Sasson et al., SICOMP 2006] and Interactive Oracle Proofs of Proximity (IOPP) [Reingold et al., STOC 2016; Ben-Sasson et al., TCC-A+B 2016]. Security analysis means measuring soundness only with respect to the set of known attacks; an attack is a randomized efficient algorithm that produces a pseudo-proof for false statements. In the context of proximity testing (PCPP/IOPP), an attack receives as input a specification of an error correcting code $C$ and a word $w$ that is very far from $C$ and outputs a pseudo-proof of proximity for the (false) statement "$w \in C$".
To jumpstart security analysis one needs a set of attacks. We define one non-trivial attack, called the rational attack, on the quasilinear PCP of [Ben-Sasson and Sudan, SICOMP 2008], and two basic attacks --- row- and column-compliant attacks --- on the specific PCPP system for Reed-Solomon codes (RS-PCPP) that underlies that PCP as well as mixed strategies combining the two attacks. Our two main results are:
A) Rational attacks force the attacker to prove proximity of a rational function (like $1/x$) to low-degree polynomials. Rational functions are maximally far from low-degree so this suggests that PCP security may be significantly higher than soundness;
B) row- and column-compliant attacks on rational functions have very large security (i.e., large probability of being rejected by the verifier); the same holds for most (random) functions. This gives additional (preliminary) support to the view that PCPP security may be higher than predicted by soundness.
We also give an improved unconditional soundness analysis for the
aforementioned RS-PCPP, reducing its concrete efficiency threshold from the previous state of the art of $2^{43}$ Threshold [Ben-Sasson et al., STOC `13] to $2^{23}$. Using this measure of concrete efficiency threshold as our gauge, we reduce it further to $2^{19}$ by applying security analysis; and finally reduce it to $2^{14}$ for IOPP systems.
This paper is a significant revision of the results of TR16-073, and thus replaces and subsumes that paper.
