<div dir="ltr">A short note on this that may illustrate some of Mike's points: in our lambda-coordinates paper (<a href="http://eprint.iacr.org/2013/131" target="_blank">http://eprint.iacr.org/2013/131</a>), 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.<div class="gmail_extra">
<div><div dir="ltr">--<br>Diego de Freitas Aranha<br>Institute of Computing - University of Campinas<br><a href="http://www.ic.unicamp.br/~dfaranha" target="_blank">http://www.ic.unicamp.br/~dfaranha</a></div>
</div>
<br><br><div class="gmail_quote">On Thu, Mar 20, 2014 at 12:56 AM, Michael Hamburg <span dir="ltr"><<a href="mailto:mike@shiftleft.org" target="_blank">mike@shiftleft.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On Mar 19, 2014, at 6:59 PM, Watson Ladd <<a href="mailto:watsonbladd@gmail.com" target="_blank">watsonbladd@gmail.com</a>> wrote:<br>
<br>
> Dear all,<br>
><br>
> Kim Laine has something to say about genus three curves. I don't know<br>
> what it is, but will report when I hear it in two weeks.<br>
><br>
> On the genus 1 front, what sort of properties do implementors expect<br>
> from point formats? Mike Hamburg argues it's fine to not have a<br>
> bijection, so long as round tripping from point to encoded format to<br>
> point gives the same point on a big encodable subset (think E[q](K),<br>
> not all the rational points. That is, we throw out some small-order<br>
> points). I'm starting to come around to this idea, but some of the<br>
> formats are just wonky and require quite a bit of thought to<br>
> understand or don't work for curve25519, or both. Does anyone have<br>
> explicit formulas for clever formats?<br>
><br>
> Sincerely,<br>
> Watson<br>
<br>
<br>
</div>To clarify slightly what I’m arguing:<br>
<br>
EC protocols usually assume that they are running over an Abelian<br>
group, possibly a cyclic or prime-order one.<br>
<br>
Instead of making your protocol work with E[F], you could make it work<br>
just as easily with E[F] / G, where G is a small subgroup of E[F]. The<br>
protocol’s security just depends on DDH or CDH being hard, and the<br>
G-part of that is easy because G is small. Therefore, it isn’t harmful for<br>
a point encoding to actually encode elements of E[F] / G. When it<br>
decodes, you will get a point in E[F] which is a representative of the<br>
class in E[F] / G. The only downside is that if your protocol compares<br>
points, it must compare them modulo G. If G is the group of order 2<br>
on a complete Edwards curve, this is actually easier than comparing<br>
the points: you just check if x1y2 = x2y1.<br>
<br>
Likewise, you could make your protocol work with a subgroup of E[F],<br>
such as E[F][2q] or E[F][q], and use an encoding that can encode<br>
precisely these points and no others (or otherwise reject them).<br>
Conceivably, these two cases could be combined, using a subgroup<br>
of a quotient.<br>
<br>
This could be helpful for one of two reasons:<br>
<br>
* The subgroup or quotient group might be prime-order. That way you<br>
won’t have to worry about the cofactor in your protocol design.<br>
<br>
* The encoding might be better: it might be faster, or smaller, or<br>
simpler, or easier to use with the Montgomery ladder, or whatever.<br>
<br>
So the upshot is, if it happens that we can construct a point encoding<br>
which either only encodes a subgroup, or loses information about the<br>
cofactor, but it’s otherwise better, then it might be worth using that<br>
encoding.<br>
<br>
Possibilities include the encoding sqrt((y-1)/(y+1)) sign(x), which can only<br>
encode even points; or the encoding x/y, which loses information<br>
about the cofactor; or something similar. Work on these isn’t complete<br>
enough to know whether they’d be “better” than a traditional encoding,<br>
but they are smaller and have some tricks with the Montgomery ladder<br>
which might not be available with a standard encoding.<br>
<br>
— Mike<br>
<div><div>_______________________________________________<br>
Curves mailing list<br>
<a href="mailto:Curves@moderncrypto.org" target="_blank">Curves@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/curves" target="_blank">https://moderncrypto.org/mailman/listinfo/curves</a><br>
</div></div></blockquote></div><br></div></div>