# For the discrete log zero-knowledge proof, can all challenges be done at once?

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

• Google "Fiat-Shamir heuristic" – user27950 Jul 13 '17 at 4:42
• @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. – Daffy Jul 13 '17 at 5:11
• No, it is not vulnerable to replay attacks, due to the random b's . In fact, it's a standard way of authentication. – user27950 Jul 13 '17 at 5:38
• @Cryptostasis Ah, I should learn to read :) If you make that an answer, I'll up vote and mark it correct. – Daffy Jul 13 '17 at 5:42
• Choosing challenge $b$ from a large set could be another option. Please take a look at Schnorr protocol. – Vadym Fedyukovych Jul 13 '17 at 20:30