1
$\begingroup$

Section 2 of this paper (page 5 in the PDF) gives a protocol for a zero-knowledge proof to prove Alice has $x$ for $y = a^x \mod p$ to Bob without revealing the value of $x$. The protocol is as follows.

  • Alice sends Bob $y$, along with the public parameters $a$ and $p$. ($p$ is prime)
  • Repeat $T$ times:
    1. Alice picks a random $r \in \{0,1,...,p-1\}$ and calculates $C = a^r \mod p$
    2. Alice sends $C$ to Bob
    3. Bob sends Alice a random $b \in \{0,1\}$ and sends it to Alice
    4. Alice calculates $R = r + bx \mod {(p-1)}$
    5. Bob verifies this as $a^R\stackrel{?}{=}Cy^b \mod p$

My question is, can this be modified so there are less interactions? Particularly in steps 1 and 2, Alice calculates all $C_0, C_1, ..., C_T$ and sends them to Bob all at once. In step 3, Bob picks all $b_0, b_1, ..., b_T$ and sends them to Alice. In step 4, Alice calculates all response values $R_0, ..., R_T$. Finally, Bob verifies them all similarly.

Does this open any security issues? The resulting information is the same, so I don't see how a cheating Bob could discover $x$. My question is mainly about whether or not a cheating Alice could fool Bob into thinking she knows $x$.

Improve this question
$\endgroup$
5
  • $\begingroup$ Google "Fiat-Shamir heuristic" $\endgroup$
    – user27950
    Jul 13, 2017 at 4:42
  • $\begingroup$ @Cryptostasis While that is very interesting, it's not resistant to replay attacks. I'm using the proof of $x$ as identification. I'm wanting to reduce the number of interactions to make the whole process quicker. $\endgroup$
    – Daffy
    Jul 13, 2017 at 5:11
  • 1
    $\begingroup$ No, it is not vulnerable to replay attacks, due to the random b's . In fact, it's a standard way of authentication. $\endgroup$
    – user27950
    Jul 13, 2017 at 5:38
  • $\begingroup$ @Cryptostasis Ah, I should learn to read :) If you make that an answer, I'll up vote and mark it correct. $\endgroup$
    – Daffy
    Jul 13, 2017 at 5:42
  • $\begingroup$ Choosing challenge $b$ from a large set could be another option. Please take a look at Schnorr protocol. $\endgroup$
    – Vadym Fedyukovych
    Jul 13, 2017 at 20:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.