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

Explore new techniques for zero-knowledge proofs in this 38-minute lecture by Dana Dachman-Soled from the University of Maryland. Delve into a transformation from Non-Interactive Zero-Knowledge (NIZK) with inefficient provers in the Uniform Random String (URS) model to ZAPs (two-message witness indistinguishable proofs) with inefficient provers. Discover how this transformation, achieved through a novel application of Nisan-Wigderson designs, differs from previous approaches for efficient provers. Learn about the implications of this work, including the construction of ZAPs from One-Way Permutations (OWP), which is black-box separated from Key Agreement (KA). Examine the applicability of this transformation in a fine-grained setting, where the prover operates in polynomial time while the verifier, simulator, and distinguisher are in lower complexity classes like NC^1. Gain insights into ongoing research in cryptography and minimal complexity assumptions, presented as part of the Simons Institute's "Minimal Complexity Assumptions for Cryptography" series.