MIT-LCS-TR-998 Implementing Probabilistically Checkable Proofs of Proximity

In this paper, we describe a proof-of-concept implementation of the probabilistically checkable proof of proximity (PCPP) system described by Ben-Sasson and Sudan in [BSS05]. In particular, we implement a PCPP prover and verier for Reed-Solomon codes; the prover converts an evaluation of a polynomial on a linear set into a valid PCPP, while the verier queries the evaluation and the PCPP to check that the evaluation is close to a Reed-Solomon codeword. We prove tight bounds on the various parameters associated with the prover and verier and describe some interesting programmatic issues that arise during their implementation.