Paper 2024/1493
Rate-1 Zero-Knowledge Proofs from One-Way Functions
Abstract
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 exist.
In more detail, assuming one-way functions, we show that every NP relation that can be verified in NC has a zero-knowledge proof with communication
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint.
- Keywords
- zero knowledge proofs
- Contact author(s)
-
noor athamnah @ gmail com
edenko @ campus technion ac il
rothblum @ cs technion ac il - History
- 2024-09-30: approved
- 2024-09-24: received
- See all versions
- Short URL
- https://ia.cr/2024/1493
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1493, author = {Noor Athamnah and Eden Florentz – Konopnicki and Ron D. Rothblum}, title = {Rate-1 Zero-Knowledge Proofs from One-Way Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1493}, year = {2024}, url = {https://eprint.iacr.org/2024/1493} }