Paper 2024/1493
Rate1 ZeroKnowledge Proofs from OneWay Functions
Abstract
We show that every NP relation that can be verified by a boundeddepth polynomialsized circuit, or a boundedspace polynomialtime algorithm, has a computational zeroknowledge proof (with statistical soundness) with communication that is only additively larger than the witness length. Our construction relies only on the minimal assumption that oneway functions exist. In more detail, assuming oneway functions, we show that every NP relation that can be verified in NC has a zeroknowledge proof with communication $w+poly(\lambda,\log(x))$ and relations that can be verified in SC have a zeroknowledge proof with communication $w+x^\epsilon \cdot poly(\lambda)$. Here $\epsilon>0$ is an arbitrarily small constant and \lambda denotes the security parameter. As an immediate corollary, we also get that any NP relation, with a size S verification circuit (using unbounded fanin XOR, AND and OR gates), has a zeroknowledge proof with communication $S+poly(\lambda,\log(S))$. Our result improves on a recent result of Nassar and Rothblum (Crypto, 2022), which achieve length $(1+\epsilon) \cdot w+x^\epsilon \cdot poly(\lambda)$ for boundedspace computations, and is also considerably simpler. Building on a work of Hazay et al. (TCC 2023), we also give a more complicated version of our result in which the parties only make a blackbox use of the oneway function, but in this case we achieve only an inverse polynomial soundness error.
Metadata
 Available format(s)
 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
 20240930: approved
 20240924: 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 = {Rate1 ZeroKnowledge Proofs from OneWay Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1493}, year = {2024}, url = {https://eprint.iacr.org/2024/1493} }