Zero-Knowledge in Streaming Interactive Proofs

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

• Tomer Gewirtzman (Technion)
• Tuesday 25 February 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

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

In a recent work, Cormode, Dall’Agnol, Gur and Hickey (CCC, 2024) introduced the model of Zero-Knowledge Streaming Interactive Proofs (zkSIPs). Loosely speaking, such proof-systems enable a prover to convince a streaming verifier that the input x, to which it has read-once streaming access, satisfies some property, in such a way that nothing beyond the correctness of the claim is revealed. Cormode et al. also gave constructions of zkSIPs to some specific and notable problems of interest. In this work, we advance the study of zero-knowledge proofs in the streaming model, by presenting protocols that are significantly more general and more secure. We use a definition of zero-knowledge that is a variation of that used by Cormode et al., which we find more appealing but is technically incomparable. Our main result is a zkSIP for any NP relation, that can be decided by low-depth polynomial-size circuits. We emphasize that this is the first general purpose protocol in this model, which captures, as a special case, the problems considered by the prior work. We also construct a specialized protocol for the ``polynomial evaluation’’ problem considered in that work, with improved parameters. The protocols constructed by Cormode et al. have an inverse polylogarithmic simulation error (i.e., a gap with which a bounded-space distingiusher can distinguish the simulation from a real execution). This means that their protocols are entirely insecure if run multiple times (say on different inputs). In contrast, our protocols achieve a negligible zero-knowledge error, a stronger and far more robust security guarantee.

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, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.