International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Marshall Ball , Columbia University
Dana Dachman-Soled , University of Maryland
Mukul Kulkarni , UMass Amherst
Download:
DOI: http://dx.doi.org/10.1007/978-3-030-56877-1_24 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2020
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 NP from the worst-case assumption $\oplus L/\poly \not\subseteq \mathsf{NC}^1$. Our techniques yield the following applications: --ZAPs for $\mathsf{AM}$ from Minicrypt assumptions (with super-polynomial time provers), --$\mathsf{NC}^1$-fine-grained ZAPs for $\mathsf{NP}$ from worst-case assumptions, --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.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30469,
  title={New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust},
  publisher={Springer-Verlag},
  doi={http://dx.doi.org/10.1007/978-3-030-56877-1_24},
  author={Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni},
  year=2020
}