[Cfrg] Hashing to EC group elements

[Robert Ransom <[e-mail]>]

For any odd-characteristic elliptic curve with a rational point of
order 2, the ‘Elligator 2’ injective map described in
<http://elligator.cr.yp.to/elligator-20130828.pdf> can be used to map
an element of the coordinate field to a point on the curve.

If a curve in short-Weierstrass form (y^2 = x^3 + ax + b) has no
rational points of order 2, then x^3 + ax + b is irreducible and the
curve has full 2-torsion over the degree-3 extension of its coordinate
field.  It's straightforward to modify the Elligator 2 formulas to map
to a curve in short-Weierstrass form *given the x coordinate of a
point of order 2*; once one has hashed to a point P over the extension
field, P + f(P) + f(f(P)) (where f is the Frobenius automorphism of
the extension field holding the base field fixed) is a point over the
base field.  (If the input to the Elligator map is in the base field,
an equivalent formulation is to use the Elligator 2 formulas with each
of the three 2-torsion points, and add the resulting points.)


Robert Ransom