** Summary **

Today we introduce the notion of *zero knowledge proof* and design a zero knowledge protocol for the *graph isomorphism* problem.

**1. Intuition **

A *zero knowledge proof* is a proof between two parties, a *prover* and a *verifier*. Both parties have in input a “statement” that may or may not be true, for example, the description of a graph and the statement that is 3-colorable, or integers and the statement that there is an integer such that . The goal of the prover is to *convince* the verifier that the statement is true, and, at the same time, make sure that *no information other than the truth of the statement* is leaked through the protocol.

A related concept is that of a *zero knowledge proof of knowledge*, in which the two parties share an input to an NP-type problem, and the prover wants to convince the verifier that he (the prover) *knows a valid solution for the problem on that input*, while again making sure that no information leaks. For example, the common input may be a graph , and the prover may want to prove that he knows a valid 3-coloring of , or the common input may be and the prover may want to prove that he knows an such that . An example showing the difference between the two definitions is that the common input is an integer , and the prover wants to prove that he knows a non-trivial factor . (Here the corresponding “statement” would be that is composite, but this can easily be checked by the verifier offline, without the need for an interaction.)

**2. The Graph Non-Isomorphism Protocol **

We say that two graphs and are *isomorphic* if there is a bijective relabeling of the vertices such that the relabeling of is the same graph as , that is, if

We call the graph that as an edge for every edge of .

The graph isomorphism problem is, given two graphs, to check if they are isomorphic.

Here we describe an interactive protocol in which a prover can “convince” a verifier that two given graphs are not isomorphic, and in which the verifier only makes questions for which he already knows an answer, so that, intuitively, he gains no new knowledge from the interaction. (We will give a precise definition later, but we will not prove anything formal about this protocol, which is presented only for intuition.) For the prover, unfortunately, we only know how to provide an exponential time implementation. The verifier algorithm, however, is very efficient.

- Common input: two graphs , ; the prover wants to convince the verifier that they are
*not*isomorphic - The verifier pick a random and a permutation ; the verifier send to the prover
- The prover finds the bit such that and are isomorphic; the prover sends to the verifier
- The verifier checks that , and, if so, accepts

Theorem 1Let be the prover algorithm and be the verifier algorithm in the above protocol. Then

- If are not isomorphic, then the interaction ends with the verifier accepting with probability 1
- If are isomorphic, then for every alternative prover strategy , of arbitrary complexity, the interaction ends with the verifier accepting with probability

The probability in (2) can be reduced to by repeating the protocol times.

**3. The Graph Isomorphism Protocol **

Suppose now that the prover wants to prove that two given graphs are isomorphic, and that he, in fact, knows an isomorphism. We shall present a protocol for this problem in which both the prover and the verifier are efficient.

- Verifier’s input: two graphs , ;
- Prover’s input: and permutation such that ; the prover wants to convince the verifier that the graphs are isomorphic
- The prover picks a random permutation and sends the graph
- The verifier picks at random and sends to the prover
- The prover sends back if , and otherwise
- The verifier cheks that the permutation received at the previous round is such that , and accepts if so

Theorem 2Let be the prover algorithm and be the verifier algorithm in the above protocol. Then

- If are isomorphic, then the interaction ends with the verifier accepting with probability 1
- If are not isomorphic, then for every alternative prover strategy , of arbitrary complexity, the interaction ends with the verifier accepting with probability

**4. Definition of Proof System and of Zero Knowledge **

We conclude the lecture with the formal definition of *proof system* (which captures the fact that a prover successfully convinces a verifier of the truth of a statement) of *honest verifier* zero knowledge, and of (general) zero knowledge.

Great lecture notes, I find this very educational! What does the statement

“An example showing the difference between the two definitions is that the common input is an integer {N}, and the prover wants to prove that he knows a non-trivial factor {N}. (Here the corresponding “statement” would be that {N} is composite, but this can easily be checked by the verifier offline, without the need for an interaction.)”

mean, however? What two definitions do you refer to?

Indeed that was not very clear. I mean the difference between: (1) a zero knowledge proof of a statement and (2) a zero knowledge proof of knowledge.

In both cases we have an instance x of an NP problem, but: in (1) the prover convinces the verifier that x is a YES-instances, and hence a witness w

exists; in (2) the prover convinces the verifier that he (the prover)knowsa witness w.If you take the NP problem “is the given integer x composite?” and you take a witness of x being composite to be a non-trivial factor of x, then having a zero-knowledge proof of compositeness is trivial (the prover says nothing and the verifier checks compositeness by itself via a primality testing algorithm), but it is non-trivial that the prover can give a zero-knowledge proof of knowledge of a factor of x.