A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. FOCS 90; Arora et al. JACM 98]; which in turn can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language $L\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 will perform in practice on concrete input sizes. This issue motivated the work of [Ben-Sasson et. al. STOC '13]. As in [BCGT11], to explore this question, we continue to investigate how well the PCPP for Reed-Solomon (RS) codes of [BS08] - the ``heavy'' component in the PCP construction of [BS08] - behaves for concrete input lengths. The crucial parameter to understand is the soundness of the PCPP, which is the probability an $x$ far from $C$ gets rejected.
The paper contains three contributions:
1. Improved soundness analysis of a new variant of the Reed-Solomon (RS) PCP of Proximity (PCPP) verifier of [BS08]. This verifier and its analysis reduce the concrete efficiency threshold of RS PCPPs, as defined by [BCGT11], from its previous state of the art ($2^{43}$) there to $2^{23}$ here. Informally, the concrete efficiency threshold is a measure that abstracts the ``smallest input length for which the PCPP is useful''; thus, reducing it will hopefully push PCP constructions a bit closer to practice. Additional improvements are reported for input lengths in the range $2^{23}$---$2^{35}$ that we view as interesting in practice.
2. We initiate the study of the security of PCPP systems, in which soundness is measured only with respect to a set of known efficient (polynomial-time) ``pseudo-provers'', or ``attacks'', attempting to prove ``$x\in C$'' when $x$ is far from $C$. As a first step in this direction we introduce a pair of natural attacks on the PCPP system of [BS08]; and show that for most inputs that are not codewords the soundness (i.e., rejection probability) of both attacks is significantly higher (better) than the new unconditional worst-case bounds reported above. We conjecture that the same should be true for any $x$ far from the code, and pose this as an interesting open problem, with significance to the ``real-word practicality'' of PCPs.
In particular, for attaining the same rejection probability against these attacks on most inputs $x$, the PCPP verifier need only read approximately a $2^{-8}$-fraction of the amount of field elements he needs to read according to the result of item 1, while maintaining the same proof length. Consequently, the concrete efficiency threshold, when defined analogously in this setting, decreases from $2^{23}$ to $2^{17}$.
3. To further reduce the concrete efficiency threshold we consider the Interactive Oracle Proofs of Proximity (IOPP) model [BCS16,RRR16,BCGRS16], in which [BCGRS16] show proof length can be significantly reduced with no loss in soundness, at the price of increased interaction.
We show that the IOPP model gives significant improvements for practical ranges of parameters. In particular, applying the security analysis above to this new interactive model, the resulting proof length is cut by a factor of approximately $8\times$ while verifier query complexity is cut down by a factor of approximately $2^{10}\times$ in comparison to item 1; and the analogous efficiency threshold goes down to $2^{14}$.
We hope this work will bring PCPs closer to practice and popularize the quest for better concrete PCP soundness within the theoretical computer science research community.
Extended analysis for random functions, new analysis for rational functions and PCP security.
A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. FOCS 90; Arora et al. JACM 98]; which in turn can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language $L\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 will perform in practice on concrete input sizes. This issue motivated the work of [Ben-Sasson et. al. STOC '13]. As in [BCGT11], to explore this question, we continue to investigate how well the PCPP for Reed-Solomon (RS) codes of [BS08] - the ``heavy'' component in the PCP construction of [BS08] - behaves for concrete input lengths. The crucial parameter to understand is the soundness of the PCPP, which is the probability an $x$ far from $C$ gets rejected.
The paper contains three contributions:
1. Improved soundness analysis of a new variant of the Reed-Solomon (RS) PCP of Proximity (PCPP) verifier of [BS08]. This verifier and its analysis reduce the concrete efficiency threshold of RS PCPPs, as defined by [BCGT11], from its previous state of the art ($2^{43}$) there to $2^{23}$ here. Informally, the concrete efficiency threshold is a measure that abstracts the ``smallest input length for which the PCPP is useful''; thus, reducing it will hopefully push PCP constructions a bit closer to practice. Additional improvements are reported for input lengths in the range $2^{23}$---$2^{35}$ that we view as interesting in practice.
2. We initiate the study of the security of PCPP systems, in which soundness is measured only with respect to a set of known efficient (polynomial-time) ``pseudo-provers'', or ``attacks'', attempting to prove ``$x\in C$'' when $x$ is far from $C$. As a first step in this direction we introduce a pair of natural attacks on the PCPP system of [BS08]; and show that for most inputs that are not codewords the soundness (i.e., rejection probability) of both attacks is significantly higher (better) than the new unconditional worst-case bounds reported above. We conjecture that the same should be true for any $x$ far from the code, and pose this as an interesting open problem, with significance to the ``real-word practicality'' of PCPs.
In particular, for attaining the same rejection probability against these attacks on most inputs $x$, the PCPP verifier need only read approximately a $2^{-8}$-fraction of the amount of field elements he needs to read according to the result of item 1, while maintaining the same proof length. Consequently, the concrete efficiency threshold, when defined analogously in this setting, decreases from $2^{23}$ to $2^{17}$.
3. To further reduce the concrete efficiency threshold we consider the Interactive Oracle Proofs of Proximity (IOPP) model [BCS16,RRR16,BCGRS16], in which [BCGRS16] show proof length can be significantly reduced with no loss in soundness, at the price of increased interaction.
We show that the IOPP model gives significant improvements for practical ranges of parameters. In particular, applying the security analysis above to this new interactive model, the resulting proof length is cut by a factor of approximately $8\times$ while verifier query complexity is cut down by a factor of approximately $2^{10}\times$ in comparison to item 1.
We hope this work will bring PCPs closer to practice and popularize the quest for better concrete PCP soundness within the theoretical computer science research community.
We significantly rewrote the results reported in this paper. It should be thus viewed as replaced and subsumed by TR16-149, titled "A security analysis of Probabilistically Checkable Proofs"
