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=92ve 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. =20 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 =3D = 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=20 trust anything like this until I've actually programmed it = up.

Unfortunately, this doesn=92t work. I =
recalled analyzing it before during the Elligator work, but anyway I =
just tested it in Sage to be sure. If x0 isn=92t in GF(q), you=92ll =
end up on a cubic twist of E. When you frob from that twist back =
to the base field, you=92ll 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=92s a =
better solution, outlined in a series of papers, most notably BCIMRT =
=9209:

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 =
=93indifferentiability=94.

I believe that full =
indifferentiability isn=92t needed for Dragonfly, though I=92m 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=92t good enough, then =
setting (r1,r2) =3D hash(password) and running =
either

Encode(password) :=3D SWU(r1) + =
SWU(r2)

or

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

is indifferentiable from a random oracle, and =
is therefore suitable for use anywhere that you=92d 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=92t be =
that horrible to implement.

Cheers,

=97=
Mike Hamburg

=
--Apple-Mail=_52957CD7-8990-4E7C-835B-FC347C5BCC7E--