Consider the diagram of tunnels in Figure 19.2. Suppose each of the four doors to the central chamber is locked so that a key is needed to enter, but no key is needed to exit. Peggy claims she has the key to one of the doors. Devise a zero-knowledge protocol in which Peggy proves to Victor that she can enter the central chamber. Victor should obtain no knowledge of which door Peggy can unlock.

Figure 19.2 Diagram for Exercise 1

Suppose $p$ is a large prime, $\alpha$ is a primitive root, and $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The numbers $p\text{,}\alpha \text{,}\beta$ are public. Peggy wants to prove to Victor that she knows $a$ without revealing it. They do the following:

1. Peggy chooses a random number $r(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

2. Peggy computes $h_1\equiv {\alpha }^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and $h_2\equiv {\alpha }^{a-r}(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and sends $h_1\text{,}{h}_2$ to Victor.

3. Victor chooses $i=1$ or $i=2$ and asks Peggy to send either $r_1=r$ or $r_2=a-r(\mathrm{m}\mathrm{o}\mathrm{d}p-1)\text{.}$

4. Victor checks that $h_1{h}_2\equiv \beta (\mathrm{m}\mathrm{o}\mathrm{d}p)$ and that $h_i\equiv {\alpha }^{r_i}(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

They repeat this procedure $t$ times, for some specified $t$.

1. Suppose Peggy does not know $a$. Why will she usually be unable to produce numbers that convince Victor?

2. If Peggy does not know $a$, what is the probability that Peggy can convince Victor that she knows $a$?

3. Suppose naive Nelson tries a variant. He wants to convince Victor that he knows $a$, so he chooses a random $r$ as before, but does not send $h_1\text{,}{h}_2$. Victor asks for $r_i$ and Nelson sends it. They do this several times. Why is Victor not convinced of anything? What is the essential difference between Nelson’s scheme and Peggy’s scheme that causes this?

Naive Nelson thinks he understands zero-knowledge protocols. He wants to prove to Victor that he knows the factorization of $n$ (which equals $pq$ for two large primes $p$ and $q$) without revealing this factorization to Victor or anyone else. Nelson devises the following procedure: Victor chooses a random integer $x$ mod $n$, computes $y\equiv x^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$, and sends $y$ to Nelson. Nelson computes a square root $s$ of $y$ mod $n$ and sends $s$ to Victor. Victor checks that $s^2\equiv y(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Victor repeats this 20 times.

1. Describe how Nelson computes $s$. You may assume that $p$ and $q$ are $\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$ (see Section 3.9).

2. Explain how Victor can use this procedure to have a high probability of finding the factorization of $n$. (Therefore, this is not a zero-knowledge protocol.)

3. Suppose Eve is eavesdropping and hears the values of each $y$ and $s$. Is it likely that Eve obtains any useful information? (Assume no value of $y$ repeats.)

Exercise 2 gave a zero-knowledge proof that Peggy knows a discrete logarithm. Here is another method. Suppose $p$ is a large prime, $\alpha$ is a primitive root, and $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The numbers $p\text{,}\alpha \text{,}\beta$ are public. Peggy wants to prove to Victor that she knows $a$ without revealing it. They do the following:

1. Peggy chooses a random integer $k$ with $1\le k\text{<}p-1$, computes $\gamma \equiv {\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}p)$, and sends $\gamma$ to Victor.

2. Victor chooses a random integer $r$ with $1\le r\text{<}p-1$ and sends $r$ to Peggy.

3. Peggy computes $y\equiv k-ar(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$ and sends $y$ to Victor.

4. Victor checks whether $\gamma \equiv {\alpha }^y{\beta }^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$. If so, he believes that Peggy knows $a$.

1. Show that the verification equation holds if the procedure is followed correctly.

2. Does Victor obtain any information that will allow him to compute $a$?

3. Suppose Eve finds out the values of $\gamma$, $r$, and $y$. Will she be able to determine $a$?

4. Suppose Peggy repeats the procedure with the same value of $k$, but Victor uses different values $r_1$ and $r_2$. How can Eve, who has listened to all communications between Victor and Peggy, determine $a$?

The preceding procedure is the basis for the Schnorr identification scheme. Victor could be a bank and $a$ could be Peggy’s personal identification number. The bank stores $\beta$, and Peggy must prove she knows $a$ to access her account. Alternatively, Victor could be a central computer and Peggy could be logging on to the computer through nonsecure telephone lines. Peggy’s password is $a$, and the central computer stores $\beta$.

In the Schnorr scheme, $p$ is usually chosen so that $p-1$ has a large prime factor $q$, and $\alpha$, instead of being a primitive root, is taken to satisfy ${\alpha }^q\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The congruence defining $y$ is then taken mod $q$. Moreover, $r$ is taken to satisfy $1\le r\le 2^t$ for some $t$, for example, $t=40$.

Peggy claims that she knows an RSA plaintext. That is, $n\text{,}e\text{,}c$ are public and Peggy claims that she knows $m$ such that $m^e\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$. She wants to prove this to Victor using a zero-knowledge protocol. Peggy and Victor perform the following steps:

1. Peggy chooses a random integer $r_1$ and computes $r_2\equiv m\cdot r_1^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ (assume that $gcd(r_1\text{,}n)=1$.)

2. Peggy computes $x_1\equiv r_1^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and $x_2\equiv r_2^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and sends $x_1\text{,}{x}_2$ to Victor.

3. Victor checks that $x_1{x}_2\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

Give the remaining steps of the protocol. Victor should be at least 99% convinced that Peggy is not lying.

1. Suppose that $p$ is a large prime, and $g\text{,}h\cancel{\equiv }0(\text{mod}p)$. Peggy wants to prove to Victor, using a zero-knowledge protocol, that she knows a value of $x$ with $g^x\equiv h(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Peggy and Victor do the following:

   1. Peggy chooses three random integers $r_1\text{,}{r}_2\text{,}{r}_3$ with $r_1+r_2+r_3\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

   2. Peggy computes $h_i\equiv g^{r_i}$, for $i=1\text{,}2\text{,}3$ and sends $h_1\text{,}{h}_2\text{,}{h}_3$ to Victor.

   3. Victor checks that $h_1{h}_2{h}_3\equiv h(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

   Design the remaining steps of this protocol so that Victor is at least 99% convinced that Peggy is not lying. (Note: There are two ways for Victor to proceed in Step 4. One has a higher probability of catching Peggy, if she is cheating, than the other.)

2. Give a reasonable method for Peggy to choose the three random numbers such that $r_1+r_2+r_3=\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. (A method that doesn’t work is “Choose three random numbers and see if their sum is $x$. If not, try again.)

Suppose that $n$ is the product of two large primes, and that $s$ is given. Peggy wants to prove to Victor, using a zero-knowledge protocol, that she knows a value of $x$ with $x^2\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Peggy and Victor do the following:

1. Peggy chooses three random integers $r_1\text{,}{r}_2\text{,}{r}_3$ with $r_1{r}_2{r}_3\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

2. Peggy computes $x_i\equiv r_i^2$, for $i=1\text{,}2\text{,}3$ and sends $x_1\text{,}{x}_2\text{,}{x}_3$ to Victor.

3. Victor checks that $x_1{x}_2{x}_3\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

1. Design the remaining steps of this protocol so that Victor is at least 99% convinced that Peggy is not lying. (Note: There are two ways for Victor to proceed in Step 4. One has a higher probability of catching Peggy, if she is cheating, than the other.)

2. Give a reasonable method for Peggy to choose the three random numbers such that $r_1{r}_2{r}_3=\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}n)$. (A method that doesn’t work is “Choose three random numbers and see if their product is $x$. If not, try again.”)

Peggy claims that she knows an RSA plaintext. That is, $n\text{,}e\text{,}c$ are public and Peggy claims that she knows $m$ such that $m^e\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Devise a zero-knowledge protocol similar to that used in Exercises 6 and 7 for Peggy to convince Victor that she knows $m$.