Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > EDEN FLORENTZ – KONOPNICKI:
All reports by Author Eden Florentz – Konopnicki:

TR24-149 | 24th September 2024
Noor Athamnah, Ron D. Rothblum, Eden Florentz – Konopnicki

Rate-1 Zero-Knowledge Proofs from One-Way Functions

We show that every NP relation that can be verified by a bounded-depth polynomial-sized circuit, or a bounded-space polynomial-time algorithm, has a computational zero-knowledge proof (with statistical soundness) with communication that is only additively larger than the witness length. Our construction relies only on the minimal assumption that one-way functions ... more >>>




ISSN 1433-8092 | Imprint