<<

. 13
( 36 .)



>>

the proof of any mathematical statement can be presented in the form of
zero-knowledge proof.
Basics of Contemporary Cryptography f o r IT Practitioners
64


Definition 5.1 Hamiltonian cycle in a graph is a continuous circular
path that passes through all vertices, each vertex visited exactly once.
Consider the graph shown in Fig. 5.3.
Example 5.2




Fig. 5.3 Graph with Hamiltonian cycle (8, 2, 4,6 , 3, 5 , 7, 1)


The path that sequentially passes through vertices 8, 2, 4, 6, 3, 5, 7,
1, is a Hamiltonian cycle. Actually, this path contains all vertices of the
graph and each vertex is visited only once.
It is plain that if a Hamiltonian cycle exists in a graph G with n vertices
then, under a certain numbering of vertices, it will pass exactly through ver-
tices with sequential numbers 1,2,3, . . . ,n. So by examining all possible
enumerations of vertices we shall necessarily find a Hamiltonian cycle. But
the number of enumerations equals n! and therefore, already under moder-
ately large n, say, n = 100, this approach becomes infeasible in practice. It
is proved that the problem of finding a Hamiltonian cycle in a graph is NP-
complete (we have already mentioned this). Informally, NP-completeness
of the considered problem means that, for solving it, no algorithms exist
(more exactly, no algorithms are known) which are essentially faster than
the exhaustive search method mentioned above.
Our task is to construct a protocol that shall be used by Alice to prove to
Bob that she knows a Hamiltonian cycle in a certain graph G in such a way
that Bob will not get any knowledge of this cycle. The first construction of
Cryptographic PTOtOCOlS 65


the protocol was suggested in [Blum (1986)l. Recall once more that “zero
knowledge” means that, independently of the number of realisations of the
protocol, Bob will have the same knowledge about Hamiltonian cycle as he
might have if he had just studied the graph G.
So, assume that Alice knows a Hamiltonian cycle in graph G. She can
prove this to Bob (and anybody else who has the graph) with the help of
a protocol described below. She may use this proof, e.g. for her personal
identification. But before giving the protocol description, let us agree on
some notation.
We shall denote graphs by letters G, H , F , implying simultaneously
corresponding adjacency matrices. The matrix element Hi,j = 1 if there is
an edge in graph H which connects the vertices i and j ; Hi,j = 0 otherwise.
The symbol 11 will denote concatenation of two numbers, more exactly, of
two corresponding binary words. For example, 1001O))l= 100101. We
need a public-key cipher. Generally speaking, it may be any cipher, but for
concreteness we shall use RSA (Sec. 2.6). Assume that Alice has generated
the RSA system with public parameters N and d. It is essential that the
messages encrypted with that system can only be decrypted by Alice and
no one else (since only Alice knows the corresponding private key).
Proceed now to the description of the protocol. Each protocol realisation
comprises the following four steps (explanations will be given below).

Step 1 Alice constructs a graph H which is the copy of G with a new
(random) numbering of vertices. In terms of graph theory, H is said
to be isomorphic to G. Alternatively, H is obtained by some per-
mutation of vertices in G (preserving connections between vertices).
Alice encodes matrix H by ascribing to initial zeroes and ones random
numbers ˜ i , according to the scheme H i , j = ri,j 1) Hi, j. Then she en-
j
crypts the elements of matrix I and obtains the encrypted matrix F ,
?
Fi,j = H$ mod N . Alice sends matrix F to Bob.
Step 2 Upon the receipt of encrypted matrix F , Bob asks Alice one of two
questions:
(1) What is the Hamiltonian cycle in graph H?
(2) Whether graph H is isomorphic to G?
Step 3 Alice answers the corresponding question of Bob:
(1) In response to the first question, she decrypts in F the edges that
constitute the Hamiltonian cycle.
(2) In response to the second question, she decrypts F completely (in
Basics of Contemporary Cryptography for IT Practitioners
66


fact, she sends Bob the graph fi) and reveals the permutations
used to produce graph H from G.

Step 4 Having received the reply, Bob checks the correctness of decrypt-
ing by repeated encrypting and comparing to F and makes certain
that either the edges decrypted constitute a Hamiltonian cycle, or the
permutations revealed convert graph G to graph H .

The described process repeats t times.
We discuss briefly several issues on the protocol construction in the form
of questions and answers.
(1) Why does Alice construct an isomorphic graph? If she had not
done that, Bob, upon the reply to his Question 1, would have learned the
Hamiltonian cycle in graph G.
(2) Why does Alice encode the matrix H? We have already met with
this trick when encrypting colours of vertices. The matter is that it is
impossible to encrypt individual zeroes and ones (with RSA cipher they
are not changed at all). Even if we replace 0 and 1 by some numbers a
and b then we will obtain as few as two different ciphertexts and it will
be straight to determine their correspondence to a and b, i.e. the graph™s
structure will not be concealed. Here we face a typical situation where a
so-called randomised cipher is necessary. And this cipher is constructed by
introducing random numbers into the matrix H prior to encrypting. The
encoded matrix H completely describes the graph (odd numbers denote the
presence of edge, even numbers the absence of it) but after encryption the
graph™s structure becomes completely concealed.
(3) Why does Bob ask two questions? If he had asked only Question 1
which is, in a sense, the main then Alice, not actually knowing a Hamilto-
nian cycle in graph G, would have been able to present another graph with
the same number of vertices and artificially enclosed Hamiltonian cycle.
Therefore Bob sometimes asks Alice to prove the isomorphism of H and G.
The point is that Alice does not know in advance what question she will be
asked.
(4) Why cannot Bob ask the two questions at once? In this case he
would have learned the Hamiltonian cycle in G, since he had obtained a
Hamiltonian cycle in H and the way of converting H into G.
(5) Why does Bob check the correctness of decrypting? If he had not
done that then Alice at Step 4 would have sent some “favourable” informa-
tion not connected with that sent at Step 2.
Cryptographic Protocols 67


