[curves] Unifying public key formats

Mon Jan 19 16:16:34 PST 2015

Nice summary ...

On 1/19/15, 3:24 PM, "Trevor Perrin" <trevp at trevp.net> wrote:

>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
+1 - yes, public keys as a building block should be capable of supporting
signatures and DH

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

DH is used commonly and often ephemeral - no need to uncompress.
2)b is appealing so as to match current DH usage and support compression.
However, are we leaking one bit of info in the compressed bit if is there
or not there?
Seems like it would identify a long term from an ephemeral key Š.

Do we need to ensure the integrity of a sign bit if it¹s only there
sometime?
Would the DH exchange need to use the no-compress/sign-plus/sign-neg
indication to ensure integrity?

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

So, to be clear the Montgomery format would be augmented to include the
Edwards y-coordinate sign bit.
Versus - sign bit of Montgomery y which matches prior ANSI/NIST
compression.

No objection - just restating to make sure i understand the implications.

>
>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%.
Protocols that have longer term keys would only need the conversion once.
A very reason performance tradeoff.

Paul

>
>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
>_______________________________________________
>Curves mailing list
>Curves at moderncrypto.org
>https://moderncrypto.org/mailman/listinfo/curves