BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Rate-1 Zero-Knowledge Proofs from One-Way Functions - Noor Athamna
 h (Technion)
DTSTART:20241018T123000Z
DTEND:20241018T133000Z
UID:TALK223078@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We show that every NP relation that can be verified by a bound
 ed-depth polynomial-sized circuit\, or a bounded-space polynomial-time alg
 orithm\, has a computational zero-knowledge proof (with statistical soundn
 ess) with communication that is only additively larger than the witness le
 ngth. Our construction relies only on the minimal assumption that one-way 
 functions exist. In more detail\, assuming one-way functions\, we show tha
 t 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 sm
 all 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-knowl
 edge proof with communication $S+poly(\\lambda\,\\log(S))$.\n\nOur result 
 improves on a recent result of Nassar and Rothblum (Crypto\, 2022)\, which
  achieve length $(1+\\epsilon) \\cdot |w|+|x|^\\epsilon \\cdot poly(\\lamb
 da)$ for bounded-space computations\, and is also considerably simpler. Bu
 ilding on a work of Hazay et al. (TCC 2023)\, we also give a more complica
 ted version of our result in which the parties only make a black-box use o
 f the one-way function\, but in this case we achieve only an inverse polyn
 omial soundness error.\n\n* Based on joint work with Eden Florentz – Kon
 opnicki and Ron Rothblum.
LOCATION:Computer Laboratory\, William Gates Building\, FW26
END:VEVENT
END:VCALENDAR