Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

[Robert Ransom <[e-mail]>]

On 1/19/15, Ilari Liusvaara <[e-mail]> wrote:
> On Sun, Jan 18, 2015 at 11:32:57PM -0800, Robert Ransom wrote:
>>
>> * Curve3617 (also known as Curve41417) has cofactor 8, and is defined
>>   over a field of order congruent to 3 mod 4.  Accordingly, the curve
>>   selection procedure in draft-agl-cfrgcurve-00 will choose a
>>   different curve if applied to the field used for Curve3617.  (This
>>   point was previously raised to CFRG in
>>   <http://www.ietf.org/mail-archive/web/cfrg/current/msg05788.html>.)
>>
>>   The curve selection procedure specified in draft-agl-cfrgcurve-00
>>   will instead choose a curve with d > 2^19 (found by D. J. Bernstein
>>   (et al. ?), found again by Mike Hamburg, and found yet again and
>>   published recently by David Leon Gil), compared to d=3617 < 2^12 for
>>   Curve3617.  The parameter value for the twist-secure curve with
>>   cofactor 4 is so much larger than the parameter value for cofactor 8
>>   that the performance of at least one implementation strategy of some
>>   significance would be harmed by insisting on cofactor 4: current
>>   FPGAs contain 18-bit multipliers, and d > 2^19 almost guarantees a
>>   greater cost to multiply by the curve parameter.
>
> I got d=-142113 (#E<p)  (d=142114 if one additionally requires #E>p)
>
> These numbers are 18-bit in absolute value.

Thank you for the correction!  (David Leon Gil had reported a curve in
the isogeny class of a=1, d=-547072.)

I've recomputed the trace of the curve with a=1, d=-142113 using GP,
and it and its twist are indeed of order 4*prime.  The prime-order
subgroup of that curve has maximal multiplicative embedding degree
(r-1), and its twist's subgroup has multiplicative embedding degree
(r'-1)/4; the discriminant of its endomorphism ring is large; and the
factorizations involved in verifying those are fairly easy.


The parameter d=-142113 is still large enough to require more carrying
after multiplication by the curve parameter in an implementation which
uses 16-bit limbs and must reduce limbs to 16 bits each before
multiplication.  I'm not certain whether this would be the case for
FPGA-based implementations, but it is still enough of a difference in
parameter size that I would strongly prefer d=3617 for use with the
point format specified in draft-agl-cfrgcurve-00.


Robert Ransom