Welcome to the resource topic for 2019/1464
Title:
New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions and Interaction
Authors: Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni
Abstract:We present a transformation from NIZK with inefficient provers in the uniform random string (URS) model to ZAPs (two message witness indistinguishable proofs) with inefficient 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-Wigderson designs, 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 \mathsf{NC}^1. We also present \mathsf{NC}^1-fine-grained NIZK in the URS model for all of \mathsf{NP} from the worst-case assumption \oplus L/\mathsf{\poly} \not\subseteq \mathsf{NC}^1. Our techniques yield the following applications: 1. ZAPs for \mathsf{AM} from Minicrypt assumptions (with super-polynomial time provers), 2. \mathsf{NC}^1-fine-grained ZAPs for \mathsf{NP} from 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 \mathsf{NC}^1-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.
ePrint: https://eprint.iacr.org/2019/1464
Talk: https://www.youtube.com/watch?v=ch4JJKTBUF0
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .