View article

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∈ 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 [BCGT13], 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 [BCGT13], from its previous state of the art (243) there to 223 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 …