The prover has $n$ group elements $g_1, ..., g_n$ and wishes to demonstrate the knowledge of the discrete logarithm to base $g$ for each of them, i.e, for each $i \in [1,n]$ she knows some $e_i$ s.t. $g_i = g^{e_i}$. We know that by applying Fiat-Shamir to the Schnorr's protocol, we can get $n$ non-interactive proofs in the form of $(R_i, c_i, s_i)$ where $c_i$ is the hash of $(g_i, R_i)$.

The question is: can we use a same challenge $c$ which is defined as: $c = hash((R_1,..., R_n), (g_1, ..., g_n))$? Each proof will look like $(R_i, c, s_i)$ sharing the same $c$. Would that change the soundness of the scheme? I vaguely feel that this may work through correlation intractability?


1 Answer 1


One way to answer your question is to check if the following proof system is sound:

  • Prover sends $R_1,\dots,R_n$
  • Verifier sends challenge $c$
  • Prover responds with $s_1,\dots,s_n$
  • Verifier checks for each $i$ that $(R_i,c,s_i)$ is an accepting transcript of the Schnorr protocol

Note that this proves a different language, namely $L=\{(g_1,\dots,g_n)\,|\, \forall i\exists w_i:\,g_i=g^{w_i}\}$. Now, if the original protocol was special sound, which is the case for Schnorr's protocol, then this is also special sound. Given two accepting transcripts $(R_{1..n},c,s_{1..n})$ and $(R_{1..n},c',s'_{1..n})$ with $c\neq c'$, you can use the witness extractor of Schnorr's protocol for each $i$ on input $(R_i,c,c',s_i,s'_i)$ to recover every $w_i$.

So soundness is preserved, what about zero-knowledge? You can just invoke the special HVZK simulator for Schnorr's protocol $n$ times on input $c$ to get $n$ accepting transcripts of the form $(R_i,c,s_i)$. This should have the same distribution as a real transcript.

In short, the new protocol is also a $\Sigma$-protocol, i.e. it satisfies special soundness (it's a proof of knowledge), special HVZK and public randomness for the verifier. So applying the Fiat-Shamir transform to it should get you a non-interactive zero-knowledge proof of knowledge with provable security in the random oracle model.

  • $\begingroup$ Many thanks for the insights. $\endgroup$
    – Sean
    Jul 7, 2023 at 19:41

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.