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

[Andrey Jivsov <[e-mail]>]

Thank you, Mike, this is helpful. This brings a few thoughts, below.

On 01/05/2015 01:35 AM, Mike Hamburg wrote:
> Microsoft's benchmarks on Ed-384-mers, and even some of my earlier 
> Ed448 numbers disagree with the Ed448 data above.  My earlier numbers 
> were about 6% less favorable to Montgomery, and Microsoft's numbers 
> were about 10-15% less favorable to Montgomery.  ...
My tests seem to confirm this that Montgomery is 10-15% less favourable 
as well.

>
> So, for larger primes, the Montgomery ladder is probably slightly 
> faster than Edwards when operating on compressed points, and slower or 
> the same otherwise. 

A common assumption is that we need point compression in ECDH, from 
which it follows that Montgomery representation is a wash for p ~ 2^256.

However, for the sake of technical argument let's leave aside the weight 
assigned to "widespread existing practice" and:
* assume that the curve is specified in Edwards form, e.g. as in 
http://www.ietf.org/id/draft-black-rpgecc-01.txt
* assume that the point is sent uncompressed.


This is fine for authenticated keys, e.g. because these will be 
distributed in X.509 certificates, DNS records, etc. Point validation is 
cheaper than decompression in other cases, and this is is how it's 
presently done on the Internet. Optional point compression is also 
well-understood.

* The fixed-base scalar multiplication is very fast, e.g. 15 times 
faster with 5.24 Mb of pre-computed static tables for the 13 bit window.

This is beneficial for protocols or implementation that cannot reuse an 
ephemeral EC key. E.g. a command-line application launched to encrypt 
data, a browser launched with open tabs, etc.

Given that the calculation of a client ECDH share is so fast relatively 
to an ECDH shared secret point calculation, an implementation may as 
well always calculate it fresh. This reduces complexity and fits many 
APIs. This is because there is no need to to maintain a "state" with 
reused ephemeral share.

* The same F(p) and ECC code can be used for signing and ECDH. Also, a 
small d in the Edwards equation is used.

Down the road, something like EdDSA+ECDH, uncompressed points in Edwards 
form, looks like the fastest alternative. Essentially this enables the 
system design with a single ECC primitive that does x*P for same field 
size, which is very fast when P=G, the base point.

* Traditional ECC assumed that one can add points. This may affect 
adoption of the new curve.

This is the case for NIST P-256. It may be desirable to sign with an 
ECDH key, e.g. for proof of key possession, without a special protocol.

* Curves that allow point addition offer space/speed tradeoff option 
through the window size, and other methods.


Unfortunately, the conversion between representations costs ~10% due to 
F(p) inverse. Decompression costs about the same. We also know that the 
performance difference between Montgomery/Edwards operations is in the 
similar range. Therefore, selection of the format on the wire determines 
the implementation. If we are sending a Montgomery x, we are committing 
to Montgomery ladder implementation. Is this justified?