Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows:

  1. Pick $g$ as a random element from $Z_N^*$
  2. Pick $x$ as a random element from $(0, N')$ where ${N' = p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
  3. Evaluate ${y = g^x \: mod \: N}$

For public $y$ and $g$, what is the easiest way to construct ZKP that the prover knows $x$ without revealing it?

  • 1
    $\begingroup$ I suppose the Schnorr protocol should be applicable here as well with a negliglible probability of failing. $\endgroup$ – SEJPM Aug 25 '18 at 9:24
  • $\begingroup$ As far as I know, the Schnorr protocol is proven to be honest-verifier zero-knowledge but not zero-knowledge and my understanding of this fact is that dishonest verifier can learn about the secret. Isn't that a case? $\endgroup$ – omnomnom Aug 25 '18 at 13:55
  • $\begingroup$ "Any" (means "not honest") verifier would make simulator fail to produce expected output, but not learn about the secret. $\endgroup$ – Vadym Fedyukovych Aug 26 '18 at 16:37
  • $\begingroup$ @VadymFedyukovych Interesting, can you please look at this question and shed some light on it? $\endgroup$ – omnomnom Aug 26 '18 at 21:51
  • $\begingroup$ If I recall correctly, can we not use the Fiat Shamir transform on the Schnorr protocol to make it full ZK (as Schnorr is a Sigma protocol)? $\endgroup$ – user2505282 Apr 15 '19 at 1:34

For a simple example of full ZKPoK of discrete log, you can look into this paper http://www.cs.au.dk/~ivan/Sigma.pdf of Damgard. In a chapter "8 Zero-Knowledge from Σ-protocols" it constructs a full ZK protocol, which is just a bit more complicated than Schnorr one.

  • $\begingroup$ Dåmgard's assumption is over $\mathbb{Z}_q$ with $q$ prime though, I think the answer to this question should also address what happens over $\mathbb{Z}_{pq}$. $\endgroup$ – Ruben De Smet Jul 1 '19 at 12:52

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.