Delegating Computation
Delegating Computation
复制标题
DOI：
10.1145/2699436
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
S. Goldwasser;Y. Kalai;G. Rothblum
中科院分区：
文献类型：
--
作者：
S. Goldwasser;Y. Kalai;G. Rothblum
在这项工作中，我们研究了易处理语言的交互证明。(诚实的)证明者应该是高效的，并且在多项式时间内运行，或者，换句话说，是一个“麻瓜”。1.验证者应该是超级高效的，并且运行在近乎线性的时间内。这些证明系统可用于委托计算：服务器可以为客户端运行计算并交互地证明结果的正确性。客户端可以在近乎线性的时间内验证结果的正确性(而不是运行整个计算本身)。此前，Babai等人在全息证明设置中考虑了相关问题。[1991b]在Kilian的计算假设下的论证环境中，以及Micali的随机预言模型中[1994]。然而，我们的重点是原始的交互证明模型，其中没有对不诚实的证明者的计算能力或适应性做出任何假设。我们的主要技术定理给出了一个任意语言的公币交互证明，该证明可由一个深度为d、输入长度为n的对数空间一致布尔电路来计算。验证器在时间n·poly(d，log(N))和空间O(log(N))上运行，通信复杂度为poly(d，log(N))，证明器在时间poly(N)上运行。特别是，对于可由对数空间均匀NC(PolyLog(N)Depth)计算的语言，证明器是有效的，验证器运行时间为n·PolyLog(N)，空间为O(log(N))，通信复杂度为PolyLog(N)。利用这个定理，我们在几个问题上取得了进展。-我们展示了如何使用PolyLog通信为任何对数空间统一NC计算构造计算合理的1轮参数。该验证器在准线性时间内运行。这一结果使用了卡莱和拉兹最近从公开硬币互动证明到1轮论点的转变。论证系统的可靠性基于具有PolyLog通信的PIR方案的存在。-我们用公币构造了交互证明，给出了对数空间的多重时间验证器。这解决了一个悬而未决的问题，即具有这样的验证者的证明系统的表达能力。-基于单向函数的存在，对于NC中可验证的任意NP语言，我们构造了通信复杂性在见证长度上为拟线性的零知识交互证明。-对于在NC中可验证的任何NP语言，在计算假设下，我们构造了在见证长度(而不是实例长度)中大小为多项式的概率可检查论元(由Kalai和Raz提出的模型)。
In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time or, in other words, a “muggle”.1 The verifier should be super-efficient and run in nearly linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result’s correctness in nearly linear time (instead of running the entire computation itself). Previously, related questions were considered in the holographic proof setting by Babai et al. [1991b] in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali [1994]. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n. The verifier runs in time n · poly(d, log(n)) and space O(log(n)), the communication complexity is poly(d, log(n)), and the prover runs in time poly(n). In particular, for languages computable by log-space uniform NC (circuits of polylog(n) depth), the prover is efficient, the verifier runs in time n · polylog(n) and space O(log(n)), and the communication complexity is polylog(n). Using this theorem we make progress on several questions. --- We show how to construct 1-round computationally sound arguments with polylog communication for any log-space uniform NC computation. The verifier runs in quasi-linear time. This result uses a recent transformation of Kalai and Raz from public coin interactive proofs to 1-round arguments. The soundness of the argument system is based on the existence of a PIR scheme with polylog communication. --- We construct interactive proofs with public coin, log-space, poly-time verifiers for all of P are given. This settles an open question regarding the expressive power of proof systems with such verifiers. --- We construct zero-knowledge interactive proofs are given with communication complexity quasi-linear in the witness length for any NP language verifiable in NC, based on the existence of 1-way functions. --- We construct probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than instance length) for any NP language verifiable in NC, under computational assumptions, are provided.