# Zero knowledge proof for a discrete logarithm

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?

• I suppose the Schnorr protocol should be applicable here as well with a negliglible probability of failing. – SEJPM Aug 25 '18 at 9:24
• 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? – omnomnom Aug 25 '18 at 13:55
• "Any" (means "not honest") verifier would make simulator fail to produce expected output, but not learn about the secret. – Vadym Fedyukovych Aug 26 '18 at 16:37
• @VadymFedyukovych Interesting, can you please look at this question and shed some light on it? – omnomnom Aug 26 '18 at 21:51
• 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)? – user2505282 Apr 15 '19 at 1:34

• 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}$. – Ruben De Smet Jul 1 '19 at 12:52