Sebery J.Cryptography.An introduction to computer security.1989

Goldreich, Micali, and Wigderson in [209] showed that there is a computational zero knowledge proof system for the graph 3-colorability (G3C) problem. As the G3C problem is known to belong to the NPC class, this result asserts that any NPC problem has a computational zero knowledge proof. The G3C problem is de ned as follows [192].

Name: Graph 3-colorability (G3C) problem Instance: Given graph G = (V; E).

Question: Is G 3-colorable, that is, does there exist a function : V ! f1; 2; 3g such that (u) 6= (v) whenever (u; v) 2 E?

This time we need to make an additional assumption that there is a secure probabilistic encryption (Section 4.7). Assume that the message space is M = f0; 1;2; 3g and the key space is K. An encryption function

E : M K ! C

any message x 2 M, we can de ne an ensemble Cx = E(x; K). The encryption function E is secure if any two ensembles E(x; K), E(y; K) are polynomially indistinguishable for x; y 2 M.

An interactive proof system for G3C is presented below. We use the following notations: n = jVj and m = jEj (note that m n2=2). P chooses a random permutation of colors and encrypts colors of all vertices using a secure probabilistic encryption. The cryptograms of the random colors of vertices are revealed to V . The veri er selects a random edge (u; v) for which the prover must show the colors that were used in encryption. V recomputes cryptograms for verticies u and v and checks whether they are valid (or appear in the collection of cryptograms computed by P ). This process is repeated many times.

