I came across the following protocol for a "Zero-Knowledge Proof of a Discrete Logarithm" in Bruce Schneier's Applied Cryptography (second edition) book. I simply cannot prove to myself that this algorithm is correct, and have been unable to find an explanation of the protocol online anywhere, only finding the original paper it appears Schneier got it from. (In the paper it is referred to as 'protocol 2,' and many of the variables are different, but it is indeed the same protocol.)
The protocol is as follows:
Peggy wants to prove to Victor that she knows an $x$ that satisfies:
$A^x \equiv (mod$ $p)$
where $p$ is a prime, and $x$ is a random number relatively prime to $p-1$. The numbers $A$, $B$, and $p$ are public, and $x$ is secret to Peggy. Here's how Peggy can prove she knows $x$ without revealing it.
- Peggy generates $t$ random numbers, $r_1, r_2, ..., r_t$, where all $r_i$ are less than $p-1$.
- Peggy computes $h_i=A^{r_i}$ $mod$ $p$, for all values of $i$, and sends them to Victor.
- Peggy and Victor engage in a coin-flipping protocol to generate $t$ bits: $b_1, b_2, ..., b_t$.
For all $t$ bits, Peggy does one of the following:
a.) if $b_i = 0$, she sends Victor $r_i$.
b.) if $b_i = 1$, she sends Victor $s_i = (r_i-r_j)$ $mod$ $(p - 1)$, where $j$ is the lowest value for which $b_j=1$.
For all $t$ bits, Victor confirms one of the following:
a.) If $b_i=0$, that $A^{r_i} \equiv h_i (mod \space p)$
b.) If $b_i=1$, that $A^{s_i} \equiv h_i h_j^{-1} (mod \space p)$
Peggy sends Victor Z, where
$Z = (x - r_j) mod \space (p-1)$
Victor confirms that
$A^Z \equiv B h_j^{-1} \space (mod \space p)$
I was unable to prove this to myself, being very confused as to how the probability that Peggy can successfully cheat is indeed the claimed $2^{-T}$ where t is the number of trials performed.
Mainly, I fail to understand how Peggy could possibly be caught during steps 4 - 5. The paper linked above claims "This is because [Peggy] can never answer both possible cases to be sent in step 2." but in step two she either sends $r_i$, a value she literally already has and does not need to compute anything for, or $r_i - r_j \space (mod \space p-1)$, which at least needs some computation, but certainly nothing she couldn't easily perform.
I understand how sending Victor all $h_i$ commits Peggy to the $r$ values, but fail to understand how she uses those to prove knowledge of $x$. I feel as if I'm missing something obvious.
