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

[Watson Ladd <[e-mail]>]

On Sun, Jan 18, 2015 at 11:11 PM, Andrey Jivsov <[e-mail]> wrote:
> On 01/12/2015 11:30 AM, Watson Ladd wrote:
<snip>
> For extended twisted Edwards coordinates (thanks, Mike) I get very similar
> result. I agree with your operation count (according to
> http://eprint.iacr.org/2008/522.pdf):
>
> n=255; w=5; 2^(w-2)*(8*M) + 2^(w-2)*(4*M+4*S) +
> w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(9*M)+11*M + 245*S =
> 1307*M + 1277*S
>
> v.s. Montgomery
>
> n=255; n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S =
> 1350*M + 1265*S
>
> I believe I properly accounted for constants (d in t.Ed is large, would
> costs D=M, a=-1 D=0). The table will include points in extended twisted
> Edwards coordinates. Interestingly, the d is not used in any calculation.
>
> The extended twisted Edwards coordinates, despite having to deal with large
> d, are slightly better (~1.5%) with a simple window exponentiation method.
>
> The comb method doesn't seem to be better.

Combs are better for fixed base mults, not variable base: it takes too
long to do the precomputation.

>
>>
>> But the bottom line is that Montgomery ladder is competitive with the
>> best known alternative methods at 255 bits, in terms of operation
>> counts, and this difference can be wiped out by the need for side
>> channel protection: none of the various models are saying anything too
>> different.
>
>
> Yes, looks like this, if my calculations are correct. The paper mentions
> additional "caching", though.
>
> One argument remains, though. If you plan to do anything beyond ECDH, there
> is a benefit to have the same code that does ECDH, and, say, signing.

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?

Sincerely,
Watson Ladd