Re: [Cfrg] Safecurves draft

[Bodo Moeller <[e-mail]>]

Robert Ransom <[e-mail]>:

> On 1/9/14, Bodo Moeller <[e-mail]> wrote:
> > In that context, given that the name
> > "Curve25519" is already overloaded, and that we probably should make the
> > Edwards representation available for DH too (in addition to EdDSA),
>
> No.  Montgomery-form variable-base single-scalar multiplication takes
> 5M+4S per scalar bit; Edwards-form doublings alone (in ‘extended
> coordinates with a=-1’) are 4M+4S (or 3M+4S if the output will only be
> used as input to another doubling).


As pointed out by Section 6 in http://eprint.iacr.org/2007/286.pdf,
sliding-window multiplication using the Edwards form can be faster than
5M+4S per scalar bit for this curve (although that's probably no longer
true if you want a constant-time implementation -- while the non-sliding
window approach in Section 8 doesn't seem optimal because it's not making
use of signed windows, I don't think the extra savings are sufficient to
beat the Montgomery ladder).  More importantly, if you have a *fixed* base
(which is very relevant for ephemeral ECDH), with appropriate fixed
precomputation you won't need any double operations at all: so the total
time for one fixed-base single-scalar multiplication and one variable-base
signal-scalar multiplication as used in ECDH can be less than with the
Montgomery ladder, even if you want constant time with no secret-dependent
branches.  If you have severe space constraints, then an approach that
involves a few hundred precomputed points is not for you, but in many
typical scenarios this is not an issue at all.

So while the Montgomery-form Curve25519 certainly has its use, allowing
applications to negotiate a different form for ECDH would be beneficial.

Bodo