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

[Andy Lutomirski <[e-mail]>]

On Mon, Sep 1, 2014 at 11:46 AM, Brian LaMacchia <[e-mail]> wrote:
> Folks,
>
>
>
> Here are the points that must be considered regarding the potential
> selection of a Montgomery form curve (and its realization using the
> Montgomery ladder):
>
>
>
> 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.

Also, can we please stop claiming that things are "clear" problems?
This isn't clearly a problem.  As has been noted as nauseum on this
list, most of the work is in the field arithmetic, and a Montgomery
ladder and, say, Edwards EC arithmetic can share that.

>
> 2.       Assuming that implementations will implement more than one security
> level, choosing X25519 for ECDHE at the 128 bit security level will require
> implementations to use different curve arithmetic for the 128 bit security
> level than other security levels.  Again from an engineering standpoint this
> is a negative.

You're pre-supposing that other security levels wouldn't use
Montgomery coordinates.

[...]

>
> Those arguing for adoption of X25519 are requesting that CFRG
= (a) treat the
> 128 bit security level different from other security levels,

This is the first time that I've seen this request on this list.

> (b) force
> implementations of multiple security levels of key agreement to implement
> different curve arithmetic for different security levels,

I really don't see any justification for this claim.

> (c) force
> implementations of protocols with both key agreement and digital signatures
> to implement different curve arithmetic for those two operations, even at
> the same security level,

This would be an option available to implementers, not a requirement.

> (d) force point conversions between curve forms to
> avoid efficiency loss in ECDHE, and

Now I'm completely lost.  I honestly have no idea what you mean by this.

> (e) to do (a)-(d) for no clear gain in
> performance. These points overwhelmingly contradict arguments in favor of
> forcing the use of the Montgomery form for key agreement, especially for
> only a single security level.
>

--Andy