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

[Andrey Jivsov <[e-mail]>]

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.

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

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

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.