0
$\begingroup$

Can the Discrete Logarithm ZK be implemented on elliptic curves? It seems that such an implementation should look like the following:

  1. $Y = \alpha G$
  2. Random pick $v$
  3. $t = vG$
  4. $c = H(G, y, t)$
  5. $r = v - cx$
  6. Check: $t = rG + cY$

If yes, can I use ed25519 for this purpose and how can I select $G$?

$\endgroup$
1
$\begingroup$

Yes, this non-interactive zero-knowledge proof works perfectly fine (with a suitable hash function) for proving knowledge of a discrete logarithm over e.g. ed25519. The basis $G$ is part of the statement: the statement is of the form "I know $\alpha$ such that $Y = G^\alpha$. As such, it works for any generator $G$ of your choice (which, over ed25519, is any element of the prime order subgroup except $0$, since its a prime order cyclic group).

$\endgroup$
6
  • $\begingroup$ Great! Thank you! But why G can be any element? As far as I know not all elements of a cyclic group are the generators $\endgroup$ Jul 19 at 17:59
  • $\begingroup$ You are right sorry, I typed too fast - I meant, since ed25519 is a prime order cyclic group, all its elements (beyond the neutral element, i.e., $g^0$) are generators. $\endgroup$ Jul 19 at 20:43
  • $\begingroup$ I think you need to be more careful about the claim that $G$ can be any element on the elliptic curve. The full group of elliptic curve points does not have prime order; it has a small cofactor. So, not every non-identity element is a generator. But every non-identity element of the large prime-order subgroup generates that subgroup. $\endgroup$ Jul 20 at 3:24
  • $\begingroup$ Something like the Ristretto group solves that issue, or you could take the standardized Ed25519 basepoint. $\endgroup$ Jul 20 at 6:48
  • $\begingroup$ Fixed the confusing statement, hopefully - I had the prime order subgroup in mind when saying "the elliptic curve", which of course is incorrect. $\endgroup$ Jul 20 at 8:58

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.