Re: [Cfrg] Fwd: Re: Safecurves draft

[Manuel Pégourié-Gonnard <[e-mail]>]

On 09/01/2014 10:50, Robert Ransom wrote:
>> About names, I'd really like the names to reflect the type of the curve
>> (Montgomery or Edwards). This is already the case for other curve families,
>> by
>> the way. So, Mxxx and Exxx seem great to me. I'd even go so far as to rename
>> Curve25519 as M255, but I'm sure there are good reasons to disagree on this
>> point.
> 
> Remember that Curve25519's parameter is *not* minimal subject to the
> constraint of twist security with minimal cofactors -- Dr. Bernstein
> considered a slightly more subtle criterion regarding the group orders
> too.  Keep that in mind if you try to establish a systematic name for
> Curve25519.
> 
I'm not sure it goes against my argument that the name should reflect the type
of the curve. Or did I miss something?

> I don't see the benefit of defining both a ‘safe’ Montgomery curve
> (for the present definition of “safe”) and a ‘safe’ Edwards curve over
> the same coordinate field -- every Edwards curve with minimal
> parameter can be used efficiently with Montgomery's formulas.  (The
> Montgomery-form parameter becomes the reciprocal of a small integer,
> which can be handled as efficiently as a small integer itself.)
> 
> (For that matter, I would suggest replacing Curve25519 with the
> twisted Edwards curve a=-1, d=121665 over the same field in any new
> application or standard.)
> 
An interesting point.

> Issue 2 is obviated by twist security for single-scalar multiplication
> of a Montgomery-form x coordinate.  It remains relevant for any
> application which operates on full points (whether transmitted
> uncompressed or compressed).
> 
Absolutely. There was a hidden assumption that only the x coordinate be used in
my statement. Actually, I think it reinforces my point that the curves aren't
"magically" safe regardless of the how they are implemented or used in a
protocol: indeed, the fact that no public key validation is needed depends not
only on the curve (twist security), but also on the protocol (x coordinate only).

>> and to be fair point 4 is a bit easier to
>> address
>> with these curves too.
> 
> Why 4?  The benefit of complete addition formulas is that
> implementations don't need to switch to a doubling routine when two
> points are equal.  Nothing about SafeCurves makes constant-time table
> lookups any easier.
> 
Right, I was making an unstated assumption again, sorry for that. The assumption
was that other curves are more likely to use a larger table for performance,
while a Curve25519 implementation will generally use a ladder with no
precomputed table, so it will only have to safely swap two points, which is less
expensive than doing a constant-time lookup in a larger (say 16 or 32 points)
table. So it lessens the performance vs security conflict.

Manuel.