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