New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
summary
Transformation shows that a NIZK in the uniform random string model with provers running in time T yields a ZAP where provers run in time poly(n)·T, enabling ZAPs with subexponential provers from one-way permutations. construction uses Nisan-Wigderson designs to make per-block dependencies only pairwise and pushes heavy work into a nonuniform pre-processing stage; soundness needs universe size l ≪ n′ and witness indistinguishability reduces to the NIZK simulator, so the approach concretely works and avoids extra assumptions like public-key encryption.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:45The Landscape of NIZK for NP
- 8:16A Generic Way to Construct ZAPS
- 14:01Roadmap
- 14:48Transformation of NIZK to ZAP Dwork, Naor
- 19:12Transformation of NIZK to ZAP-WI Problem with inefficient honest provers
- 22:43Main Tool: Nisan-Wigderson Designs
- 33:43Applying Our Transformation in the Fir Grained Setting
- 34:53Future Directions
related talks
49mLattice-Based Zero Knowledge and Applications
33mAn Introduction to Zero Knowledge Proofs
33mA New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
01h 06mLattice-based Zero-knowledge Proofs
19mDIZK: A Distributed Zero Knowledge Proof System
33mHow to Share an NP Statement or Combiners for Zero-Knowledge Proofs
29mKolmogorov Complexity Characterizes Statistical Zero Knowledge
26mPractical, Efficient ZKPs, Economic and Social Processes