[curves] Unifying public key formats

[Trevor Perrin]

Resuming this discussion...


Background (skip if you've heard this before)
-----------
Curve25519 is conventionally used with single-coordinate "Montgomery
x" public keys for DH, and compressed Edwards coordinates for
signatures.

As the world moves to next-gen curves, it should be considered whether
to keep different formats or move towards a "unified" format.

A unified format might be worthwhile because:
1) It simplifies APIs and protocols
2) Some protocols might want to use a single public key for both DH
and signatures


Options
--------
1) Use Edwards or compressed Edwards for everything.

2) Use Montgomery x and the sign bit of the Edwards x coordinate (i.e.
the Ed25519 sign bit).  Robert Ransom was an early advocate of this
[1].  Sub-options:
  a) always require the sign bit in public keys
  b) allow "DH-only" public keys that omit the sign bit

3) Mike Hamburg's recent proposal [2], which for certain curves (but
not 25519) only encodes and decodes the main subgroup, avoiding
cofactor issues.


Analysis
---------
A lot of people like the efficiency and simplicity of the Montgomery
ladder, so (1) seems less appealing.

I'm not sure how people are feeling about Mike's proposal?

I'll advocate for 2b, because:
 - Existing Curve25519 DH-only public keys are supported
 - DH-only protocols can be built out of DH-only keys and the Montgomery ladder.
 - Libraries that support full-format keys will work with DH-only
protocols and implementations.
 - Full-format keys decode to Edwards coordinates in about the same
efficiency as compressed Edwards format.

I'll try a quick writeup of the last point, based on equations Mike
showed me.  Robert Ransom also explained this in [3]; below will be a
more simplified explanation.


Decoding Montgomery x to Edwards coordinates
---------------------------------------------

First let's look at decompression of a compressed Edwards public key
(y, signbit(x)).  Then we'll consider how decompression changes when
the Edwards y is replaced by Montgomery x.

Consider the Ed25519 equation: -x^2 + y^2 = 1 + dx^2y^2

Given the Edwards y, we can calculate two possibilities for Edwards x,
then discriminate them with the sign bit [4]:

x = sqrt((y^2 - 1) / (dy^2 + 1))

The expensive operations here are the square-root, and the inversion
of (dy^2 + 1).  But inversion and square roots can be calculated using
a field exponentiation, and as shown in [4] Section 5 they can be
"merged" so that a single field exponentiation calculates an inverse
square root.

Given this efficient inverse-square-root function, decompression takes
a single field exponentiation and a few field multiplies:

a = y^2 - 1
b = dy^2 + 1
s = invsqrt(ab)  # s = 1/sqrt(ab)
x = as           # multiplication by a cancels s to sqrt(a/b)
# adjust x based on sign bit

I'll assume the ratio of computation time for field multiplication :
field exponentiation : scalar multiplication is around 1 : 250 : 2500
[5].

So the decompression time is dominated by the invsqrt (field
exponentiation), and decompression is ~10% of the costs of, say, a
signature verify.

Now consider the Curve25519 equation for DH-only keys.  We'll relabel
Montgomery (x,y) to (u,v) for clarity:

v^2 = u(u^2 + Au + 1)

According to the Ed25519 paper, calculating Edwards (x,y) from
Montgomery (u,v) is:

x = Cu/v          # where C = sqrt(A+2)
y = (u-1)/(u+1)

So to decompress (u,signbit(x)) to (x,y) we could calculate y using
this simple equation, then invoke the previously-described Edwards
decompression.  But that adds an extra inversion of u+1, roughly
doubling the decompression cost.

Instead, we can batch this inversion with the others:

a = u(u^2 + Au + 1)  # a = v^2
b = u + 1
s = invsqrt(ab^2)    # s = 1/vb
x = Cubs             # multiplication by b cancels s to 1/v
y = (u-1)abs^2       # multiplication by ab cancels s^2 to 1/b
# adjust x based on sign bit

(To avoid division-by-zero problems, this logic should be preceded by
explicit checks returning (0,-1) for u=0 and rejecting u=-1).

This adds several multiplications, but decompression cost remains
dominated by the single invsqrt (i.e. one field exponentiation).

So compared to overall signature verification, the added compute time
of decompressing from Montgomery x instead of Edwards y is a fraction
of 1%.

Trevor

[1]
http://www.ietf.org/mail-archive/web/cfrg/current/msg04079.html

[2]
https://moderncrypto.org/mail-archive/curves/2014/000343.html
https://moderncrypto.org/mail-archive/curves/2015/000371.html

[3]
http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html

[4]
http://ed25519.cr.yp.to/ed25519-20110926.pdf

[5]
https://www.imperialviolet.org/2013/05/10/fastercurve25519.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg05886.html