[curves] The great debate over point formats (Mike Hamburg)

[Mike Hamburg]

On Jan 31, 2014, at 2:13 AM, Paulo S. L. M. Barreto <pbarreto at larc.usp.br> wrote:

> On Fri Jan 31 00:07:44 PST 2014, Mike Hamburg wrote:
> 
>> We could start with x^2 + y^2 = 1 - 14666 x^2 y^2 mod 2^192-2^64-1.
>> The isogenous curve — y^2 = x^3 + 58666*x^2 + x — is isomorphic to
>> y^2 = x^3 - 3*x + 6047900113480193987160910265022055632294672911518856488260.
> 
> I think we discussed this one in private already. Let u := sqrt(-d). Then 2*(u
> - 1)/(u + 1) is not a square, and the Elligator injective map is undefined.

We did discuss this, and I pointed out that Elligator 2 is still defined via the isomorphic Montgomery curve -- and, in fact, for all curves with even order over a large-characteristic field, except with j=1728.  Elligator 2 is easier to implement than Elligator 1, even including the isomorphism, and it's just as fast, and it doesn't have any more exceptional points than Elligator 1.

As a co-author of the Elligator paper, this is my fault for not making it clear enough.  Elligator 2 is a late addition, and the style of the paper is far too cookbook-y, giving no reasons for anything.  I'll try to rectify this in my next paper, and maybe an ePrint post or a blog post on implementation.

This is a large part of why I'm less than happy with the Brazil curves.  They are designed around this idea that comes from the structure of the Elligator paper: use Elligator 1 for Edwards curves with p=3 mod 4 (which constrains your choice of d), and use Elligator 2 with Montgomery curves with p=5 mod 8.  This isn't actually a good design pattern; it's there because Elligator and Curve1174 were already posted to ePrint before we added Elligator 2.  The actual takeaway is, in my opinion, that you can and should use Elligator 2 for either curve shape over either field shape, with any d unless j=1728.

Cheers,
-- Mike