2
$\begingroup$

My question (at the bottom) is in regards to the part of the protocol where the Verifier challenges the Prover by sending a bit b where b = 0 or b = 1.

Example for context

One Time Setup

p = 3  
q = 5  
n = 15  
privKey = 8 (co-prime to n)  
pubKey = privKey^2 mod n ⇒ 64 mod 15 = 4

At this point, the verifier knows:
n = 15
pubKey = 4

Protocol: The following is repeated t times

  1. Prover selects a random number < n
    randNum = 11
  2. Prover computes x as follows and sends x to Verifier
    x = randNum^2 mod n ⇒ 121 mod 15 = 1
  3. Verifier chooses a bit, b = 0 or b = 1, and sends it to Prover as a challenge
  4. Prover computes (privKey^b • randNum) mod n as a response

By choosing a bit b = 0 or b = 1 the Verifier chooses to see either:
Case 1
b = 0: randNum mod n ⇒ 11 mod 15 = 11 (if randNum is < n, verifier will receive randNum)
OR Case 2
b = 1:(randNum • privKey) mod n ⇒ 88 mod 15 = 13

Case 1: b = 0
As a response from Prover, Verifier receives: 11
Verifier computes:

11^2 mod 15 = (x • pubKey^b) mod n  
11^2 mod 15 = (1 • 4^0) mod 15  
121 mod 15  = 1 mod 15  
1 = 1 //passes the test

Case 2: b = 1
As a response from Prover, Verifier receives: 13
Verifier computes:

13^2 mod 15 = (x • pubKey^b) mod n
13^2 mod 15 = (1 • 4^1) mod 15  
169 mod 15 = 4 mod 15  
4 = 4 //passes the test

My Question

In Case 1, the Verifier is actually checking that:

randNum^2 mod n = (randNum^2 mod n) mod n 

which is essentially randNum = randNum

I don't understand why this part of the protocol is necessary. It seems that all the Prover has proved here is that they've picked a randNum. Anyone who doesn't know the privKey will always be able to do this.

I understand that there is only a 50% chance in any given round that this case will be chosen and that a false Prover (one who does not know privKey) will inevitably fail, but it seems that Case 2, where b = 1, is sufficient for the Verifier to be convinced that the Prover knows the privKey whilst gaining zero knowledge about the privKey and that no false Prover could pass this test.

Why is Case 1 a necessary part of the protocol? I must be missing something.

I hope that's clear, Thanks!

$\endgroup$
  • $\begingroup$ I would also be very interested in this questions... does anyone know the answer? :) $\endgroup$ – ec-m Feb 25 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.