. 12
( 36 .)


with probability 1/3.
It is interesting to note that if any of the players will violate the protocol
specifications, it may be used against that player. Therefore each player is
Basics of Contemporary Cryptography for IT Practitioners

concerned with exact observance of rules. Let™s check it assuming that the
game repeats many times.
Suppose that Alice does not shuffle the numbers ul, u g , but always
sends them in one order or follows some other simple rule. If the distribution
of cards is carried out several times, Bob can benefit from Alice™s behaviour
(e.g. he will always send back to Alice the first number and will know what
card she is dealt). So it is advantageous to Alice to shuffle the cards.
Similarly, it can be easily checked that it is better for Bob to shuffle and
select cards randomly (with equal probabilities).
Check the second requirement to a fair card game. When Bob selects
uito be Alice™s card (Step 2 ) he does not know the secret C A , so he cannot
determine to which card u corresponds and computation of CA given u i
is equivalent to solving the discrete logarithm problem which is impossible
when p is large. As a matter of fact, when Alice selects a card for Bob, and
Bob for Alice, neither of them can determine the value of the card because
it is encrypted with either C A or CB.
Notice also that neither Alice nor Bob can determine the card remaining
in the deck because the corresponding number has the form acAcB (see (5.4)
and ( 5 . 5 ) ) . Alice does not know d s and Bob does not know d A to decrypt
Check the third requirement. In case of contention between Alice and
Bob, they reveal their cards together with the record of all computations
to the judge who is able to repeat all computations and bring in a verdict.
Finally, check the fourth requirement. Eve, who overhears all commu-
nication between Alice and Bob, has the numbers u1,u2,u3, 711, 712, 713,
and w1. Each of these numbers can be represented as a” mod p where x
is unknown to Eve. But to find x one have to solve the discrete logarithm
problem which is practically impossible. So Eve cannot learn anything. 0

Assume that Alice and Bob wish to honestly deal the three
Example 5.1
cards: the three ( a ) ,the seven (p), and the ace (7).(More exactly, it is
usually assumed in cryptography that neither of them wants to be cheated
and “greater” honesty is not required.) Let the following parameters be
chosen at the preliminary stage:

p=23, p=3, +=5.

Let Alice choose C A = 7 and Bob choose CB = 9. Then they find using the
extended Euclidean algorithm dA = 19 and d B = 5 .
Cryptographic Protocols 59

(Step 1) Alice computes
u1 = 27 mod 23 = 13,
u2 = 37 mod 23 = 2 ,
u3 = 57 mod 23 = 17.

Then she shuffles ul,212, u3 and sends them to Bob.
(Step 2) Bob selects one of the numbers received. Let it be 17. He sends
the number 17 to Alice. She knows that 17 corresponds to y and so her
hand is the ace.
(Step 3) Bob computes
13™mod 23 = 3 ,
v1 =
= 29 mod23=6

and sends these numbers to Alice, perhaps, having swapped them.
(Step 4) Alice receives the numbers 3 and 6, selects one of them, let it
be 3, and computes the number
= 3” mod 23 = 6 ,

She sends this number to Bob, who computes
z = 6˜ mod 23 = 2
and learns his card a , i.e. his hand is the three. The seven remains in
the deck but neither Alice nor Bob know that. As for Eve who has inter-
cepted all messages, she cannot learn the cards without having computed
the inverse functions of the messages which is impossible when p is large.

Zero Knowledge Proofs

Consider the following problem which arises in some cryptographic applica-
tions. The participants are again Alice and Bob. Alice knows the solution
of some complex problem and wishes to convince Bob thereupon but in
such a way that he would not learn the solution. In other words, Bob must
become sure that Alice knows the solution but must know nothing about
that solution. At first glance the very problem statement seems absurd and
the possibility of its being settled fantastic ! In order to realise the situation
better, consider a scenario from the life of pirates. Let Alice knows the map
of an island where there is buried treasure. And let Bob be the captain of
Basics of Contemporary Cryptography for IT Practitioners

