1

The question is the same as: is elliptic curve cyclic? how to prove it?

update

Seems the above answer is no.

But I've a further question(maybe should post another thread?).

Is there a bounding for the order of a random point on an elliptic curve? Many zero knowledge algorithms choose a point randomly, I guess there should be a low limit ?

omg
  • 147

1 Answers1

0

If you need to produce random points of large order, the standard approach is to use a fixed, known curve of prime order (which is then guaranteed to be cyclic), and choose random points on that curve.

Do not fix a point $P$ and then choose random integers $k$ and output $kP$, as suggested in one of the comments. This approach is insecure for many protocols.

A definitive resource for this topic is How to hash into elliptic curves by Icart, published in CRYPTO 2009.

djao
  • 1,119
  • Can you briefly tell why is it insecure? – omg Feb 24 '22 at 13:26
  • Random point on the curve – kelalaka Feb 24 '22 at 13:47
  • Consider BLS signatures (https://en.wikipedia.org/wiki/BLS_digital_signature). You are supposed to hash the message $m$ to a point $h$ and output the signature $h^x$. Suppose instead that you hash the message to a point $g^k$ where $k = H(m)$. Then any party can forge the signature of $m$ by outputting $z^k$ where $z = g^x$ is the public key. – djao Feb 24 '22 at 14:52