New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust
New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust
复制标题
DOI：
10.1007/978-3-030-56877-1_24
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Marshall Ball;Dana Dachman-Soled;Mukul Kulkarni
中科院分区：
文献类型：
--
作者：
Marshall Ball;Dana Dachman-Soled;Mukul Kulkarni
我们提出了一种从具有无效率证明的统一随机字符串（URS）模型的NIZK到具有无效率证明者的ZAPs（两个消息见证不可区分证明）的转换。虽然这种转换在证明者是高效的情况下是已知的，但如果证明者是低效的，安全证明就会失效。我们的变换是通过Nisan-Wigdersondesigns的新应用获得的，Nisan-Wigdersondesigns是一个组合对象，最初是在非随机化文献中引入的。我们观察到，我们的转换既适用于超多项式证明者/多时间对手的设置，也适用于新的细粒度设置，其中证明者是多项式时间，验证者/模拟器/零知识区分者处于较低的复杂性类别，例如。我们还在URS模型中给出了所有最坏情况假设的细粒度NIZK。我们的技术产生以下应用：从Minicrypt假设（具有超多项式时间证明），2。-最坏情况下的细粒度zap；在标准（无crs）模型中实现“离线”NIZK （oNIZK）概念的协议，在超多项式设置（来自Minicrypt假设）和细粒度设置（来自最坏情况假设）中都具有统一的可靠性。oNIZK概念足以用于基于不可区分性的证明。
We present a transformation from NIZK withinefficient proversin the uniform random string (URS) model to ZAPs (two message witness indistinguishable proofs) withinefficient provers. While such a transformation was known for the case where the prover is efficient, the security proof breaks down if the prover is inefficient. Our transformation is obtained via new applications of Nisan-Wigdersondesigns, a combinatorial object originally introduced in the derandomization literature.We observe that our transformation is applicable both in the setting of super-polynomial provers/poly-time adversaries, as well as a new fine-grained setting, where the prover is polynomial time and the verifier/simulator/zero knowledge distinguisher are in a lower complexity class, such as. We also present-fine-grained NIZK in the URS model for all offrom the worst-case assumption.Our techniques yield the following applications:1.ZAPs forfrom Minicrypt assumptions (with super-polynomial time provers),2.-fine-grained ZAPs forfrom worst-case assumptions,3.Protocols achieving an “offline” notion of NIZK (oNIZK) in the standard (no-CRS) model with uniform soundness in both the super-polynomial setting (from Minicrypt assumptions) and the-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.