On the concrete efficiency of probabilistically-checkable proofs

ABSTRACT

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables fast verification of long computations in many cryptographic constructions. Yet, despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these powerful cryptographic constructions from being used in practice. To address this problem, we present several results about the computational efficiency of PCPs. We construct the first PCP where the prover and verifier time complexities are quasi-optimal (i.e., optimal up to poly-logarithmic factors). The prover and verifier are also higly-parallelizable, and these computational guarantees hold even when proving and verifying the correctness of random-access machine computations. Our construction is explicit and has the requisite properties for being used in the cryptographic applications mentioned above.

Next, to better understand the efficiency of our PCP, we propose a new efficiency measure for PCPs (and their major components, locally-testable codes and PCPs of proximity). We define a concrete-efficiency threshold that indicates the smallest problem size beyond which the PCP becomes "useful", in the sense that using it is cheaper than performing naive verification (i.e., rerunning the computation); our definition accounts for both the prover and verifier complexity.

We then show that our PCP has a finite concrete-efficiency threshold. That such a PCP exists does not follow from existing works on PCPs with polylogarithmic-time verifiers.

As in [Ben-Sasson and Sudan, STOC '05], PCPs of proximity for Reed-Solomon (RS) codes are the main component of our PCP. We construct a PCP of proximity that reduces the concrete-efficiency threshold for testing proximity to RS codes from 2⁶⁸³ in their work to 2⁴³, which is tantalizingly close to practicality.

References

1. B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. ICALP '10.
2. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. JACM, 1998.
3. S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. JACM, 1998.
4. L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. STOC '91.
5. B. Barak and O. Goldreich. Universal arguments and their applications. SIAM JC, 2008.
6. E. Ben-Sasson, A. Chiesa, D. Genkin, and E. Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. ITCS '13.
7. E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. Robust PCPs of proximity, shorter PCPs and applications to coding. STOC '04.
8. E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. Short PCPs verifiable in polylogarithmic time. CCC '05.
9. E. Ben-Sasson, P. Harsha, and S. Raskhodnikova. Some 3CNF properties are hard to test. SIAM JC, 2005.
10. E. Ben-Sasson and M. Sudan. Short PCPs with polylog query complexity. SIAM JC, 2008.
11. E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson. Randomness-efficient low degree tests and short pcps via epsilon-biased sets. STOC '03.
12. E. R. Berlekamp. Algebraic Coding Theory. 1968.
13. N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. ITCS '12, 2012.
14. N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. STOC '13, 2013.
15. N. Bitansky and A. Chiesa. Succinct arguments from multi-prover interactive proofs and their efficiency benefits. CRYPTO '12.
16. D. Boneh, G. Segev, and B. Waters. Targeted malleability. ITCS '12.
17. A. Chiesa and E. Tromer. Proof-carrying data and hearsay arguments from signature cards. ICS '10.
18. A. Chiesa and E. Tromer. Proof-carrying data: Secure computation on untrusted platforms. The Next Wave: The NSA's review of emerging technologies, 2012.
19. K.-M. Chung, Y. Kalai, and S. Vadhan. Improved delegation of computation using fully homomorphic encryption. CRYPTO '10.
20. I. Damgård, S. Faust, and C. Hazay. Secure two-party computation with low communication. TCC '12.
21. G. Di Crescenzo and H. Lipmaa. Succinct NP proofs from an extractability assumption. CiE '08.
22. I. Dinur. The PCP theorem by gap amplification. JACM, 2007.
23. U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. JACM, 1996.
24. R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. CRYPTO '10.
25. O. Goldreich and M. Sudan. Locally testable codes and pcps of almost-linear length. JACM, 2006.
26. S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegating computation: interactive proofs for muggles. In STOC '08.
27. S. Goldwasser, H. Lin, and A. Rubinstein. Delegation of computation without rejection problem from designated verifier CS-proofs. ePrint, 2011.
28. P. Harsha and M. Sudan. Small PCPs with low query complexity. Comp. Compl., 2000.
29. W. C. Huffman and R. A. Brualdi. Handbook of Coding Theory. Elsevier Science Inc., New York, NY, USA, 1998.
30. Y. Ishai, E. Kushilevitz, and R. Ostrovsky. Efficient arguments without short PCPs. CCC '07.
31. J. Kilian. A note on efficient zero-knowledge proofs and arguments. STOC '92.
32. R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 2nd edition, 1997.
33. R. J. Lipton. Galactic algorithms. http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/, 2010.
34. T. Mateer. Fast Fourier Transform algorithms with applications. PhD thesis, Clemson University, 2008.
35. O. Meir. Combinatorial PCPs with efficient verifiers. FOCS '09.
36. O. Meir. Combinatorial pcps with short proofs. CCC '12.
37. S. Micali. Computationally sound proofs. SIAM JC, 2000.
38. T. Mie. Polylogarithmic two-round argument systems. J. Math. Crypt., 2008.
39. T. Mie. Short PCPPs verifiable in polylogarithmic time with o(1) queries. A. Math. and AI, 2009.
40. D. Moshkovitz and R. Raz. Two-query PCP with subconstant error. JACM, 2008.
41. A. Polishchuk and D. A. Spielman. Nearly-linear size holographic proofs. STOC '94.
42. R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. STOC '97.
43. S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish. Taking proof-based verified computation a few steps closer to practicality. Security '12.
44. D. Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, MIT, Mathamatics Department, May 1995.
45. P. Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. TCC '08.

Index Terms

• Theory of computation