[Cfrg] Whether the performance advantage of small d needs to affect specifications.

[Adam Langley <[e-mail]>]

As I understand it, we have significant agreement at the ~128-bit
level: Microsoft accepts curve25519 with a different base point and
sending Montgomery-X for ECDH. Everyone else accepts curve25519 with
Montgomery-X for ECDH. (I'm not considering those who want random
primes as the chairs have said that's out of scope for now.)

Since any base point (in the correct subgroup) is as good as any
other, I'm going to make the assumption that significant existing
practice will mean that we can we can all end up accepting x=9 as the
base point.

Where Microsoft still differ at ~128-bits is that they specify an
isogenous twisted Edwards curve with small d, while existing practice
uses an isomorphic twisted Edwards curve with d=-121665/121666.

There is no security difference between these, but there is an
argument that the small d brings a performance advantage—possibly
leading to a tension between existing practice and performance.

However, I think that tension can be resolved by considering a small d
as an implementation strategy. That requires that implementations who
wish to use the isogenous curve be able to convert inputs and outputs
to/from the isomorphic curve very cheaply.


1) A "small d" implementation wishes to perform a scalarmult:

This case is fairly easy I think. At the point that the implementation
is doing the transformation to affine form, it holds extended
coordinates (X, Y, Z, T) where x'=X/Z, y'=Y/Z and x'y' = T/Z. (I'll
write (x', y') for the isogenous curve and (x, y) for the isomorphic
one.)

Rather than calculate 1/Z and then multiply that by X and Y, it can
use different formulas to merge the transform to the isomorphic curve:
x = TZ/(2Z^2 - X^2 - Y^2), y = (Y^2-X^2)/(Y^2+X^2). (I don't have
Sage, Python or even enough paper with me, so I *probably* have the
equations wrong, but the strategy should hold.)

Since the inversions can be merged, the cost is essentially the same
as outputting affine coordinates on the isogenous curve.

For a modified ECDSA with Edward's curves (which Microsoft have
suggested that they want to do), this is sufficient since the
signature contains only scalars. For EdDSA, the paper[1] says that
they skip the decompression of 'R' and check that the encoding of the
other side of the verification equation matches 'R', thus this should
be sufficient there too.

However, let's assume that some protocol needs to decompress points:


2) A "small d" implementations wishes to use a compressed point on the
isomorphic curve.

The inverse transformation for the isogeny is more complex and results
in 4 times the point. It also needs the decompressed point as an input
to the map.

As the Ed25519 paper shows, it's possible to merge an inversion and
square root when decompressing Edwards points such that only a single
field exponentiation is needed. I certainly won't get the equations
for the inverse map correct here, but it appears that they'll end up
needing an inversion and calculation of 'x', which needs a square
root. (The value to invert needs to be independent of 'x', but that
appears to be easy to arrange.)

Call the value to be inverted 'a', and let b=uv^7, which is the value
that we need to raise to (q-5)/8 in order to calculate 'x'. (I'm using
the variable names 'u' and 'v' to match [1].)

Calculate (a^8×b)^((q-5)/8) = c = a^(q-5)b^((q-5)/8). Multiplying by
a^4 will eliminate the 'a' term leaving b^((q-5)/8), as needed for the
'x' calculation.

Now c^8 = a^(7(q-1) + q - 33)b^q-5. Thus c^8×a^31×b^4 = a^(q-2), as
needed for the inversion.

So I think (albeit with the distinct possibility that I've missed
something by not being able to confirm that it works) that a "small d"
implementation can use compressed points from the isomorphic curve
with only a single field exponentiation, which is the same cost as
decompressing points is for implementations of the isomorphic curve
anyway. It does result in 4R, but often that's not a problem, and
could even be an advantage. (Consider ECDH with compressed points on
the wire: since the private scalar is a multiple of 8, the two
low-order bits can just be skipped.)


So, hopefully, a performance advantage of small d, if any, can be
realised even if the isomorphic curve is specified on the wire. Thus
there need not be tension between performance and existing practice
here.

(Time to catch my flight.)

[1] http://ed25519.cr.yp.to/ed25519-20110926.pdf, section 5.


Cheers

AGL

-- 
Adam Langley [e-mail] https://www.imperialviolet.org