Re: [Cfrg] draft-ladd-safecurves-02

[Michael Hamburg <[e-mail]>]

On Jan 10, 2014, at 11:25 AM, Watson Ladd <[e-mail]> wrote:

> On Fri, Jan 10, 2014 at 11:20 AM, Trevor Perrin <[e-mail]> wrote:
>> On Fri, Jan 10, 2014 at 11:11 AM, Watson Ladd <[e-mail]> wrote:
>>> Added: explicit formulas and a point format (big endian with a bit for
>>> the missing coordinate).
>> 
>> I don't see the draft yet, but if you're including point formats, any
>> thoughts on Jivsov's trick?
>> 
>> http://tools.ietf.org/html/draft-jivsov-ecc-compact-03
> 
> Assumes short Weierstrass form. I did put in x coordinate only for
> Montgomery, but it's not the same thing.

Well, you can do it in any coordinate system where negating one coordinate negates the point.  You just have to change section 4.3 to use the curve’s formula instead of the short Weierstrass formula.  For example, you can do it with Edwards curves and negate x instead of y.

This trick is neat, but it saves only one bit, and restricts to a subset of EC points.  You can do the same thing with some other subset, particularly with Edwards curves.  For example, you could restrict to only q-torsion or only 2q-torsion points, or only Elligator-encodable points.

I think the fastest way to do this is the one I posted with the inverse square root on the isomorphic Montgomery curve, but there are other options which basically accomplish the same thing.

— Mike