On the concrete efficiency of probabilistically-checkable proofs
On the concrete efficiency of probabilistically-checkable proofs
复制标题
关于概率可检验证明的具体效率
DOI：
10.1145/2488608.2488681
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Eran Tromer
中科院分区：
文献类型：
--
作者：
Eli Ben;A. Chiesa;Daniel Genkin;Eran Tromer
概率可检查的证明（PCP）形成了算法核心，该核心可以在许多加密结构中快速验证长期计算。然而，尽管他们带来了奇妙的渐近节省，但PCP还是臭名昭著的计算瓶颈，阻止了这些强大的加密结构在实践中使用。为了解决这个问题，我们提供了有关PCP的计算效率的几个结果。我们构建了第一个PCP，其中谚语和验证者时间复杂性是准最佳选择的（即，最佳延伸至多形因子因子）。谚语和验证者也是可行的，即使在证明和验证随机访问机器计算的正确性时，这些计算保证也可以保证。我们的构造是明确的，并且具有上述加密应用程序中使用的必要属性。
接下来，为了更好地了解PCP的效率，我们提出了针对PCP的新效率度量（及其主要组件，可当地测试的代码和接近性的PCP）。我们定义了一个具体效率阈值，该阈值表明PCP变得“有用”的最小问题大小，从某种意义上说，使用它比执行幼稚验证（即重新计算）；我们的定义既说明了谚语和验证者的复杂性。
然后，我们证明我们的PCP具有有限的混凝土效率阈值。这种PCP的存在并不遵循带有Polygarithmic-time验证符的PCP上的现有作品。
就像在[Ben-Sasson和Sudan，STOC '05]中一样，Reed-Solomon（RS）代码的接近PCP是我们PCP的主要组成部分。我们构建了一个近距离的PCP，该PCP将与RS代码接近的具体效率阈值从2683的工作中降低到243，这是诱人的实用性。
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 2683 in their work to 243, which is tantalizingly close to practicality.