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

[Michael Hamburg <[e-mail]>]

> On Jan 11, 2015, at 10:35 PM, Andrey Jivsov <[e-mail]> wrote:
> 
> On 01/11/2015 06:52 PM, Michael Hamburg wrote:
>> Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.
> You are welcome. I would appreciate a pointer to the method.

For the method with lookahead, Hüseyin Hışıl, thesis, http://eprints.qut.edu.au/33233/1/H%C3%BCseyin_Hi%C5%9Fil_Thesis.pdf

For the method with a 5-element accumulator,
https://eprint.iacr.org/2012/309

This is also used in the Goldilocks code.

>> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.
> 
> Right, I was ignoring additions and multiplication by a constant.
> 
> Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in t.Edwards (corresponding to the 37095705...283555 in draft-agl-cfrgcurve-00):
> 
> M: n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S
> tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 1335*S

> 5.4%, 5.5% (M, S). Montgomery is better.

> With small curve constants (A, d), M/4 for the multiplication by these constants:
> M: currently optimal, same 1350*M + 1265*S
> tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M + 1335*S
> 
> 2.2%, 5.5%. Montgomery is better.

If a readd is 8M (or 7M for a mixed add, 1M+1m to convert to readd form) then:

2^(w-2)*((7+1+1/4)*M) + 2^(w-2)*(3*M+4*S + M+M/4) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(8*M)+11*M + 245*S = 1261*M + 1277*S

That’s -12%M, -4%S vs Montgomery.  But the constant-time lookups may nullify that gain.

Cheers,
— Mike