# CS276 Lecture 26: Quadratic Residuosity and Proofs of Knowledge

Scribed by Anindya De

Summary

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.

# CS276 Lecture 26 (draft)

Summary

After showing that last week’s protocol for quadratic residuosity is indeed zero-knowledge, 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.