New techniques for zero-knowledge: Leveraging inefficient provers to reduce assumptions, interaction, and trust

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 NC1. We also present NC1-fine-grained NIZK in the URS model for all of NP from the worst-case assumption (Formula Presented). Our techniques yield the following applications: 1.ZAPs for AM from Minicrypt assumptions (with super-polynomial time provers),2.NC1-fine-grained ZAPs for 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 NC1-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, Proceedings
EditorsDaniele Micciancio, Thomas Ristenpart
Number of pages30
ISBN (Print)9783030568764
StatePublished - 2020
Event40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States
Duration: Aug 17 2020Aug 21 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12172 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference40th Annual International Cryptology Conference, CRYPTO 2020
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'New techniques for zero-knowledge: Leveraging inefficient provers to reduce assumptions, interaction, and trust'. Together they form a unique fingerprint.

Cite this