Subject: [Cfrg] Hashing to EC group elements

From: Robert Ransom <[email-masked]>
Date: Sat, 4 Jan 2014 12:55:50 -0800

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

---

From: Paul Lambert <[email-masked]>
Date: Mon, 6 Jan 2014 12:47:57 -0800

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Robert Ransom
> Sent: Saturday, January 04, 2014 12:56 PM
> To: [email-masked]
> Subject: [Cfrg] Hashing to EC group elements
> 

Interesting.

> 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
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Wed, 8 Jan 2014 19:38:36 +0000

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.

> Sent: Saturday, January 04, 2014 3:56 PM
> To: [email-masked]
> http://www.irtf.org/mailman	/listinfo/cfrg