[curves] Another try at point compression

[Michael Hamburg]

> On Dec 24, 2014, at 5:26 PM, D. J. Bernstein <djb at cr.yp.to> wrote:
> 
> 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.

Yes.

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

Its ease of recognition depends on the format.  For example, if you use an Edwards curve, then the orbits are trivial to compute so recognition is easy, but with a Montgomery curve it requires inversion.

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

Yes, that’s the idea.  This is strictly a an encoding format; all group computations would be done much as before.

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

Yes, it is missing a few.

* The system under discussion compresses points.  Lexicographic ordering doesn’t work for compression, because given eg x, both possible y-coordinates are likely to be the lex minimum within their orbits.

* The system under discussion can only encode even points.  This means that in a cofactor-4 twisted Edwards curve with a=-1, the addition formulas are complete.

* The system under discussion is (maybe, perhaps with some extra complexity) is compatible with the usual Montgomery ladder on Montgomery curves.

* Largely just a curiosity, but the original system under discussion is simultaneously an encoding of E_{1,d} and E_{-1,d-1}.

* Parity is simpler to check than ordering.

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


Yes, exactly.  And you don’t have to run the encoding to check if two points are equivalent.  If you’re using the system under discussion, both points are known to be even (on the untwisted Edwards curve), and it’s as simple as whether x1 : y1 = x2 : y2 instead of also checking the : z component.  If they’re not both known to be even, you have to also check if x1 : y1 = -y2 : x2.

Merry Christmas,
— Mike