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
1
$\begingroup$

If $b$ was always the same value, you could convince the Verifier that you have the private key even though you actually don't!

Case $b = 1$:

Instead of sending $x = {\text{randNum}}^2 \bmod n$, the false Prover can send $x = {\text{randNum}}^2 / \text{pubKey} \bmod n$.

Assuming the Verifier sends $b = 1$, the false Prover can then send $\text{randNum} \bmod n$.

When the Verifier verifies the response, they check if ${\text{randNum}}^2 == (({\text{randNum}}^2)/\text{pubKey} \bmod n) \times \text{pubKey} \bmod n)$, which simplifies to ${\text{randNum}}^2 == {\text{randNum}}^2 \bmod n$, and that's obviously true. So even though the false Prover doesn't actually have the private key, the verification succeeded. But here's the catch: If $b$ turns out to be $0$ instead, they'd have to send $\sqrt{x} \bmod n$ in the final step. This is computationally infeasible.

As you observed, if the false Prover sends $x = {\text{randNum}}^2$ and $b$ turns out to be $0$, they can pass the verification. But if $b = 1$, the false Prover can't pass the final step, as they don't know $\text{privKey}$.

In summary, the false Prover has to commit to $b$ either being $0$ or $1$ before sending $x$. Each guess has a 50/50 probability of being correct. So after $t$ rounds, the chance of the Prover actually being a false Prover is $(1/2)^t$

$\endgroup$
  • $\begingroup$ Welcome to Cryptography. $MathJax/ \LaTex$ available in this site. $\endgroup$ – kelalaka Sep 9 at 18:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.