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