Re: [Cfrg] Safecurves draft

[Robert Ransom <[e-mail]>]

On 1/9/14, Bodo Moeller <[e-mail]> wrote:
> 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.

Even if the party which generates a public key uses Edwards-form
points internally for that operation, whoever generates the key can
put it into Montgomery form for free before scaling, whereas whoever
receives it would need to perform an extra coordinate inversion in
order to convert from Edwards form to affine Montgomery form.  (Over
an implementation-friendly coordinate field, projective-base
Montgomery-form point multiplication is always slower than scaling
followed by affine-base Montgomery-form point multiplication.)

I really don't see any benefit to transmitting an Edwards-form point for ECDH.


Robert Ransom