Re: [Cfrg] Curve selection revisited

[Robert Ransom <[e-mail]>]

On 7/25/14, Watson Ladd <[e-mail]> wrote:
> Thanks for the much more detailed analysis: I'll have to revise my opinion.
> On Fri, Jul 25, 2014 at 7:25 PM, Robert Ransom <[e-mail]>
> wrote:
>> On 7/25/14, Watson Ladd <[e-mail]> wrote:

>>> The second question and third question what coordinates and what
>>> addition formulas to use when, and what algorithm to use. All twisted
>>> Edwards curves expose the same possibilities here: large precomputed
>>> tables with mixed coordinate addition vs. smaller tables for variable
>>> base, or a conversion to some other isogenous curve for variable base
>>> exponentiation.
>>
>> Affine Montgomery-form points can be unpacked to and packed from
>> projective (optionally twisted) Edwards-form points at a trivial extra
>> cost over unpacking from or packing to a compressed affine
>> Edwards-form point.  Variable-base scalar-multiplication operations
>> which use Edwards form internally are not slowed significantly by
>> having a projective rather than affine input (if any operations rely
>> on their input being affine, they must occur during table setup), and
>> they are not slowed at all if they double and/or apply isogenies to
>> clear the cofactor group before operating on an ‘incomplete’ curve
>> (e.g. a=-1 in a field in which -1 is a non-square).
>
> I think I follow all the way up to the last phrase: the incompleteness
> means some
> additions might blow up, complicating the analysis, and I think a=-1
> only gives the twist
> if -1 is a nonsquare.

I'm not talking about using the twist.  I'm talking about mapping from
the ‘complete’ Edwards/Montgomery curve which the specification states
and simple implementations use to an ‘incomplete’ curve (i.e. a
(twisted) Edwards curve with non-affine points defined over the base
field), by whatever means (isomorphism or isogeny), on which the
unified addition formula has exceptional cases for inputs with even
order.  When this is a useful thing to do -- i.e. when the curve is
defined over a field in which -1 is a non-square, and thus (twisted)
Edwards curves with a=-1 are always incomplete -- there is almost
always more than one suitable curve to map to.  For example, Mike
Hamburg suggests in <https://eprint.iacr.org/2014/027.pdf> a 4-isogeny
from Ed(1,d) to Ed(-1,d-1); when d is a non-square, there is also an
isomorphism from Ed(1,d) to Ed(-1,-1/d).

My point is that most implementation strategies which want to *use* an
incomplete Edwards curve start with operations which (a) modify the
original input point such that it is guaranteed to have odd order, and
(b) produce a non-affine result, which all further operations use as
their input.  Because of (b), using a Montgomery-form input point
format in such an implementation has almost no performance cost (only
a few multiplies).


Dr. Bernstein's Curve3617 implementation (he now wants to call it
Curve41417) operates on a complete Edwards curve; its implementation
strategy is more complex than the Montgomery ladder, and slightly less
complex than one using an incomplete curve.  As a consequence, it
benefits more than the fastest implementation strategy from having an
affine Edwards-form input point: it saves an additional 7M in the
process of constructing a 15-element table.  I don't think this
benefit to exactly one sub-optimal implementation strategy justifies
the cost to the simplest implementation strategy (the Montgomery
ladder).

> Otherwise it is a curve isogenous to the
> original one, under a 1-isogeny.

The proper term for a ‘1-isogeny’ is “isomorphism”.  Otherwise, people
will think that “isogeny” is just the term used for an isomorphism
between elliptic curves, rather than a very different type of map.


>> As you should know, fixed-base scalar-multiplication operations which
>> use Edwards form internally are not slowed at all by producing
>> Montgomery-form output.
>>
>> Affine Edwards-form points cannot be unpacked to affine
>> Montgomery-form points for use with the Montgomery ladder without an
>> extra inversion at the beginning of a scalar multiplication, and using
>> a projective input in the Montgomery ladder is always slower than
>> inversion by coordinate exponentiation.
>>
>> Since the Montgomery ladder remains the simplest implementation
>> strategy, and the performance benefit to more complex implementations
>> from using an Edwards-form point format is small at most, I still see
>> no reason to use an Edwards-form point format.
>
> Signatures: the y-encoding strategies I've seen are too clever by
> half, so keys for
> ECIES and signatures look very different.

What do you mean by this?

> There is no security issue
> with reuse and
> there are papers to that effect, or so I'm told.
> That said adding Edwards support or Montgomery support to an implementation
> of the other partner in the isogenous pair is easy: we can live with
> two point formats.

“Easy” does not mean “low-cost”.  Adding support for Edwards-form
input points to a Montgomery-ladder implementation is easy, but has a
high performance cost (1I per scalarmult).  Adding support for
Montgomery-form input points to an implementation which operates on
Edwards form is easy, and has much smaller performance cost.


> (there is an additional question of small parameters: a Montgomery
> curve with small
> parameter is birationally equivalent to a twisted Edwards curve of
> small parameter, but
> the converse is not (obviously) true. Most generated curves seem to be
> in Edwards form
> however.)

Curve25519 chose (A+2)/4 to be a small integer because Edwards curves
had not been published yet.  All new curves should be chosen to have
Edwards d be a small integer, because that makes the Edwards-form
unified addition formulas faster at no cost to the Montgomery ladder
on the isomorphic Montgomery curve.  (I've mentioned this to CFRG
before; I wish more people had listened to me.)

>>> one caches ephemeral DH
>>> parameters so the cost of fixed-base exponentiation is amortized
>>> across connections. OpenSSL does this anyway, and this affects
>>> technique
>>> slightly.
>>
>> This is good for performance even if you use a table to optimize
>> fixed-base scalar multiplications.
>
> Very true: the NUMS performance results are thus dead wrong in ECDHE costs,
> which are two variable-base multiplications plus a very amortized
> fixed-base multiplication, not
> the fixed+variable base they used.

I don't see anything wrong with what MSR states as the cost of ECDHE
-- they're consistent across the implementations, and not reusing
ephemeral keys is the simplest implementation strategy.  (If they did
change their figures to take key reuse into account, though, the cost
would be only one variable-base scalar multiplication, not two.)


Robert Ransom