Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs
Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs
复制标题
DOI：
10.1007/s00145-014-9184-y
复制
发表时间：
2015-10-01
影响因子：
3
通讯作者：
Smith, Adam
中科院分区：
文献类型：
--
作者：
Gentry, Craig;Groth, Jens;Smith, Adam
非交互式的零知识（NIZK）证明可以用来证明陈述的真相，而无需透露其他任何内容。已在标准的加密假设下表明，NP中所有语言都存在NIZK会员资格证明。尽管有证据表明，这种证据不能比相应的成员证人短得多，但所有已知的NIZK语言证明都比证人更长。在绅士建造完全同态加密后不久，几个小组独立考虑使用混合加密来优化NIZK证明的规模，并在加密社区中讨论了这一想法。本文正式探讨了使用完全同型混合加密来优化NIZK证明和其他相关加密原始原始原始图的想法。我们调查了最小化NP的Nizk证明沟通开销的问题，并表明，如果存在完全同质的加密，则可以获得与证人大小相同的证据。我们的技术包括构建具有密文大小的完全同型混合加密方案，在哪里是纯文本，是安全参数。对证人进行加密为NP统计，使我们能够以沟通效率的方式评估NP关系。我们将此技术应用于标准的非相互作用零知识证明，并将其应用于普遍综合的非相互作用的零知识证明。该技术也可以在非相互互动零知识证明的领域之外应用，例如，在普通模型中获得证人大小的交互式零知识证明，而无需任何设置或最大程度地减少安全计算协议中的通信。
A non-interactive zero-knowledge (NIZK) proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that NIZK proofs of membership exist for all languages in NP. While there is evidence that such proofs cannot be much shorter than the corresponding membership witnesses, all known NIZK proofs for NP languages are considerably longer than the witnesses. Soon after Gentry's construction of fully homomorphic encryption, several groups independently contemplated the use of hybrid encryption to optimize the size of NIZK proofs and discussed this idea within the cryptographic community. This article formally explores this idea of using fully homomorphic hybrid encryption to optimize NIZK proofs and other related cryptographic primitives. We investigate the question of minimizing the communication overhead of NIZK proofs for NP and show that if fully homomorphic encryption exists then it is possible to get proofs that are roughly of the same size as the witnesses. Our technique consists in constructing a fully homomorphic hybrid encryption scheme with ciphertext size , where is the plaintext and is the security parameter. Encrypting the witness for an NP-statement allows us to evaluate the NP-relation in a communication-efficient manner. We apply this technique to both standard non-interactive zero-knowledge proofs and to universally composable non-interactive zero-knowledge proofs. The technique can also be applied outside the realm of non-interactive zero-knowledge proofs, for instance to get witness-size interactive zero-knowledge proofs in the plain model without any setup or to minimize the communication in secure computation protocols.