A security analysis of Probabilistically Checkable Proofs
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 L 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 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 rowand 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 main results are: 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; rowand 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 [Ben Sasson et al. STOC '13] to 2. Using this measure of concrete efficiency threshold as our gauge, we reduce it further to 2 by applying security analysis; and finally reduce it to 2 for IOPP systems. An earlier version of this report appeared as Technical Report TR16 073 on the Electronic Colloquium on Computational Complexity [BBGR16] this report subsumes and replaces that version. Research supported by the Israel Science Foundation (grant 1501/14) and the US Israel Binational Science Foundation (grant 2021036)
Electron. Colloquium Comput. Complex.