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 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.
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) knows a 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.