CS276 Lecture 27: Computational Zero Knowledge

Scribed by Madhur Tulsiani

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.

Continue reading

CS276 Lecture 27 (draft)

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.

Continue reading

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.

Continue reading

CS276 Lecture 25: Quadratic Residuosity and Zero Knowledge

Scribed by Alexandra Constantin

Summary

Today we show that the graph isomorphism protocol we defined last time is indeed a zero-knowledge protocol. Then we discuss the quadratic residuosity problem modulo a composite, and define a protocol for proving quadratic residuosity. (We shall prove that the protocol is zero knowledge next time.)

Continue reading