We can use Fiat-Shamir heuristic to replace 3-move Schnorr's protocol with 1-move non-interactive protocol.

When I implement this non-interactive protocol( ref. https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic): That is

Let $G$ be a cyclic group with order $q$.

Peggy needs to prove that she knows $x$ which is the discrete logarithm of $y =g^x$ to a fixed base $g$.

  1. She randomly chooses an element $v \in [1,q-1]$ and computes $t = g^v$.
  2. She computes $c = H(g,y,t)$, where $H$ is a cryptographic hash function (implementing random oracle).
  3. She computes $r = v-cx \pmod q$. The proof is the pair $(t,r)$.

  4. Anyone can check this proof by $t = g^r \cdot y^c$.

My question is that:

Assume that Peggy is prover and Victor is verifier. Can Peggy send $y =g^x$ and a proof $(t,r)$ in the same round?

Or it should be divided it into two rounds:

  1. The first round is that Peggy sends $y=g^x$ to Victor.
  2. The second round is that a proof $(t,r)$ to Victor.

Does it arise any risk if we combine two rounds?



1 Answer 1


No, sending both parts of the proof together does not create any additional risk.

Notice that at the end of the protocol, Victor knows the same set of values, regardless of whether it has been split into two rounds or not. So whatever he would be able to achieve in "one-round" version, he can still achieve after the second round of the two phase protocol.

  • $\begingroup$ Thank you very much! I see. $\endgroup$
    – user76328
    Commented Feb 7, 2020 at 5:28

Your Answer

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

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