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

[Andrey Jivsov <[e-mail]>]

On 01/25/2015 08:16 PM, Watson Ladd wrote:
> 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.

Yes, but P256 is not a subject this this thread.

( For P256 v.s. Curve25519+Montgomery I timed that in
https://www.ietf.org/mail-archive/web/cfrg/current/msg05211.html and 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05251.html : up to 
65% faster )

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

I think this will have a ~10% performance penalty due to y missing.

There was no free way to recover y noted. E.g., if we start with 
Montgomery Z!=1, as Mike Hamburg observed, it is cheaper to perform an 
inverse first than to use ( X, Z!=1 ) in the Montgomery ladder formula 
(because squaring is faster than multiplication), and so on.

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

I wonder if this will be worth the benefit (in a single thread).

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

There are benefits to have single implementation (that can add points).

However, regarding the wire format, it may be desirable for an 
encryption key to sign (think OpenPGP top-key only, proof of key 
possession, etc). Ignoring the "existing implementation practice", 
defining the Montgomery (x,y) as the point representation allows to do 
signatures, or encryption, and have single implementation, without 
performance penalty to recover y.

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

Hm, 1.5 variable base multiplication doesn't seem appealing here, 
because xG is a factor of 10 faster than yP (for a reasonable 
precomputed table for ~256 bit F(p)) with EC formula that can add points).

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

It's system simplicity. One then needs to implement, tune, and debug a 
single implementation.

(Single) Montgomery ladder is an excellent implementation strategy for 
many applications. If these applications' needs are served by the 
Montgomery ladder -- they should use a Montgomery ladder.


> Sincerely,
> Watson Ladd
>