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

===========================

https://umd.zoom.us/j/97585901703

Meeting ID: 975 8590 1703