Re: [Cfrg] Curve manipulation, revisited

[Adam Langley <[e-mail]>]

On Mon, Dec 29, 2014 at 6:14 PM, Benjamin Black <[e-mail]> wrote:
> After Yarov and Benger I don't know how robust anyone should assume ladders
> are, though that might be beside the point. Had Dan been insisting that
> ladders be _allowed_ then I would agree with you, as I have said the same
> (in the line just before the part you quoted, even). What Dan said is that
> single-coordinate ladders are _required_. They are not (or, to quote Dan
> again, "False."). X-only on the wire has clear advantages and I support that
> recommendation, but that does not force use of ladders.

I don't see quite how you're understanding Dan's quoted message to
mean that, but I think that everyone would be happy with any technique
that eliminated possible problems.

But, since a working with a windowed multiplication on the Edwards
curve is faster with Curve41417, that opens the question of whether it
would be better to transmit compressed Edwards points for ECDH at that
size.

Tanja did some calculations and the answer appears to be "no": for
41417, it's better to work with Montgomery-X for ECDH rather than do
the square-root to uncompress the point and then use the (slightly
faster) windowed method. So a general rule of "send Montgomery-X on
the wire" appears to be optimal in the cases under consideration,
which is nice.

(The limiting factor for the windowed method is reading from the L1.
The size of the window, and thus the speedup, is limited by the
requirement to read the whole table each step in order that the code
be constant-time. That means that a windowed method with 41417 is only
very slightly faster and thus the square-root cost is sufficient to
tip the balance. Of course, that also assumes that cache-pressure is
free, which it isn't in reality, so the Montgomery ladder is actually
even better than the estimates would suggest.)


Cheers

AGL