[curves] Another try at point compression

[Mike Hamburg]

Hi curves,

Here is another try at a unified point compression system.  It currently only works for p==3 mod 4, at least for the best properties.  It's related to the others I've suggested, and it came up when I was trying to map potentially cryptographically relevant isogenies and isomorphisms between, eg, Edwards, Twisted Edwards, Huff, Montgomery and Jacobi Quartic curves.  (That’s a WIP...)

---------------------------------

TLDR benefits:
* Unified format can compress and decompress to Edwards, Twisted Edwards and Montgomery curves.
* Presents the illusion of a prime-order curve, i.e. allows us to completely ignore the cofactor (if it's 4).
* Compatible with the Montgomery ladder, I think.
* Always requires one invsqrt and several adds/muls to compress or decompress.
* Encodes every even point on Edwards, Twisted Edwards and Montgomery curve.
* Compresses to ceil(log p) - 1 bits.

Drawbacks:
* Complicated, though not horrible.
* Doesn't work as well with p == 1 mod 4.  Have to come up with a different restriction besides Legendre symbol.
* I haven't worked out the Montgomery ladder formulas yet.  It's probably somewhat complicated, and it probably doesn't include the free twist rejection that Goldilocks gets.
* Needs checking.

---------------------------------

Let J be the Jacobi Quartic curve t^2 = s^4 + (2-4d)s^2 + 1.  Its identity element is (0,1).  It can be shown that if the order of the curve is 4*odd, then t can't b 0 and s can't be +-1.

J is 2-isogenous to the Edwards curve E: x^2 + y^2 = 1 + d x^2 y^2:
  J -> E: 2s/(s^2 + 1), (1 - s^2)/t
  E -> J: x/y, (2 - x^2 - y^2)/y^2

J is 2-isogenous to the twisted Edwards curve T: y^2 - x^2 = 1 + (d-1) x^2 y^2:
  J -> T: 2s/(1 - s^2), (s^2 + 1)/t
  T -> J: x/y, (2 - y^2 + x^2)/y^2

  Note that if T has order 4*odd, then its formulas will be complete on the isogeny's range.

J is 2-isogenous to the Montgomery curve M: y^2 = x*(x^2 + (2-4d)x + 1):
  J -> M: s^2, st
  M -> J: (x^2-1)/2y, (x^2+1)/2x - (x^2-1)^2/4y^2
  *** Actually this is slightly off because it maps the base point to the 2-torsion element, but that doesn't matter at all in the following and I'm too lazy to fix it at a quarter to midnight on a Sunday. ***

Now, J has full 2-torsion.  It acts as follows:
  s,t -> s, t (identity)
  s,t -> -s, -t (kernel of J -> M)
  s,t -> 1/s, -t/s^2 (kernel of J -> E)
  s,t -> -1/s, t/s^2 (kernel of J -> T)

These points have all 4 possible combinations of signs (let's say, Legendre symbols, but you could try to extend the definition to p==1 mod 4).  In particular, for any point P = (s,t) in J, there is exactly one s-value s(P) in the torsion coset where:
 * s is even and finite
 * st is square mod p
Note that for the identity, both (0,1) and (0,-1) are in the torsion coset, but there is only one s coordinate.

Define the compression of P to be all but the bottom bit of s(P).

Define the compression of an even point in M, T, or E to be the compression of either of its preimages (they are in the same coset) under the isogeny.  To compute this for all but the Montgomery curve, we first find s such that st is square, and then make s even by negating s if it's odd (and theoretically, negating t, but we don't compute t).

For E, we have:
  s = (1 + sqrt(1-x^2)) / x,
  where the square root is taken with the same Legendre symbol as -2y.
  The 4-torsion points have x=0, but they encode to 0 anyway.
  Doubling and calling this amounts to either x/y or y/x, but to figure out which you need to compute a Legendre symbol.

For T, we have:
  s = (-1 + sqrt(1+x^2)) / x,
  where the square root is taken with the same Legendre symbol as 2y.
  The 4-torsion points have x=0, but they encode to 0 anyway.
  Doubling and calling this amounts to either x/y or y/x, but to figure out which you need to compute a Legendre symbol.

To decompress, just compute t from the curve equation, with the same symbol as s, and then run the isogeny.  This can be done to affine with one invsqrt, but in pratice you'll probably do it to projective anyway.

For M, we may need something more creative.
  It is easy to square S to get to M, then ladder the square.  But how do we recompress, when that's desired?

The isogeny to M kills the (s,t) <-> (-s,-t) map that made our lives easier above.  Perhaps the easiest thing is to compute whether y is square at the end.  There is an ugly but non-obscene formula which computes the Legendre symbol of ybegin * yend, and ybegin is always square.  If yend is also square, compute s = sqrt(x), and otherwise, compute s = sqrt(1/x).  This can actually all be batched up together, at least if the scalar is adjusted to be odd, but it's still pretty complex and I haven't worked it out yet.

Anyway, thoughts?  Is this sort of thing worth pursuing?  Is there a way to make the Montgomery ladder nice?

Cheers,
-- Mike