# Zero Knowledge Discrete Logarithm on Elliptic Curves

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$$?

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).
• 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. Jul 19 at 20:43
• 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. Jul 20 at 3:24