[curves] Another try at point compression

[D. J. Bernstein]

Tanja and I are catching up on this; we have a few comments and
questions.

It seems that the objective of this system is to efficiently and
uniquely encode elements of an order-l group, where l is a large prime:
specifically, the order-l subgroup G of E(\F_p), where E is an elliptic
curve and #E(\F_p) is a small multiple of l. Efficiency includes being
able to recognize encodings cheaply, something not achieved by the usual
representation of G.

Another way to think of G is as the quotient of E(\F_p) modulo the group
of small-order points: i.e., the set of equivalence classes of points,
where two points are viewed as equivalent if their difference has small
order. For each curve point P, there is a unique small-order point Q
such that P-Q is an element of G.

Why not simply represent an equivalence class C as the maximum element
of C in any reasonable ordering? In other words, why not represent an
element R of G as the maximum R+Q, where Q runs through all curve points
of small order? This is easy to compute (since there aren't many Q's),
and easy to recognize.

Normalization (replacing a point by the maximum point in its equivalence
class) is necessary only before equality tests, outputs, etc., so it can
be done lazily. To add group elements one simply adds representatives.

For example, the case under discussion is an Edwards curve with cofactor
4. The following points are equivalent to (x,y):

   * (y,-x), i.e., (x,y) plus the point (1,0) of order 4; or
   * (-x,-y), i.e., (x,y) plus the point (0,-1) of order 2; or
   * (-y,x), i.e., (x,y) plus the other point (-1,0) of order 4; or
   * (x,y), i.e., (x,y) plus the point (0,1) of order 1.

Exactly one of these points is in G (is killed by p), and is the group
element being represented. Exactly one of these points is in the first
quadrant (the set of (x,y) such that x>=0 and y>0), and is the
representation of that element. Is this representation missing some
feature of the system under discussion?

As an analogy, the group of squares in \F_p is somewhat annoying to
recognize in the usual representation, but there's a much nicer
representation if -1 is not a square in \F_p: simply represent a group
element s as its absolute value |s|. To multiply squares in this
representation one simply multiplies in \F_p, lazily computing absolute
values only when necessary.

---Dan (and Tanja)