G3C interactive proof { G3C$

Common Knowledge: an instance of G3C, i.e. a graph G = (V; E) (n is the number of vertices in V).

Description: P and V repeat the following steps m2 times.

After a successful completion of m2 rounds, V halts and accepts.

Observe that the interactive proof satis es the completeness property. For any yes-instance, the prover who knows the requested 3-coloring of the graph, and follows the protocol, can always convince the veri er. For any no-instance, at each round, the prover can convince V with probability at most 1 m1 as there must be at least one edge (u; v) 2 E such that (u) = (v). After m2 rounds, V accepts with the probability (1 m1 )m2 e m. The soundness of the proof system holds. To assert that the interactive protocol is computationally zero knowledge, we need to show that there is a polynomial time transcript simulator SV (G; h) that is polynomially indistinguishable from the view V iewP;V (G; h) for any yes-instance and an arbitrary veri er V . As previously, the veri er uses a polynomial time probabilistic algorithm F to choose an edge for veri cation.

Transcript simulator { SV (G; h) for G3C$

Input: A graph G(V; E), a yes-instance of G3C; h, past transcripts; vi 1, transcript of the current interaction.

Description: Repeat the following steps until the transcript contains m2 entries.

4. If e = F(G; h; vi 1; E1; : : : ; En), then return (E1; : : : ; En; e; a; b; ru; rv) else go to (1).

A single round of the simulator is successful whenever the edge chosen in the step (1) equals to the edge indicated by the algorithm F . This event happens with the probability m1 . The analysis in [209] shows that the simulator runs in expected polynomial time and the expected number of rounds (to generate a single output) is bounded from below by 2m. In the same paper, the authors also demonstrated that the ensemble generated by the simulator is polynomially indistinguishable from the view ensemble of G3C$.

Note that the prover has never used her unlimited power during the execution of G3C$. In fact, it is enough to assume that the prover P is polynomially bounded provided that she knows a 3-coloring of an yes-instance. In this context, computational zero knowledge of G3C$ assures the prover that her secret (the 3-coloring) will not be divulged to the veri er V during the execution of the protocol. What V gains is the assertion that P knows a 3-coloring without revealing any details about it.

Brassard, Chaum, and Crepeau [61] independently showed that the satis a- bility (SAT) problem has a computational zero knowledge protocol. Instead of probabilistic encryption, they used a bit commitment scheme.

12.4 Bit Commitment Schemes

Consider again the protocol G3C$. The probabilistic encryption E was used there to hide the known 3-coloring into a sequence of n cryptograms Ei = E( ( (vi)); ri) (i = 1; : : : ; n). A single cryptogram can be seen as a locked box with a single (permuted) color ( (vi)) of the vertex vi. The lock can be opened by a holder of the key ri. After sending a box, the prover commits herself to the particular color. P cannot change the contents of the box. Later the veri er may ask P to open the box and reveal the color.

A bit commitment scheme is a necessary ingredient for the design of computational zero knowledge protocols for all problems from NPC. It provides a

424 12 ZERO KNOWLEDGE PROOF SYSTEMS

tool to hide the structure of a yes-instance and pins down the prover's choice before getting the veri er's challenge. Having a bit commitment scheme we can encrypt bit by bit the structure or put these bits into locked boxes. The boxes can be treated as pieces of paper covering bits of the yes-instance structure. Obviously, the prover reveals a small part of the structure only so the veri er learns nothing about the structure itself but this is enough for V to be convinced (after several rounds) that the prover indeed knows the structure.

De nition 35. A bit commitment scheme is a pair of polynomial time functions (f; ). The function

f : f0; 1g Y ! X

transforms binary messages b 2 f0; 1g using a random y 2 Y. The number x = f (b; y) is called a blob. The veri cation function

: X Y ! f0; 1; g

is used to open a blob and reveal the bit ( stands for \unde ned"). The functions have to satisfy the following conditions:

1.Binding { for any blob x = f (b; y), the prover is not able to nd y0 6= y such that the blob can be opened to the di erent bit, i.e.

(x; y) 6= (x; y0):

2. Secrecy { two ensembles ff(0; Y)g and ff (1; Y)g are indistinguishable.

The condition (1) says that once P has committed herself to a bit b by presenting a blob x = f(b; y) to the veri er, she is later unable to change the bit. The condition (2) ensures that there is no leakage of information about the committed bits from the blobs that are not opened by the prover.

Commitment schemes can be divided into two major classes,

{schemes with unconditional binding,

{schemes with unconditional secrecy.

If binding holds unconditionally, unambiguity of the committed bit is unconditional. If secrecy holds unconditionally, the veri er can learn nothing about the committed bit in the information theoretical sense (the entropy of the bit stays 1).

12.4.1 Blobs with Unconditional Secrecy

Brassard, Chaum, and Crepeau [61] gave a list of such schemes. We start from a scheme based on the factorization problem. The scheme is initialized by the veri er who chooses at random two large enough primes p and q and creates the modulus N = pq. Next, V picks up at random t 2R ZN and computes s = t2 mod N. The pair (s; N) is made public and is used by P . The encryption and veri cation is described below.

Bit commitment based on factoring

Setup: V selects two large enough primes p and q, creates the modulus N = pq, picks up at random t 2R ZN , and computes s = t2 mod N. The set of blobs X = ZNQ+ and the set Y = ZN . V sends the public parameters of the scheme to P, that is V ! P : s; N.

Hiding: To hide a bit b, P chooses at random y 2 ZN and creates a blob x = f(b; y) = sby2 mod N:

Opening: P reveals her random y and V checks

8 0 if x y2 mod N(x; y) = >< 1 if x sy2 mod N

>: otherwise:

Binding holds under the assumption that the factorization problem is intractable (clearly P has to be polynomially bounded). Secrecy is satis ed unconditionally as the ensembles ff(0; Yg and ff(1; Yg are identical.

Under the assumption that the discrete logarithm is intractable, it is possible to build a bit commitment scheme that uses exponentiation as a one way function.

Bit commitment based on discrete logarithm

Setup: P and V agree on a large enough prime p and a primitive element g 2 Zp . The set X = Zp and Y = f0; 1; : : : ; p 2g. V chooses s 2 Zp 1 and forwards it to P.

Hiding: To hide a bit b, P chooses at random y 2 Y and creates a blob x = f(b; y) = sbgy mod p:

426 12 ZERO KNOWLEDGE PROOF SYSTEMS

Opening: P reveals her random y and V checks

8 0 if x gy mod p(x; y) = <> 1 if x sgy mod p

>: otherwise:

Binding is satis ed conditionally if the discrete logarithm is intractable. Again secrecy is satis ed unconditionally as the ensembles ff(0;Yg and ff(1; Yg are identical.

The GI problem can also be used to construct bit commitment schemes assuming that instances applied are intractable.

Bit commitment based on GI

Setup: P and V agree on a graph G = (V; E) (n = jVj). V selects a random permutation 2R Sym(V) and de nes H = (G). The pair (G; H) of

graphs is known to both P and V (while the permutation is kept secret by V ). The set X = fHjH = (G); 2R Sym(V)g and Y = Sym(V).

Hiding: To hide a bit b, P chooses at random 2 Y and creates a blob (a graph)

X = f(b; ) = ( (G) if b = 0;(H) if b = 1:

Opening: P reveals her random and V checks

80 if (G) = X;(X; ) = ><1 if (H) = X;

>: otherwise:

Note that a blob cannot be opened to a di erent bit under the assumption

that P is not able to nd the isomorphism used by V (intractability of GI instances) to generate H that is an isomorphic copy of G. The ensembles ff(0; Yg and ff (1; Yg are identical, so secrecy holds unconditionally.

12.4.2 Blobs with Unconditional Binding

Consider the quadratic residue problem. It is assumed that for a composite

This property can be exploited in the design of bit commitment schemes. This

time the scheme is set up by the prover who chooses two random and big enough primes p and q and a quadratic nonresidue s 2 ZNQ .

Bit commitment based on QR

Setup: P selects two large enough primes p and q, creates the modulus N = pq,

picks up at random s 2R ZNQ . The set of blobs X = ZNQ and the set Y = ZN . P sends the public parameters of the scheme to V , that is P ! V : s; N.

Hiding: To hide a bit b, P chooses at random y 2 Z and creates a blob

N

x = f(b; y) = sby2 mod N:

Opening: P reveals her random y and V checks

8 0 if x y2 mod N(x; y) = <> 1 if x sy2 mod N

>: otherwise:

The prover is unable to cheat and open a blob to the di erent bit as there exists no y0 2 ZN , which would give the same blob for the di erent bit. This is the consequence of fact that ZNQ \ZNQ+ = ;. Binding is unconditional. The two ensembles ff(0; Y)g and ff(0; Y)g are polynomially indistinguishable. Secrecy holds under the assumption that the testing quadratic residuosity is intractable.

The discrete logarithm can also be used. Let p be a large enough Blum prime and g be a primitive element of Zp .

Bit commitment based on discrete logarithm

428 12 ZERO KNOWLEDGE PROOF SYSTEMS

Once the prover committed herself to a blob, the hidden bit cannot be changed { binding is unconditional. On the other hand, secrecy holds under the assumption that an instance of DL is intractable.

Another example of a bit commitment is a probabilistic encryption discussed in Section 4.7 and applied in Section 12.3.

12.4.3 Multivalued Blobs

A string commitment scheme is a generalization of bit commitment schemes. Unlike in a bit commitment, the prover can hide a string of bits in a single blob. An advantage of these schemes is that they can be tailored to a particular zero knowledge protocol making the interactions more eÆcient. We need to adjust

our de nition. The function f : f0; 1gn X ! Y operates on n-bit sequences. The function : X Y ! f0;1; : : : ; 2n 1; g.

Consider a multivalued blob that constitutes a commitment to an n-bit string s = (b1; : : : ; bn) [400].

String commitment based on discrete logarithm

Setup: P and V agree on a large enough prime p, a primitive element g 2 Zp and an integer h such that logg h is unknown. The set X = Zp and Y = Zp .

Hiding: To lock an n-bit string s, P chooses at random y 2 Y and creates a blob

x = f(s; y) = gshy mod p:

Opening: P reveals the pair (s0; y0) and V checks

Blobs in the scheme: are secret unconditionally. Binding is conditional as it

depends on the assumption that the discrete logarithm is intractable. Claw-free permutation pairs studied in [212] can be used to build a string

commitment scheme [229]. Given two large primes p and q such that p 3 mod 8 and q 7 mod 8. The modulus N = pq. De ne a function gb(x) 4bx mod N where b is a bit.

String commitment based on claw-free permutations

Secrecy is unconditional, binding is conditional if the factorization of N is intractable.

Let us discuss implications of the type of a bit commitment scheme on a zero knowledge proof in which the scheme is being used. A bit commitment scheme with unconditionally secure blobs for the veri er was used to design a zero knowledge proof for G3C. The protocol works correctly for the prover who may or may not be polynomially bounded. Moreover, the prover is not able to cheat the veri er when P opens some blobs. An evident disadvantage is that the security of unopened blobs depends on the assumption of intractability. After completion of the protocol, if the veri er is able to break the bit commitment scheme, the secret structure of yes-instance (in the case of G3C$, a 3-coloring) can be easily revealed.

What happens when a zero knowledge proof employs a bit commitment with unconditional secrecy? P cannot open a blob to two di erent bits under some intractability assumption. Clearly, P has to be polynomially bounded. Otherwise, P could cheat. To make the point clearer, consider a bit commitment based on factoring. If a blob is x, then \all powerful" prover can easily nd factors of the modulus N and open x as bit 0 (for this she needs to nd a square root of x) or as bit 1 (she computes a square root of xs 1). Unlike in the rst case however, the prover has a limited time for computations that may help her to cheat. After the execution of protocol, even if P gains some additional computational power (either by progress in computing technology or development of new more powerful algorithms), it is too late for cheating. Unopened blobs are unconditionally secure and the security does not depend

430 12 ZERO KNOWLEDGE PROOF SYSTEMS

on the computational power of the veri er. In literature, protocols that use this type of bit commitment are called zero knowledge arguments.

12.5 Problems and Exercises

1.Consider the following interactive proof system.

QNR interactive proof { QNR$

Common Knowledge: an instance (x; N) of the QNR problem (n is the size of the instance).

Description: Given a polynomial t(n) in n. P and V repeat the following steps t(n) times.

a)V picks up r 2R ZN and 2R f0; 1g.

b)V ! P : w r2 x mod N.

c)The prover sends to V

0 if w 2 ZNQ+;

1 otherwise:

d)V checks whether = . If the check fails, V stops and rejects. Otherwise V

continues.

After passing through t(n) rounds without rejection, V halts and accepts.

Prove that the protocol is complete and sound. Is the protocol zero knowledge? Justify your answer [211].

2.Consider two protocols QR$ and GI$. Assume that the veri er follows strictly the protocol. Modify the corresponding transcript simulators and show that both protocols are zero knowledge.

3.Consider two protocols GNI$ and QNR$. Show that the two protocols are complete and sound.

4.Consider the following decision problem [497].

Name: Subgroup membership problem.

Instance: Given a composite integer N. Two integers g; x 2 ZN where g generates a subgroup of order .

Question: Is x gk mod N for some k ?

Consider the following interactive proof based on the problem.

Subgroup Membership Interactive Proof

Common Knowledge: an instance of the subgroup membership problem, i.e. a modulus

N and two integers g; x 2 Z where g has order in Z .

N N

Description: Given a polynomial t(n) in n (n is the size of the instance). For i = 1; : : : ; t(n), P and V repeat the following steps

a)P picks up j at random (0 j ) and evaluates gj mod N.

b)P ! V : .

c)V chooses at random a bit b and sends it to P.