Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

[Watson Ladd <[e-mail]>]

On Sun, Jan 25, 2015 at 1:35 PM, Andrey Jivsov <[e-mail]> wrote:
> On 01/21/2015 05:39 PM, Watson Ladd wrote:
>>
>> On Wed, Jan 21, 2015 at 1:04 AM, Andrey Jivsov <[e-mail]>
>> wrote:
>>>
>>> On 01/19/2015 04:20 PM, Watson Ladd wrote:
>>>>
>>>> And once again, the Montgomery ladder is extremely small in codesize,
>>>> one the field operations are implemented. Or is there some other
>>>> benefit I don't understand you are thinking of?
>>>
>>>
>>> The benefits of using extended twisted Edwards coordinates would be:
>>>
>>> * An order of magnitude faster key generation (this is a part of
>>> signature
>>> generation or ECDH ephemeral key generation)
>>> * Ability to add points (needed for signatures and many other protocols)
>>> * The same code can do what Montgomery ladder does (variable case
>>> scalarmult) at the same speed.
>>>
>>> It plausible that a library that needs more then ECDH variable base
>>> scalarmult would implement the above operations without the Montgomery
>>> ladder.
>>>
>>> However, if there there is a penalty to recover 'y', that unified
>>> implementation is less likely to happen.
>>
>> And the cost here is what? Note that your first bullet point is false:
>> the comb method on twisted Edwards can deliver a point on a Montgomery
>> curve, with minimal change in performance. I agree we would be using
>> twisted Edwards for signatures and protocols that require addition
>> (although Mike Hamburg has some ideas on safer point formats, based on
>> Jacobi quartics). But that doesn't mean we should use the same method
>> for ECDH: there are security advantages which your proposal doesn't
>> have.
>>
>> Once again this got discussed extensively over the summer.
>
>
> You are proposing to use a Montgomery ladder for second flight of ECDH
> (variable base). There is a benefit of simplicity of code here and
> protection against timing attacks for free, but not much of performance.
> This makes sense.
>
> The first flight of ECDH (fixed-base) is too slow with same implementation
> used for variable base (or any key generation), and so you propose to use a
> discussed over the summer idea to have another type of Montgomery ladder
> (which I couldn't locate). It won't be as simple as the first Montgomery
> ladder and it will probably be more complex as a simple ~20 additions of
> points from a pre-computed read-only table.

Let's look at actual performance numbers, and consider what the
algorithm actually is.

First performance http://bench.cr.yp.to/results-dh.html The Curve25519
implementation presented there outperforms a rather optimized P256
implementation even if we just use the Montgomery ladder for fixed
based exponentiation.

But we can do better via precomputation: what is the algorithm that
lets us do this? Well, we can compute the multiplication in Edwards
form and evaluate the isomorphism or isogeny to Montgomery form. This
was already spelled out January 6th, in Mike Hamburg's email.

Ah, but what if I need more speed? Well, Edwards form isn't faster for
variable time scalarmult. If you want the absolute fastest speed,
Kummer surfaces of genus 2 or GLV/GLS curves are standing by to take
your call.

>
> This, however, still doesn't solve the problem of digital signatures and
> SPAKE, which need to add points.

So we have a different point format for them: again this is what is
being done in SSH right now. Why is this impossible?

>
> For example, in https://tools.ietf.org/html/draft-ladd-spake2-01 each peer
> does 1 fixed-base, 2 variable-base, 2 addition. I would do this with a
> single implementation of a curve formula (e.g. using extended twisted
> Edward).

You seem to be conflating curves, coordinates, and computations, and
then managed to ignore standard speedups Of course, the SPAKE2
protocol needs to preserve the sign of points, and so cannot work with
x-coordinate only Montgomery. But what is the actual cost of SPAKE2?
Firstly, the additions are minimal cost. Secondly, xG+yP is best
computed by an algorithm due to Strauss, and is much closer to 1.5
variable-base multiplications.

When using the comb method, the comb contains affine points, and the
formulas for mixed addition are significantly faster than general
addition. One could of course forgo this increased performance, but
its not clear why one would. Similarly, double-base scalarmult
requires a complete addition law, while for single base one can get by
with an incomplete one that is potentially faster. All these
optimizations are generally implemented and deployed today.

>
> IMO a library like OpenSSL that anticipates to implement most of these
> algorithms *may* consider a single implementation that can add points with
> no performance loss.

But why is that implementation choice so valuable as to justify using
something other than x-coordinate Montgomery? It's not codesize,
except in the most constrained environments.

Sincerely,
Watson Ladd