[curves] The great debate over point formats

[Robert Ransom]

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.


> 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.


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>.)


Robert Ransom