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) _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