the ship which can get her to the island. Alice wishes to prove t o Bob that
she really possesses the map without showing it (or else Bob could manage
without her and obtain all the treasure himself).
Similar problem is in demand for computer networks in the cases when
Bob (server or domain controller) should decide on Alice™s admission t o the
information stored in the network but Alice does not wish that anybody
who overhears the communications channels, including Bob himself, learn
something about her password. That is, Bob gets zero knowledge about her
password (map) but is sure that Alice possesses that password (or map).
So our goal is to construct a “zero-knowledge proof” protocol. At that
we assume that participants can play an unfair game and try to cheat one
As a complex problem whose solution is known to Alice, we first con-
sider the graph colouring problem with three colours. We describe a
quite simple in a sense of ideas protocol for that problem. Then we
consider the problem of finding Hamiltonian cycle in a graph with more
complicated in a sense of ideas but more computationally efficient proof
protocol. Note that both problems, the graph colouring and finding
Hamiltonian cycle, are NP-complete. We do not give a formal defini-
tion of NP-completeness which can be found, e.g. in [Aho et a2. (1976);
Papadimitriou (1994)l. For the reader who is not familiar with this defi-
nition, note only that, informally, NP-completeness means the exponential
growth of problem solving time as the problem size (the amount of initial
data) increases.

Graph Colouring Problem
In the problem of graph colouring, a graph is considered with the set of
vertices V and set of edges E (denote the number of elements in these sets
by JVI and IEI). Alice knows the right colouring of the graph with three
colours, red (R), blue (B), and yellow (Y). The right colouring is the one
where any two adjacent vertices, i.e. connected by an edge, are coloured
with different colours. Consider an example (Fig. 5.1).
For finding a correct colouring with three colours, only exponential al-
gorithms are known, i.e. those whose computation time grows exponentially
as the number of vertices and edges in a graph increases. Therefore, in case
of large I I and JEl this problem is intractable.
So, Alice knows a right colouring in a graph with large I I and IEl.
She wishes to prove that to Bob in such a way that he would not learn the
Cryptographic Protocols 61


a b

- wrong colouring
Fig. 5.1 Colouring: a - right colouring, b

The protocol of proof consists of a number of realisations of the following

Step 1 Alice chooses a random permutation II of three letters R, B, Y and
changes the colouring of graph according to that permutation. Obvi-
ously, the colouring remains correct. For example, if II = (Y,R,B)
then the colouring on the left (Fig. 5.1) turn into the colouring shown
in Fig. 5.2.


Fig. 5.2 Another variant of colouring

Step 2 For every vertex u from set V , Alice generates a large random
integer T and replaces its two least significant bits by the colour code:
00 for red, 01 for blue, 10 for yellow.
Basics of Contemporary Cryptography for IT Practitioners

Step 3 For every vertex u, Alice generates the data used in RSA, namely,
Pv,Q v , N = PvQv,cv, and dv.
Step 4 Alice computes
Z, mod N,
= r,".

and sends Bob the values N,, d,, and Z,, for each vertex.
Step 5 Bob selects randomly one edge from set E and tells Alice what
edge he has selected. Alice responds with the numbers c,, and cvZ
corresponding to the vertices of this edge. After that Bob computes

, i ,= 2:;'
, mod N,, = rvz
Z,, = Z;,l mod N,, = r,,
and checks two least significant bits in these numbers. Under the right
colouring, the least significant bits in Z , Zv2must be different. If
, and
it is not the case, Alice is declared cheating and the protocol stops. Oth-
erwise, the described procedure repeats once again. The total number
of repetitions is alEl where a > 0 is a protocol parameter.
Proposition 5.2 If Alice does not know the right colouring of the graph
then the probability of deceiving Bob does not exceed e-a where e M 2.718
as the Euler number (the base of natural logarithm).
Remark If one takes a large a then the probability of deception can be made
as small as desired. For instance, with a = 5 this probability is less than 0.01.

Proof. Assume that Alice does not know the right colouring, i.e. her
colouring is not correct. In this case, at least for one edge the vertices
are equally coloured. If Alice obeys the protocol then the probability of
selecting that edge by Bob is not less than 1/IEl (in this case Alice is
denounced). Hence, the probability that Alice can deceive at one realisation
of the protocol procedure does not exceed 1 - 1/IEl and, consequently,
the probability that Alice can deceive at alEl realisations does not exceed
(1 - l/IEI)"lEl. Using a well-known inequality 1 - 2 5 e-" we obtain

Check the properties zero-knowledge proof must have.
(1) We see that the probability of Alice's deception can be made as
small as desired by selecting large a.
(2) Let us explain why Bob does not receive any information about
colouring. Because the colours are permuted randomly in each realisation
(see Step 1) he cannot learn the right colouring examining all edges one
Cryptographic P TOt OCOl S 63

after another. All he learns is that two adjacent vertices are differently
coloured but it gives no information about colouring. Besides, he cannot
find the codes of colours given the set of N, and d, since r, is random
(Step 2). He also cannot decrypt 2, since he does not know c, (these are
not sent for all vertices) and cannot compute cw without P, and Q,.
(3) Consider one more chance to deceive that Alice seems to have. It
seems that Alice can substitute cUl and c,,˜ with other values at Step 5.
But it is impossible since c, satisfying the equation

is unique and Bob knows d,.
So, all requirements are fulfilled:

(1) Alice proves to Bob that she knows the problem solution and the prob-
ability of deception does not exceed e - a ;
(2) Bob obtains no information about the colouring.

Consider the last chance of deception for all participants. What will
ensue should they disobey the described protocol by making their choices
not randomly?
Let, for instance, Bob ask edges not randomly but by some simple rule
(e.g. in their order). In this case Alice, not actually knowing the colouring,
can deceive him by preparing “right” colours only for the edges he will
ask. Therefore Bob is interested in making random selections without any
The security of other protocol actions is determined by security of RSA
and under large P, and Q, the system is quite reliable.

Hamiltonian Cycle Problem
The problem considered in this subsection not only gives us an opportunity
to describe one more scheme of constructing zero-knowledge proofs but also
plays an important theoretical role. Manuel Blum showed that, speaking
informally, any mathematical statement can be represented as a graph, the
proof of the statement being in correspondence with the Hamiltonian cycle
of the graph (see [Goldreich et al. (1987); Schneier (1996)l). Therefore
the existence of zero-knowledge proof for Hamiltonian cycle implies that


. 12
( 36 .)