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

[Watson Ladd <[e-mail]>]

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.

Sincerely,
Watson Ladd