[curves] The great debate over point formats

[Mike Hamburg]

On Jan 28, 2014, at 10:25 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:

> On 1/28/14, Trevor Perrin <trevp at trevp.net> wrote:
>> On Tue, Jan 28, 2014 at 11:44 AM, Watson Ladd <watsonbladd at gmail.com>
>> wrote:
>>> On Tue, Jan 28, 2014 at 11:41 AM, Michael Hamburg <mike at shiftleft.org>
>>> wrote:
>>>> Do you mean the whole Edwards-x-coordinate, or just the sign?
>>> 
>>> Good catch: just the sign is probably the best choice.
>> 
>> That's similar to point compression, which some people have avoided
>> due to patent fears [1].  But the patent in question expires in July
>> 29 2014.  Since it will probably take that long to get any new curves
>> deployed, that doesn't seem like a problem.
> 
> Dr. Bernstein cites prior art for point compression.

What is it?  I was trying to find it, but his "irrelevant patents" page only mentions dropping y.

>> It would be interesting to see an analysis of how this "unified
>> format" affects performance and code complexity vs simply using 2
>> separate formats, one for ECDH and one for signatures, as is done for
>> curve25519 / Ed25519.
> 
> In any routine which operates on points in Edwards form internally
> using a reasonable algorithm, using a Mongomery-form x coordinate in a
> point format instead of an Edwards-form y coordinate either has no
> performance or complexity cost, or costs a few multiplies during table
> setup while *reducing* code complexity.
> 
> The conversion from Montgomery-form affine x (which I will denote “u”)
> to Edwards-form projective y (in P_1 * P_1) is y = (u - 1 : u + 1).  y
> is always defined (even if it is projective infinity), regardless of
> the value of u, and P_1 * P_1 is a very good internal representation
> for use with the Hisil et al. formulas.
> 
> Unpacking a point to a projective, rather than affine, Edwards-form
> representation does mean that the implementation can't save 1M per
> addition of that point using the ‘mixed’ addition formulas, but the
> only algorithm where that matters is Brauer's (or Straus's) algorithm
> with 1-bit limbs (sometimes known as ‘double-and-add’, but I think
> I've also seen that term used for a right-to-left algorithm where the
> affine-input speedup doesn't apply).  For a constant-time Brauer's (or
> Straus's) algorithm with larger (even signed 2-bit) limbs, or for
> variable-time Bos-Coster multiple-scalar multiplication, the maximum
> possible benefit of an affine input point is tiny.

I agree.  Also, if you really care about unpacking to affine, and you're recovering x from a sign bit, then your square root can pay for the inversion.

> For the other coordinate, Montgomery-form y is unsafe to use in
> software which uses Edwards form internally, in the sense that
> implementations are more likely to screw up point unpacking than to
> get it right.  (See
> <https://www.ietf.org/mail-archive/web/cfrg/current/msg04115.html>.)

The remaining trick is, should the Ed-x-coordinate or its sign bit be used universally, even by Montgomery implementations or not?  Because it's not thaaaaat difficult or expensive to compute, but it isn't trivial either.  And we'd have to go one way or the other for interoperability.  Maybe say it's used by everything except ECDH and SPEKE (and Dragonfly, and other Kummer-curve protocols)?

-- Mike