1
$\begingroup$

Before looking at the textbook ZKP for discrete log, I tried to construct one myself. This turned out quite different to the textbook one, and I've been wondering what might be wrong with it? (I was unable to refute any of the ZKP requirements, so I guess I'm missing something).

The original problem:

Given $g,h \in \mathbb{Z}_p^x$ ($g$ being the generator), provide a ZKP for the knowing $x \in \mathbb{Z}_p^x$ such that $g^x=h$.

My suggestion:

  • The verifier chooses a random $r\in \mathbb{Z}_p^x$ and sends $h^r$ to the prover.
  • The prover sends back its best guess for $g^r$, denoted $a$.
  • The verifier asserts that $a=g^r$.

If the prover indeed knows $x$ then he will send: $a=(g^{rx})^{x^{-1}}=g^r$.

If the prover does not know $x$ then, in order to get $a=g^r$ from knowing $g^{rx}$ he has to solve discrete log for $(g^r)^x$ to recover $g^r$, i.e. discrete log for $g^x$.

If the verifier is dishonest, I don't see how he can gain an edge on discovering $x$.

What am I missing?

$\endgroup$
2
  • $\begingroup$ How would you go about proving knowledge soundness? How would you prove zero knowledge? $\endgroup$
    – Maeher
    Aug 24 at 8:07
  • 1
    $\begingroup$ “In order to get $g^r$ from $g^{rx}$ [the prover] has to solve discrete log”: this is not how the discrete log problem is defined. The DLP asks for the exponent of some element (relative to some fixed base), but here you are asking for the “$x$th root” of the element $g^{rx}$, which is very different. This might or might not be hard to compute, but it’s not the discrete log. Formally, you would need to show a knowledge extractor that computes $x$ after interacting with the prover according to the protocol, and it’s not clear how to do that for this protocol. $\endgroup$ Aug 27 at 11:41

1 Answer 1

3
$\begingroup$

Good question. Note that being "zero-knowledge" means more than "not learning x". It means that you shouldn't learn anything at all from the protocol (this is formalized with the simulation paradigm).

In particular your protocol is not ZK against a malicious verifier. This is easy to see, since the verifier could be choosing some arbitrary group element $f$ instead of $h^r$ and then the verifier would learn $f^{1/x}$. This is some extra information that the verifier isn't supposed to learn.

$\endgroup$
1
  • $\begingroup$ This answer is not quite as satisfying as one might hope for. If we're talking about computational ZK, the simulator does not need to produce $f^{1/x}$, but only something indistinguishable from it. It may not be immediately obvious that that's not possible. $\endgroup$
    – Maeher
    Aug 25 at 7:02

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.