Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits
Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits
复制标题
多证明者交互式证明的简洁论证及其效率优势
DOI：
10.1007/978-3-642-32009-5_16
复制
发表时间：
2012
影响因子：
3
通讯作者：
A. Chiesa
中科院分区：
文献类型：
--
作者：
Nir Bitansky;A. Chiesa
知识的简洁论点是NP的计算中知识证明，其中验证者的运行时间独立于NP非确定机器的时间复杂性。
现有的简洁参数结构通常是基于结合加密散布散布和概率检查PCP的技术的技术，因此鉴于当今最先进的PCP技术，效率很低：要么将长期PCP证明与长期证明一起使用大量的冗余以使验证者快速，但要使供供者放慢速度，或者使用简短的PCP证明来使卖者快速，但以制作验证器为代价 慢的。
为了获得提高效率，我们建议研究基于多能互动证明MIP和更强的加密技术来构建简洁参数的替代方法：
1我们构建了一个单轮知识协议的简洁MIP，我在时间和空间方面效率很高，而II也是验证者高效的。
2我们展示了如何使用单个供奉献者将任何一个圆形MIP协议转换为简洁的四元参数，同时保留原始MIP协议的时间和空间效率。
作为这种转换的主要工具，我们构建了一个简洁的多功能承诺，A允许发件人在时代和空间复杂性的功能向量上承诺与对功能进行单个评估所需的功能相同，并且b确保接收器的运行时间本质上与功能无关。该方案基于完全塑形的加密，我们简洁的论点不需要其他假设。
3此外，我们重新审视了知识snark的非交互式简洁参数的问题，其中已知的不可能是基于基于黑箱减少标准假设的解决方案。我们制定了具有同态甲状化特性的同态加密的天然但非标准的变体。然后，我们证明他的原始性基本上允许“挤压”我们的互动协议，同时再次保留了时间和空间效率。我们进一步表明，这种变体实际上是由于蛇的存在所暗示的。
Succinct arguments of knowledge are computationally-sound proofs of knowledge for NP where the verifier's running time is independent of the time complexity of the NP nondeterministic machine for the considered language.
Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs PCPs, and thus, in light of today's state-of-the-art PCP technology, are quite inefficient: either one uses long PCP proofs with lots of redundancy to make the verifier fast but at the cost of making the prover slow, or one uses short PCP proofs to make the prover fast but at the cost of making the verifier slow.
To obtain better efficiency, we propose to investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs MIPs and stronger cryptographic techniques:
1 We construct a one-round succinct MIP of knowledge protocol where i each prover is highly efficient in terms of time AND space, and ALSO ii the verifier is highly efficient.
2 We show how to transform any one round MIP protocol to a succinct four-message argument with a single prover, while preserving the time and space efficiency of the original MIP protocol.
As a main tool for this transformation, we construct a succinct multi-function commitment that a allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and b ensures that the receiver's running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption and no additional assumptions are needed for our succinct argument.
3 In addition, we revisit the problem of non-interactive succinct arguments of knowledge SNARKs, where known impossibilities rule out solutions based on black-box reductions to standard assumptions. We formulate a natural though non-standard variant of homomorphic encryption that has a homomorphism-extraction property. We then show that his primitive essentially allows to "squash" our interactive protocol, while again preserving time and space efficiency. We further show that this variant is, in fact, implied by the existence of SNARKs.