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

[Diego Aranha]

A short note on this that may illustrate some of Mike's points: in our
lambda-coordinates paper (http://eprint.iacr.org/2013/131), we use an
encoding (x, \lambda = x + y/x) that automatically excludes points of small
order in our GLS binary curve, simply because they have a non-invertible x
= 0.
--
Diego de Freitas Aranha
Institute of Computing - University of Campinas
http://www.ic.unicamp.br/~dfaranha


On Thu, Mar 20, 2014 at 12:56 AM, Michael Hamburg <mike at shiftleft.org>wrote:

> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140320/2dd67998/attachment.html>