CS276 Lecture 26: Quadratic Residuosity and Proofs of Knowledge

Scribed by Anindya De


In this lecture, we show that the protocol for quadratic residuosity discussed last week is indeed zero-knowledge. Next we move on to the formal definition of proof of knowledge, and we show that the quadratic residuosity protocol is also a proof of knowledge. We also start discussing the primitives required to prove that any language in {NP} admits a zero-knowledge proof.

Continue reading