Re: [Cfrg] Hashing to EC group elements

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Ransom
> Sent: Saturday, January 04, 2014 12:56 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] Hashing to EC group elements
> 
> 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.

Interesting.

> 
> 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.)
May seem easy to you ... could you help to provide more explicit formulas.
For example, for x1 and y1 below ...

def elligator(curve, element):
    """ Maps an arbitrary element to a point on the curve """
    assert 0 < element < curve.p  # p is prime order of curve
    assert curve.type = 'smallWeirstrass'

    x1 = 
    y1 = 
    return curve.point(x1,x2)

Paul

> 
> Robert Ransom
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg