2. Suppose p is a large prime, a is a primitive root, and = a (mod...

Transcribed Image Text:

2. Suppose p is a large prime, a is a primitive root, and = a (mod p). The numbers p, a, 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 (mod p 1). a-r 2. Peggy computes h = a (mod p) and h = a (mod p) and sends h1, h2 to Victor. 3. Victor chooses i = 1 or i = 2 and asks Peggy to send either r = r or r2=ar (mod p 1). 4. Victor checks that hh2 = (mod p) and that h = a'i (mod p). They repeat this procedure t times, for some specified t. a. Suppose Peggy does not know a. Why will she usually be unable to produce numbers that convince Victor? b. If Peggy does not know a, what is the probability that Peggy can convince Victor that she knows a? c. 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 h1, h2. Victor asks for r; 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? 2. Suppose p is a large prime, a is a primitive root, and = a (mod p). The numbers p, a, 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 (mod p 1). a-r 2. Peggy computes h = a (mod p) and h = a (mod p) and sends h1, h2 to Victor. 3. Victor chooses i = 1 or i = 2 and asks Peggy to send either r = r or r2=ar (mod p 1). 4. Victor checks that hh2 = (mod p) and that h = a'i (mod p). They repeat this procedure t times, for some specified t. a. Suppose Peggy does not know a. Why will she usually be unable to produce numbers that convince Victor? b. If Peggy does not know a, what is the probability that Peggy can convince Victor that she knows a? c. 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 h1, h2. Victor asks for r; 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?