Non-interactive delegation and batch NP verification from standard computational assumptions
Non-interactive delegation and batch NP verification from standard computational assumptions
复制标题
根据标准计算假设进行非交互式委托和批量 NP 验证
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Y. Kalai
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Justin Holmgren;Y. Kalai
我们提出了一种自适应和非相互作用协议，用于验证固定多项式时间内任意有效计算。我们的协议在计算上是合理的，可以基于任何计算PIR方案，这又可以基于标准的多项式加密假设（例如，短载体晶格问题的多项式因素近似值的最坏情况硬度）。在我们的协议中，验证者提前设置了公共密钥，并且任何供者可以通过简化向验证者发送证明来证明任意语句。验证是使用秘密验证密钥进行的，声音依赖于供者所知道的此密钥。我们的协议进一步允许证明有关任意RAM机器计算的陈述。以前的作品要么依赖于知识假设，要么只能提供非自适应的两种消息协议（第一个消息无法重复使用），并且需要基于混淆的假设或超级多项式硬度假设。我们表明，我们的技术也可以应用于构建一种新型的（非自适应）2-Message参数以构成批处理NP统计。具体而言，我们可以同时证明（计算声音）在给定的NP语言中多个实例的成员，并且与单个证人的长度成正比，交流复杂性。
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 polynomial-factor approximation of short-vector lattice problems). In our protocol, the verifier sets up a public key ahead of time, and this key can be used by any prover to prove arbitrary statements by simpling sending a proof to the verifier. 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 super-polynomial hardness assumptions. We show that our techniques can also be applied to construct a new type of (non-adaptive) 2-message argument for batch NP-statements. Specifically, we can simultaneously prove (with computational soundness) the membership of multiple instances in a given NP language, with communication complexity proportional to the length of a single witness.