Score:0

Zero Knowledge Discrete Logarithm on Elliptic Curves

ph flag

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

Score:1
cn flag

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).

Кирилл Волков avatar
ph flag
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
Geoffroy Couteau avatar
cn flag
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.
Chris Peikert avatar
in flag
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.
us flag
Something like the [Ristretto group](https://ristretto.group/) solves that issue, or you could take the [standardized Ed25519 basepoint](https://crypto.stackexchange.com/questions/27392/base-point-in-ed25519).
Geoffroy Couteau avatar
cn flag
Fixed the confusing statement, hopefully - I had the prime order subgroup in mind when saying "the elliptic curve", which of course is incorrect.
Кирилл Волков avatar
ph flag
@GeoffroyCouteau Thank you very much!!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.