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

58

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

u2,

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

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

this.

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:

&=2,

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

212

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 ,

201

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

5.2

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

60

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

another.

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

5.2.1

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.

V

So, Alice knows a right colouring in a graph with large I I and IEl.

V

She wishes to prove that to Bob in such a way that he would not learn the

Cryptographic Protocols 61

Y R

a b

- wrong colouring

Fig. 5.1 Colouring: a - right colouring, b

colouring.

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

procedure.

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.

B

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

62

Step 3 For every vertex u, Alice generates the data used in RSA, namely,

Pv,Q v , N = PvQv,cv, and dv.

v

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

regularity.

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

5.2.2

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