On Mar 19, 2014, at 6:59 PM, Watson Ladd <[email protected]> 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 [email protected] https://moderncrypto.org/mailman/listinfo/curves
