[curves] Point formats (also, genus 3 coming soon!)
Michael Hamburg
mike at shiftleft.org
Wed Mar 19 20:56:08 PDT 2014
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
More information about the Curves
mailing list