Subject: Re: [Cfrg] Curve manipulation, revisited

From: Peter Dettman <[email-masked]>
Date: Thu, 01 Jan 2015 17:16:55 +0700

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.

- Given input X0, use curve equation to calculate {Y0}^2, let K = {Y0}^2.
- Initial point P0 is (X0,{Y0}) where {Y0} is unevaluated.
- Change of variables to an isomorphic curve: x' = u^2.x, y' = u^3.y, a' 
= u^4.a, with u = {Y0} (b' = u^6.b, but not typically needed).
- Can now write P0' as (K.X0, K^2) without unknowns.
- Proceed with scalar multiplication of P0' to result point Pn'.
- Recover output Xn from Pn' as Xn'/(K.Zn^2).

Note that the doubling formula is affected by the changed a' curve 
parameter (unless a==0); assume modified-Jacobian coordinates are used.

In the case where the original curve has a==-3, the extra cost of the 
windowing using the isomorphism in modified-Jacobian coordinates is 
+2S(quares) per addition (doubling cost is unchanged). The total extra 
cost using width 5 windows is therefore < 40% of the best-case cost of a 
sqrt.

However, there are actually good performance reasons to already be using 
an isomorphism: to allow mixed addition with precomputed points without 
needing an inversion in the precomputation. In that case, there is very 
little additional overhead for the scheme above.

Regards,
Pete Dettman

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 7 Jan 2015 10:33:58 -0800

> On Jan 1, 2015, at 2:16 AM, Peter Dettman <[email-masked]> 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.
> 
> - Change of variables to an isomorphic curve: x' = u^2.x, y' = u^3.y, a' = u^4.a, with u = {Y0} (b' = u^6.b, but not typically needed).
> Note that the doubling formula is affected by the changed a' curve parameter (unless a==0); assume modified-Jacobian coordinates are used.
> 
> In the case where the original curve has a==-3, the extra cost of the windowing using the isomorphism in modified-Jacobian coordinates is +2S(quares) per addition (doubling cost is unchanged). The total extra cost using width 5 windows is therefore < 40% of the best-case cost of a sqrt.
> 
> However, there are actually good performance reasons to already be using an isomorphism: to allow mixed addition with precomputed points without needing an inversion in the precomputation. In that case, there is very little additional overhead for the scheme above.
> 
> Regards,
> Pete Dettman

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

---

From: Peter Dettman <[email-masked]>
Date: Thu, 08 Jan 2015 22:00:01 +0700

>> 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 Montgomer…
<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