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

Add to your list(s) Download to your calendar using vCal

• Noor Athamnah (Technion)
• Friday 18 October 2024, 13:30-14:30
• Computer Laboratory, William Gates Building, FW26.

If you have a question about this talk, please contact Tom Gur.

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 $|w|poly(\lambda,\log(|x|))$ and relations that can be verified in SC have a zero-knowledge 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 fan-in XOR , AND and OR gates), has a zero-knowledge 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 bounded-space 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 black-box use of the one-way function, but in this case we achieve only an inverse polynomial soundness error.

• Based on joint work with Eden Florentz – Konopnicki and Ron Rothblum.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, FW26
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.