Re: [Cfrg] Hashing to EC group elements

["Igoe, Kevin M." <[e-mail]>]

Robert:

  Thanks for the pointer to the paper, I'm enjoying working through it
in more detail.

   One of my coworkers reminded me of the Cardano's algorithm for solving
cubic equations (published in 1545). I'd long ago consigned this to my
ever growing list of interesting but basically useless mathematics.  
It is a deterministic algorithm for solving cubic equations, only
requiring the ability to solve quadratic equations and take cube roots.
At first look this seems to be constant time, might have to stray into
GF(q^6) arithmetic.  We're looking to see if the following idea would work:

	1) Pick an arbitrary y0 on GF(q).
	2) Use Cardano to find a root x0 \in GF(q^3) of x^3 + a*x + b = y0^2.
      3) Apply your I + \phi + \phi(\phi) map to drive (x0,y0) back
         to a point on (x1,y1) \in E/GF(q).

Doesn't give indistinguishability, but it would avoid DragonFly's hunt & peck.
At first glance it looks like it works, but I've learned the hard way to never 
trust anything like this until I've actually programmed it up.

> -----Original Message-----
> From: Cfrg [mailto:[e-mail]] On Behalf Of Robert Ransom
> Sent: Saturday, January 04, 2014 3:56 PM
> To: [e-mail]
> 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.
> 
> 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
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman	/listinfo/cfrg