Re: [Cfrg] Progress on curve recommendations for TLS WG

[Robert Ransom <[e-mail]>]

On 8/8/14, Ilari Liusvaara <[e-mail]> wrote:

> b) Parameters

> With parameters, random choice is not wise, given that there are very few
> (I think 4 or 2 depending on bitlength[2][3]) rational choices for
> deterministic curve per prime. It would be very hard to reach similar
> rigidity via random process.

> [2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),
> q < 2^n vs. q > 2^n.

There is no trade-off between efficiency in Edwards form and
efficiency in Montgomery form -- a curve with small-integer Edwards d
has its Montgomery (A+2)/4 as the reciprocal of a small integer, which
is as efficient as having (A+2)/4 be a small integer itself.  *ALL*
new curves should be specified with small-integer Edwards d.  (I've
repeated this already recently, and included a link to formulas in
that message.)


The remaining less-than-perfectly rigid aspects that I know of in
selecting a deterministic curve parameter, given the coordinate-field
order p, are:

* cofactors (For p = 3 mod 4, do you settle for curve and twist having
cofactor 8 (as Curve3617 does), or insist on the minimal cofactor 4
(as Microsoft does; note that E-521 also has cofactor 4)?  For p = 5
mod 8, where either the curve or twist must have cofactor 8, do you
operate on the one with cofactor 8 (as Curve25519 does) or the one
with cofactor 4?)

* group size (For p = 3 mod 4, do you operate on the group with
smaller order (as Curve3617 and E-521 do, perhaps by accident, and as
the MSR curves do), or operate on the group with larger order (I don't
think anyone does this)?  For p = 5 mod 8, do you insist that both
groups have order greater than the power of 2 closest to p/8 (as
Curve25519 does, in order to make key generation hard to screw up)?)

* multiplicative embedding degree (Exactly how large, or how close to
maximal, do you insist that the curve's embedding degree be?)

There may be a few others.


Robert Ransom