Paper 2019/1464

New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions and Interaction

Marshall Ball, Dana Dachman-Soled, and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in Crypto 2020
Keywords
Zero-KnowledgeNIZKZAPNIWIfine-grainedinefficient proverminicryptderandomization
Contact author(s)
marshall @ cs columbia edu
History
2020-06-16: last of 2 revisions
2019-12-18: received
See all versions
Short URL
https://ia.cr/2019/1464
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1464,
      author = {Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni},
      title = {New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions and Interaction},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1464},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1464}},
      url = {https://eprint.iacr.org/2019/1464}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.