Cryptology Assignment 4

Due 10:15 Wednesday, May 20, 1998

Consider the following verification protocol which we showed in class could be used instead of the one in Figure 6.7 in the textbook. The keys and signing algorithms are exactly the same as described in the textbook, as is the notation. Thus, β = α^{a} (mod p), and y = x^{a} (mod p), and the signer needs to prove that log_{x}(y) = log_{α}(β) (= a).

Signer  Verifier
Choose e_{1}, e_{2} ∈ ZZ_{q}^{∗} and com-
pute c = x^{e_{1}}α^{e_{2}} (mod p).

c_{\overline{}}

Choose t ∈ ZZ_{q}^{∗} and compute h_{1} = c^{t} (mod p) and h_{2} =

h_{1}^{a} (mod p). (h_{1}, h_{2})_{\overline{}}

(e_{1}, e_{2})_{\overline{}}

Verify that c = x^{e_{1}}α^{e_{2}} (mod p).

t \overline{}

Verify that t ≠ 0 (mod q) and that h_{1} = (x^{e_{1}}α^{e_{2}})^{t} (mod p) and h_{2} = (y^{e_{1}}β^{e_{2}})^{t} (mod p).

Prove that this protocol is zero-knowledge. (Hint: Recall the zero-knowledge proof system for Quadratic Non-residues which we discussed in class.) Is it perfect zero-knowledge? Is it an interactive proof system? (Prove your answers.)