Re: [Cfrg] Hashing to EC group elements

[Michael Hamburg <[e-mail]>]

Hello CFRG,

It might be time to unlurk here.  Trevor Perrin asked my opinion of this topic, and since I was a co-author on Elligator, I’ve studied the matter.

Kevin Igoe wrote:
> 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.
Unfortunately, this doesn’t work.  I recalled analyzing it before during the Elligator work, but anyway I just tested it in Sage to be sure.  If x0 isn’t in GF(q), you’ll end up on a cubic twist of E.  When you frob from that twist back to the base field, you’ll just get the identity.

I believe that the Elligator version of this, proposed by Robert, does work at least if the input to Elligator is chosen uniformly from the extension field.  However, it would be pretty horrible to implement.  Fortunately, there’s a better solution, outlined in a series of papers, most notably BCIMRT ’09:

http://eprint.iacr.org/2009/340.pdf

This paper outlines how to hash deterministically to an elliptic curve, while maintaining the ability to model the hash as a random oracle.  This property is called “indifferentiability”.

I believe that full indifferentiability isn’t needed for Dragonfly, though I’m not sure of it.  In this case, a good candidate would be the SWU maps, of which some simple variants are in the BCIMRT paper.  These maps map a field element to any curve over that field, deterministically but not indifferentiably, uniformly or injectively.  However, they are at most 8-to-1 or something like that, and that might be good enough for Dragonfly.

If this isn’t good enough, then setting (r1,r2) = hash(password) and running either

Encode(password) := SWU(r1) + SWU(r2)
or
Encode(password) := SWU(r1) + r2 * G

is indifferentiable from a random oracle, and is therefore suitable for use anywhere that you’d use one.  The SWU maps are comparable to Elligator, but not 1:1.  In fact, Elligator 2 at least can be seen as a simplified SWU variant that only works on curves of even order.  So these techniques shouldn’t be that horrible to implement.

Cheers,
— Mike Hamburg