Today we introduce the notion of zero knowledge proof and design a zero knowledge protocol for the graph isomorphism problem.
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 1 Let 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 2 Let 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.