log in  |  register  |  feedback?  |  help  |  web accessibility
Constant-Round Zero-Knowledge for NP: the Goldreich-Kahan protocol
Thursday, March 31, 2022, 3:00-4:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

In 1996, Goldreich and Kahan published a paper introducing the first constant-round zero-knowledge proof system for NP. In this talk, I'll use their protocol as a case study for simulation-based proofs by going over their proof of zero-knowledge. As we'll see, although the intuition is straightforward, the constant number of rounds introduces some subtleties when determining the expected runtime of the simulator. I'll talk about how these issues are addressed (spoiler: negligible functions cannot always be neglected).

See https://link.springer.com/content/pdf/10.1007/BF00208001.pdf and §5.4 of https://eprint.iacr.org/2016/046 and



Meeting ID: 975 8590 1703


This talk is organized by David Miller