Introduction to Cryptography with Coding Theory, 3rd Edition

19.3 Exercises

1. 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

   

   Figure 19.2 Full Alternative Text

2. 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. ...