期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 N EX P , 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 [BCGT11], 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 [BCGT11], from its previous state of the art ( 2 43 ) there to 2 23 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 PCP constructions a bit closer to practice. Additional improvements are reported for input lengths in the range 2 23 --- 2 35 that we view as interesting in practice. 2. We initiate the study of the security of PCPP systems, in which soundness is measured only with respect to a set of known efficient (polynomial-time) ``pseudo-provers'', or ``attacks'', attempting to prove `` x C '' when x is far from C . As a first step in this direction we introduce a pair of natural attacks on the PCPP system of [BS08]; and show that for most inputs that are not codewords the soundness (i.e., rejection probability) of both attacks is significantly higher (better) than the new unconditional worst-case bounds reported above. We conjecture that the same should be true for any x far from the code, and pose this as an interesting open problem, with significance to the ``real-word practicality'' of PCPs. In particular, for attaining the same rejection probability against these attacks on most inputs x , the PCPP verifier need only read approximately a 2 − 8 -fraction of the amount of field elements he needs to read according to the result of item 1, while maintaining the same proof length. Consequently, the concrete efficiency threshold, when defined analogously in this setting, decreases from 2 23 to 2 17 .
