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

[Robert Ransom <[e-mail]>]

On 9/2/14, Brian LaMacchia <[e-mail]> wrote:
> -----Original Message-----
> From: Robert Ransom [mailto:[e-mail]]
> Sent: Tuesday, September 2, 2014 12:25 AM
> To: Brian LaMacchia
> Cc: Andy Lutomirski; [e-mail]
> Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
>
>>On 9/1/14, Brian LaMacchia <[e-mail]> wrote:
>>>  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.)
>
> Hi Robert,
>
> I think you misread that portion of my email as being about the cost of
> conversion between coordinate formats, when I was in fact referring to the
> overall “hybrid” implementation.

I'll quote that portion again, with all possible context:

>>> 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.  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.

I interpret “change to another form in ECDHE” to mean “change the
ECDHE protocol to use another form” (in context, a form other than
Montgomery form).  I still consider that to be the most reasonable
interpretation of that phrase, given the full context.

If you meant “convert a point used in ECDHE to another form” (other
than Montgomery form), then your statement is poorly worded and still
clearly false: the performance improvement that you are referring to
for fixed-base scalar multiplication relies on the base point being
provided in the form of a precomputed table.  The cost of converting a
base point into that ‘format’ is greater than the benefit can possibly
be for a single operation, so you cannot possibly be referring to the
table precomputation as ‘chang[ing] to another form *in ECDHE*’
(emphasis added).


>  If you go back and reread the entire
> message, you’ll see a more detailed comment on exactly this point at the
> bottom of my reply to Andy.

I did see that.  However:

* Your research group only considered one type of processor in its
benchmarks, and made all design decisions based on the performance of
its implementations on that processor.  The results do not show which
point format (or coordinate-field shape) will provide the best
performance in a small processor (or other device) with limited
memory, or in a processor with no (or small) cache RAM.  (I expect
that some implementations will be forced to use the Montgomery ladder
even for signature verification, due to extreme memory or cache
limitations.)

* Your research group didn't know that the Montgomery ladder can
tolerate leading zero bits, so they implemented the Montgomery ladder
with an unnecessarily long scalar.  As a consequence, I don't trust
your initial benchmarking results for the Montgomery ladder.  Have you
corrected that implementation issue and published new benchmark
results?

* Your research group's paper did not, as of the last time I read it,
explicitly state whether the twisted-Edwards-form benchmark results
used compressed or uncompressed points.  As Dr. Bernstein has pointed
out, specifying an uncompressed point format in a standard meant to
have multiple independent implementations introduces the risk that
someone will omit input validation, so I would oppose the use of an
uncompressed point format in any IETF protocol.  Do your benchmark
results for twisted-Edwards ECDHE include the cost of point
compression?

(Disclaimer: I've implemented software which uses uncompressed
Edwards-form points; I now believe that both “uncompressed” and
“Edwards-form” were bad design decisions.)


Robert Ransom