Re: [Cfrg] Curve manipulation, revisited

[Peter Dettman <[e-mail]>]

On 8/01/2015 1:33 am, Michael Hamburg wrote:
>> On Jan 1, 2015, at 2:16 AM, Peter Dettman <[e-mail]> wrote:
>>
>> On 29/12/2014 8:31 pm, Adam Langley wrote:
>>> (An implementation that wants to use a windowed method with a Montgomery-X *input* will need to perform a square-root first, but that's the same cost as a design where compressed Edwards points are sent. Note: smarter people than I might be able to eliminate the square-root but I don't see it)
>> I believe I can give an example of how to eliminate the square-root for a random-base scalar-mult. I'll use short Weierstrass to describe it though, as I'm less familiar with Edwards and Montgomery. I assume we can convert easily enough between forms, and that twist security carries across.
<snip>
> This is neat. Have you tested it? Does it work, and do you know if 
> it’s better than a Montgomery ladder? From your high-level description 
> it looks like it should be competitive with the short Weierstrass XZ 
> Montgomery ladder (8M + 7S + 5m IIUC). Cheers, — Mike 

I did some basic tests of the sqrt-avoiding isomorphism using secp256k1 
(a==0 makes the testing easier) and it works, yes.

Regarding performance, I can give numbers from a modified version of the 
Granger/Scott P-521 implementation; there I changed the precomputation 
so that all the precomputed points would have a common Z, then used an 
isomorphism on which those points are affine, and switched to 
modified-Jacobian coordinates. That scheme is 3M + 5S for doubling, 7M + 
6S per point addition, 9M + 3S per precomputed point, plus a handful of 
ops to shift to/from the isomorphic curve. So, with width 5 windows, I 
make that roughly (4.7M + 6.2S)/bit for P-521, or for something around 
256 bits, (5M + 6.3S)/bit.

The sqrt-avoiding scheme would have the same per-bit cost as above, with 
a few extra ops at the start/end.

Regards,
Pete Dettman