Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
复制标题
DOI：
10.4230/lipics.itcs.2018.18
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Oded Goldreich;G. Rothblum
中科院分区：
文献类型：
--
作者：
Oded Goldreich;G. Rothblum
如果证明者的策略可以在多项式时间内实现，而验证者的策略可以在几乎线性时间内实现，则证明系统被称为双有效的。我们提出了直接建设的双重有效的互动证明系统的问题，在P被认为具有相对较高的复杂性。具体来说，这样的结构是为t-CLIQUE和t-SUM。此外，我们提出了一个通用的建设，这样的证明系统的自然类，包含这两个问题，是在NC（也在SC）。我们提出的证明系统比Goldwasser，Kalai和Rothblum（JACM，2015）提出的证明系统要简单得多，更不用说Reingold，Rothblum和Rothblum（STOC，2016）提出的证明系统了。
A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear-time. We present direct constructions of doubly-efficient interactive proof systems for problems in P that are believed to have relatively high complexity. Specifically, such constructions are presented for t-CLIQUE and t-SUM. In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC). The proof systems presented by us are significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016).