4
$\begingroup$

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.

  1. Peggy generates $t$ random numbers, $r_1, r_2, ..., r_t$, where all $r_i$ are less than $p-1$.
  2. Peggy computes $h_i=A^{r_i}$ $mod$ $p$, for all values of $i$, and sends them to Victor.
  3. Peggy and Victor engage in a coin-flipping protocol to generate $t$ bits: $b_1, b_2, ..., b_t$.
  4. 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$.

  5. 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)$

  6. Peggy sends Victor Z, where

    $Z = (x - r_j) mod \space (p-1)$

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

$\endgroup$
2
$\begingroup$

This is "Protocol 2" shown on page 207 of the paper (pdf) referenced.

Maybe I should start from "Protocol 1" that requires (I believe) $s_i = x e_i^{-1}$, not $xe_k^{-1}$.

With step 5, it was explained at Theorem 4, "Correctness" part (that is actually proving soundness property). It starts with a claim of Peggy unable to always produce an acceptable answer $s_i$ for both cases of $b_i$ at step 4. However, this answer does not depend on $x$ and only depends on $\{r_k\}$ chosen by Peggy herself at step 1.

My view is, a better (I believe) protocol was presented next year by (almost) the same team. For practical purposes, Schnorr protocol would be my choice for this setup. This paper remains the first to introduce a proof for DL setup/problem.

$\endgroup$
  • $\begingroup$ We generally consider news of a happy landing of a KLM flight at Santo Domingo somewhat different than historic Columbus report. $\endgroup$ – Vadym Fedyukovych Jun 9 '18 at 10:55
  • $\begingroup$ I understand that the Schnorr protocol is a better option, and that protocol makes sense when I look at it. My confusion is how this protocol is even correct, as it is the claim in Theorem 4 "Correctness" that I don't understand. I fail to see how Peggy could possibly not be capable of generating both $s_i$. $\endgroup$ – Strident Jun 10 '18 at 0:24
  • $\begingroup$ There are a few thing that could fixed, starting from $i$ vs. $k$ index at Protocol 1. A historic overview in a recent modern textbook could be a better option. $\endgroup$ – Vadym Fedyukovych Jun 10 '18 at 9:30

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.