7
$\begingroup$

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?

$\endgroup$
4
  • $\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, 2018 at 13:55
  • $\begingroup$ "Any" (means "not honest") verifier would make simulator fail to produce expected output, but not learn about the secret. $\endgroup$ Aug 26, 2018 at 16:37
  • $\begingroup$ @VadymFedyukovych Interesting, can you please look at this question and shed some light on it? $\endgroup$
    – omnomnom
    Aug 26, 2018 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$ Apr 15, 2019 at 1:34

2 Answers 2

3
$\begingroup$

This problem was studied in [BCK], and interestingly they showed that constructing a Schnorr-like zero-knowledge proof system (ZKP) in a group of unknown order with non-trivial soundness error is not possible in the plain model (i.e., without CRS). Their result is much more general and talks about homomorphisms in groups of unknown order.

However, if one considers the CRS model, then [BBF] recently showed that ZKP is possible in the generic group model under the "adaptive root" assumption. Boneh talks briefly about this work here.

[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 2019

[BCK]: Bangerter, Camenisch and Krenn, Efficiency Limitations for Σ-Protocols for Group Homomorphisms, TCC 2010

$\endgroup$
2
  • 1
    $\begingroup$ Great and correct answer! Instead of Knowledge of Exponent assumption, did not you want to say Adaptive Root assumption? $\endgroup$ May 8, 2020 at 16:59
  • $\begingroup$ Good point. In the talk Boneh mentions knowledge-of-exponent assumption, but looking at the paper again, it seems they rely on the adaptive root assumption. $\endgroup$
    – ckamath
    May 8, 2020 at 17:45
1
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Jul 1, 2019 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.