We got a EC group generated with point G, and the cofactor of E(G) is with the similar size of the Order. Now we need a random point of E(G) and not revealing the "logarithm" of the random point, so we don't want to use base point multplication method. The curve equation solved method seems hard to get a valid point of E(G). How can we get such a random point?

  • $\begingroup$ Choose a random x co-ordinate, compute its corresponding y coordinate. If corresponding y co-ordinate does not exist, then choose another random x coordinate $\endgroup$ – satya Jun 20 at 2:30
  • $\begingroup$ Such trail and error is hard to get a valid point in group E(G) because the cofator is too large. And I don't konw how to check such a point with satisfied order is belong to E(G) or not. $\endgroup$ – scv10086 Jun 20 at 2:52
  • $\begingroup$ Not quite enough: need to annihilate cofactor too. $\endgroup$ – Squeamish Ossifrage Jun 20 at 2:52
  • $\begingroup$ If $\#E(k) = h\ell$ for prime $\ell$, then for a uniform random $P \in E(k)$, either $[h]P = \mathcal O$ or $[h]P$ has order $\ell$; since $E(k)$ is a finite abelian group as long as $k$ is a finite field, there's only one order-$\ell$ subgroup and thus $[h]P$ can be reached from any base point in $E(k)$ of order $\ell$. See draft-irtf-cfrg-hash-to-curve-03 for a fairly comprehensive overview of techniques. $\endgroup$ – Squeamish Ossifrage Jun 20 at 3:02
  • $\begingroup$ Thx, that helps a lot. The standard offers effective ways to encode string to point. My question come from pairing application: $e(G_1, G_2)\rightarrow G_T$. We need a random point of $E(G_2)$, while the BN curve $E(F_p)=E(G_1)$ with prime order and the order of its twist curve $E(F_{p^2}) : cY^2=X^3+aX+b$ is not concerned. Are there any effective way to calculate the #$E(F_{p^2})$? $\endgroup$ – scv10086 Jun 20 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.