Re: [Cfrg] On the use of Montgomery form curves for key agreement

[Robert Ransom <[e-mail]>]

On 9/1/14, Brian LaMacchia <[e-mail]> wrote:
> See responses inlined below
>
> -----Original Message-----
> From: Andy Lutomirski [mailto:[e-mail]]
> Sent: Monday, September 1, 2014 11:55 AM
> To: Brian LaMacchia
> Cc: [e-mail]
> Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
>
>>> 1.       Requiring a Montgomery form curve for key agreement and for a
>>> particular security level means that implementations of protocols with
>>> both key agreement and digital signatures must implement both
>>> Montgomery curve arithmetic and additionally curve arithmetic for
>>> another curve form.  From an engineering perspective there is thus a
>>> clear drawback to requiring different curve forms for key agreement
>>> and digital signature at the same security level.
>
>>You can do arithmetic on a curve points given in Montgomery form without a
>> Montgomery ladder >implementation by converting to a different coordinate
>> system.  I'm not sure why you'd want to in >anything other than the
>> tiniest embedded implementation, but you could.
>
> Yes, technically you could do that, but I haven’t seen anyone suggest that
> was in any way practical or interesting.

I've suggested that
(<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>).

To summarize:

* If the point format contains an Edwards-form y coordinate instead of
a Montgomery-form x coordinate, implementations which use the
Montgomery ladder, for whatever reason, must incur a significant extra
cost.  (The Montgomery ladder is far simpler than the algorithms you
recommend, and can be implemented with far less RAM than any tolerably
efficient scalar-multiplication routine based on Edwards form, so many
implementations will use the Montgomery ladder in practice, and some
implementations must use it.)

* If the point format consists of a Montgomery-form x coordinate
(possibly together with a sign bit for an Edwards-form x coordinate),
point decompression to projective Edwards (or twisted Edwards) form
costs only trivially more.  There is a small added cost over Dr.
Bernstein's ‘Curve41417’ ECDH implementation (but only because it is
sub-optimal), and essentially no added cost for your algorithms (which
must double their input before table construction).


(I do believe that using Edwards-form point formats in the Ed25519
signature system and the Curve41417 ECDH system was a bad decision --
in particular, if Ed25519 had used a Montgomery-form point format
instead, it would have been far more convenient for many applications
-- but I disagree strongly with your claim that using a different
point format for a signature system's nonces is inherently bad.  I'll
post more details about that at some point, hopefully soon.)


>  To be clear, the reason you would
> want to change to another form in ECDHE is for significant performance gains
> in the fixed-base key generation.

This is false, and you clearly know that: your own research group's
paper gives performance figures for a ‘hybrid’ ECDHE implementation
which uses Edwards form internally for key generation, and uses the
Montgomery ladder for the variable-base scalar multiplication.

(For everyone else, the added cost (during key generation) of encoding
a projective Edwards-form point to a Montgomery-form point format
rather than an Edwards-form point format is trivial: two additions.)


Robert Ransom