Implementing Probabilistically Checkable Proofs of Proximity
Abstract: 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 \\cite{bs05}. In particular, we implement a PCPP prover and verifier for Reed-Solomon codes; the prover converts an evaluat...
| Main Author: | |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30562 |
| _version_ | 1811076681508585472 |
|---|---|
| author | Bhattacharyya, Arnab |
| author2 | Complexity Theory |
| author_facet | Complexity Theory Bhattacharyya, Arnab |
| author_sort | Bhattacharyya, Arnab |
| collection | MIT |
| description | Abstract: 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 \\cite{bs05}. In particular, we implement a PCPP prover and verifier for Reed-Solomon codes; the prover converts an evaluation of a polynomial on a linear set into a valid PCPP, while the verifier 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 verifier and describe some interesting programmatic issues that arise during their implementation. |
| first_indexed | 2024-09-23T10:25:53Z |
| id | mit-1721.1/30562 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:25:53Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305622019-04-12T08:26:07Z Implementing Probabilistically Checkable Proofs of Proximity Bhattacharyya, Arnab Complexity Theory Abstract: 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 \\cite{bs05}. In particular, we implement a PCPP prover and verifier for Reed-Solomon codes; the prover converts an evaluation of a polynomial on a linear set into a valid PCPP, while the verifier 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 verifier and describe some interesting programmatic issues that arise during their implementation. 2005-12-22T02:33:55Z 2005-12-22T02:33:55Z 2005-08-08 MIT-CSAIL-TR-2005-051 MIT-LCS-TR-998 http://hdl.handle.net/1721.1/30562 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 16 p. 13280259 bytes 636640 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Bhattacharyya, Arnab Implementing Probabilistically Checkable Proofs of Proximity |
| title | Implementing Probabilistically Checkable Proofs of Proximity |
| title_full | Implementing Probabilistically Checkable Proofs of Proximity |
| title_fullStr | Implementing Probabilistically Checkable Proofs of Proximity |
| title_full_unstemmed | Implementing Probabilistically Checkable Proofs of Proximity |
| title_short | Implementing Probabilistically Checkable Proofs of Proximity |
| title_sort | implementing probabilistically checkable proofs of proximity |
| url | http://hdl.handle.net/1721.1/30562 |
| work_keys_str_mv | AT bhattacharyyaarnab implementingprobabilisticallycheckableproofsofproximity |