The main details of the protocol are more strictly justified in the proofs
of the following two propositions.


Proposition 5.3 The probability of deception under t protocol realzsa-
tions does not exceed 2 - t .


Proof. First we show that the probability of deception in one realisation
of the protocol equals 1/2. Notice that if Alice knows the Hamiltonian cycle
in graph G, she can answer right to any question of Bob. On the contrary,
if she does not know the Hamiltonian cycle then the most she can do is to
prepare an answer to either the first or the second question. In expectation
of Question 1 she creates a new graph with artificially enclosed Hamiltonian
cycle. But in this case she will not be able to prove its isomorphism to graph
G. In expectation of Question 2 she creates a graph isomorphic to G. But
in this case she will not be able to show a Hamiltonian cycle therein. So
the probability of deception equals the probability of guessing the question
number. Assuming that Bob puts both questions with equal probabilities
we obtain that the probability of deception equals 1/2.
Since Bob stops the game upon a first incorrect answer, the probability
of deception under t realisations of the protocol does not exceed (1/2)t. 0


The described protocol implements a zero-knowledge
Proposition 5.4
proof.


Proof. In order to prove that Bob does not get any knowledge in reali-
sation of the protocol it suffices to show that all he receives from Alice he
would obtain himself without entering into any communication with Alice.
Let™s begin with the second question of Bob. As a reply to this question
he receives a graph isomorphic to G. But he could himself construct as
many isomorphic graphs as he wished and what he obtains from Alice is
one of such graphs.
The case of the first Bob™s question is not that simple. As a reply to
his first question he obtains a Hamiltonian cycle in a graph isomorphic to
graph G. At first glance it may seem that this provides Bob with some
information. But it is not so. Notice that if G possesses a Hamiltonian
cycle then under some numbering of vertices, there exist an isomorphic
Basics of Contemporary Cryptography for IT Practitioners
68


graph defined by the adjacency matrix of the form




11
* 1 * . . .* **
* **
**I.**

***...* ™
1*
***... **1
1 * *... .* * *
..


where * denotes the uncertainty in the presence or absence of edge. Under
such a numbering the Hamiltonian cycle passes through the vertices in the
order of increasing numbers. By changing the numbering of vertices Bob
can construct from (5.8) various isomorphic matrices. When Alice replying
to the first question of Bob reveals the Hamiltonian cycle, Bob obtains just
one of these matrices.
So, Bob does not obtain any additional information from Alice which
0
he could not obtain himself.

Consider an example to illustrate all steps and operations of the de-
scribed protocol.

Example 5.3 Take as a basis the graph G shown in Fig. 5.3. Its adja-
cency matrix is


˜ 1 2 3 4 5 6 7 8
10 0 1 0 0 11m
lpJ0 0 0 1
0
2 0
OM1
_.



31 1 0 10
0 0 OpJO 0
G= 40 1
-1 0 0 om1
500




0 is used to show the Hamiltonian cycle. Let™s use the RSA
The box
system with public parameters N = 55, d = 3 for encryption.
Cryptographic Protocols 69


At Step 1 of the protocol, Alice chooses a random numbering of vertices,
say, 7, 4, 5, 3, 1, 2, 8, 6, and constructs ail isomorphic graph

7 4 5 3 1 2 8 6
7 0 0 1 lll_lO 0 0
4 - 0 0 0 0 1 om
0
1 0 0 1 0
H= 0 1 1 0 1
o m 1
1 0
1 0 0 1 0



Next, she must encodc Y by ascribing to zeroes and ones some random
numbers. In this particular example let her simply ascribe to the left of
each element a randomly chosen digit from the set {1,2,3,4,5}:

50 20 11 31 21 40 20 10™
40 30 50 20 10 41 50 21
41 30 50 11 30 20 51 40
- 1110413051413021
H=
31 20 40 11 50 10 41 31
50 41 20 21 40 10 21 50
40 30 31 50 41 21 30 40
20 41 10 51 41 20 30 40,

Now she encrypts the matrix H by cubing each element modulo 55:

˜40 25 11 36 21 35 25 10™
35 50 40 25 10 06 40 21
06 50 40 11 50 25 46 35
11 10 06 50 46 06 50 21
F=
36 25 35 11 40 10 06 36
40 06 25 21 35 10 21 40
35 50 36 40 06 21 50 35
25 06 10 46 06 25 50 35,

(It may seem at attentive examination of matrix F that the cipher used
poorly hides the initial matrix H . It is explained by small value of the

<<

. 13
( 36 .)



>>