Obfuscation-Based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NP
Obfuscation-Based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NP
复制标题
DOI：
10.1007/978-3-662-46497-7_25
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
Omkant Pandey;M. Prabhakaran;A. Sahai
中科院分区：
文献类型：
--
作者：
Omkant Pandey;M. Prabhakaran;A. Sahai
我们展示了以下结果：假设所有多项式时间图灵机类都存在公共币差异输入混淆（pc-diO），那么对于NP中的所有语言都存在一个四消息、完全并发的零知识证明系统，可靠性误差可以忽略不计。这一结果具有建设性：给定（pc-diO），我们的约简产生了一个显式协议沿着一个显式模拟器，该模拟器是“直线”并在严格的多项式时间内运行。混淆安全属性仅用于证明可靠性。公共硬币差异输入混淆是与不可识别性混淆密切相关的混淆概念。对于我们的结果最重要的是，（pc-diO）不受任何已知的不可能结果的影响：最近关于标准差分输入混淆的负面结果不适用于（pc-diO）。此外，所有多项式时间图灵机类的（pc-diO）的候选结构是已知的。我们的减少依赖于一个新的非黑盒模拟技术，不使用PCP定理。我们认为这种新的非黑盒模拟技术的发展是我们工作的主要贡献。除了假设（pc-diO），我们的简化还假设（标准和多项式时间）密码学假设，如抗碰撞哈希函数。
We show the following result: Assuming the existence of public-coin differing-input obfuscation(pc-diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages inNPwith negligible soundness error. This result is constructive: given (pc-diO), our reduction yields an explicit protocol along with anexplicitsimulator that is “straight line” and runs in strict polynomial time. The obfuscation security property is used only to prove soundness.Public-coin differing-inputs obfuscation is a notion of obfuscation closely related to indistinguishability obfuscation. Most importantly for our result, (pc-diO) does not suffer from any known impossibility results: recent negative results on standard differing-inputs obfuscation do not apply to (pc-diO). Furthermore, candidate constructions for (pc-diO) for the class of all polynomial-time Turing Machines are known.Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. We view the development of this new non-black-box simulation technique as the main contribution of our work. In addition to assuming (pc-diO), our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions.