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

[Paulo S. L. M. Barreto]

On Fri, January 31, 2014 15:50, Mike Hamburg wrote:
>
> 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.

My bad. I only now noticed that Elligator 1 has 2 exceptional points! So,
there are situations (e.g. when p = 5 mod 8) when Elligator 2 has no
exceptional point, and when it does, either Elligator 1 is not defined or else
both have exactly 2 exceptional points (which, in the most straightforward
setting, are precisely the same, i.e. +-1). Nice!

> 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.

You convinced me. If you convince Diego as well, we'll have fun redesigning
the curve-finding script ;-) (actually I wasn't quite happy with them either,
since they don't adopt the more efficient (-1)-twist for Edwards curves)

Cheers,

Paulo.