Non-Interactive RAM and Batch NP Delegation from any PIR
Non-Interactive RAM and Batch NP Delegation from any PIR
复制标题
来自任何 PIR 的非交互式 RAM 和批量 NP 委派
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Y. Kalai
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Justin Holmgren;Y. Kalai
我们提出了一个自适应和非交互式的协议，用于在固定的多项式时间内验证任意有效的计算。我们的协议在计算上是合理的，可以基于任何计算PIR方案，这反过来又可以基于标准的多项式时间密码学假设（例如，最坏情况下的多项式因子近似的短向量晶格问题的硬度）。在我们的协议中，证明者和验证者根本不需要交互：验证者提前设置公钥，并且该密钥可以由任何证明者以完全自适应的方式来证明任意语句。验证是使用一个秘密的验证密钥来完成的，可靠性依赖于证明者不知道这个密钥。我们的协议还允许证明任意RAM机器的计算语句。以前的工作要么依赖于知识假设，要么只能提供非自适应的两个消息协议（其中第一个消息不能被重用），并需要基于混淆的假设或超多项式硬度假设。我们表明，我们的技术也可以应用于构建一种新型的（非自适应）2-消息委托协议批NP语句。具体来说，我们可以同时证明多个实例的成员在一个给定的NP语言，通信的复杂性成正比的长度一个单一的证人。魏茨曼科学研究所，zvika. brakerski@weizmann.ac.il。由以色列科学基金会（批准号468/14），阿隆青年教师奖学金，两国科学基金会（批准号712307）和谷歌教师研究奖支持。[2]麻省理工学院，holmgren@mit.edu。由NSF MACS项目CNS-1413920 Microsoft Research提供支持，yael@microsoft.com。
We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomialfactor approximation of short-vector lattice problems). In our protocol, the prover and the verifier do not need to interact at all: The verifier sets up a public key ahead of time, and this key can be used by any prover to prove arbitrary statements in a completely adaptive manner. Verification is done using a secret verification key, and soundness relies on this key not being known to the prover. Our protocol further allows to prove statements about computations of arbitrary RAM machines. Previous works either relied on knowledge assumptions, or could only offer non-adaptive two-message protocols (where the first message could not be re-used), and required either obfuscation-based assumptions or superpolynomial hardness assumptions. We show that our techniques can also be applied to construct a new type of (non-adaptive) 2-message delegation protocols for batch NP-statements. Specifically, we can simultaneously prove the membership of multiple instances in a given NP language, with communication complexity proportional to the length of a single witness. ∗Weizmann Institute of Science, zvika.brakerski@weizmann.ac.il. Supported by the Israel Science Foundation (Grant No. 468/14), the Alon Young Faculty Fellowship, Binational Science Foundation (Grant No. 712307) and Google Faculty Research Award. †MIT, holmgren@mit.edu. Supported by the NSF MACS project CNS-1413920 ‡Microsoft Research, yael@microsoft.com.