Revolutionizing Zero-Knowledge Proofs: Using Inefficient Provers to Minimize Assumptions 🔐

Dana Dachman-Soled (University of Maryalnd)
https://simons.berkeley.edu/talks/dana-dachman-soled-university-maryalnd-2023-05-01
Minimal Complexity Assumptions for Cryptography

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 a new application of Nisan-Wigderson designs, a combinatorial object originally introduced in the derandomization literature.
Our transformation implies ZAPs (with inefficient provers) from OWP (which is BB separated from KA) whereas previous ZAP constructions required assumptions that are known to imply the existence of public key encryption (and hence also imply KA).
We further observe that our transformation is also applicable in a new fine-grained setting, where the prover is polynomial time and the verifier/simulator/distinguisher are in a lower complexity class, such as NC^1.

Joint work with Marshall Ball and Mukul Kulkarni.