[curves] Point formats (also, genus 3 coming soon!)

[Michael Hamburg]

On Mar 19, 2014, at 6:59 PM, Watson Ladd <watsonbladd at gmail.com> wrote:

> Dear all,
> 
> Kim Laine has something to say about genus three curves. I don't know
> what it is, but will report when I hear it in two weeks.
> 
> On the genus 1 front, what sort of properties do implementors expect
> from point formats? Mike Hamburg argues it's fine to not have a
> bijection, so long as round tripping from point to encoded format to
> point gives the same point on a big encodable subset (think E[q](K),
> not all the rational points. That is, we throw out some small-order
> points).  I'm starting to come around to this idea, but some of the
> formats are just wonky and require quite a bit of thought to
> understand or don't work for curve25519, or both. Does anyone have
> explicit formulas for clever formats?
> 
> Sincerely,
> Watson


To clarify slightly what I’m arguing:

EC protocols usually assume that they are running over an Abelian
group, possibly a cyclic or prime-order one.

Instead of making your protocol work with E[F], you could make it work
just as easily with E[F] / G, where G is a small subgroup of E[F].  The
protocol’s security just depends on DDH or CDH being hard, and the
G-part of that is easy because G is small.  Therefore, it isn’t harmful for
a point encoding to actually encode elements of E[F] / G.  When it
decodes, you will get a point in E[F] which is a representative of the
class in E[F] / G.  The only downside is that if your protocol compares
points, it must compare them modulo G.  If G is the group of order 2
on a complete Edwards curve, this is actually easier than comparing
the points: you just check if x1y2 = x2y1.

Likewise, you could make your protocol work with a subgroup of E[F],
such as E[F][2q] or E[F][q], and use an encoding that can encode
precisely these points and no others (or otherwise reject them).
Conceivably, these two cases could be combined, using a subgroup
of a quotient.

This could be helpful for one of two reasons:

* The subgroup or quotient group might be prime-order.  That way you
 won’t have to worry about the cofactor in your protocol design.

* The encoding might be better: it might be faster, or smaller, or
 simpler, or easier to use with the Montgomery ladder, or whatever.

So the upshot is, if it happens that we can construct a point encoding
which either only encodes a subgroup, or loses information about the
cofactor, but it’s otherwise better, then it might be worth using that
encoding.

Possibilities include the encoding sqrt((y-1)/(y+1)) sign(x), which can only
encode even points; or the encoding x/y, which loses information
about the cofactor; or something similar.  Work on these isn’t complete
enough to know whether they’d be “better” than a traditional encoding,
but they are smaller and have some tricks with the Montgomery ladder
which might not be available with a standard encoding.

— Mike