[curves] The great debate over point formats

[Robert Ransom]

On 1/29/14, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On Jan 28, 2014, at 10:25 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:

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

See the first four paragraphs of <http://cr.yp.to/patents/us/6141420.html>.


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

Good point.

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

Only if the party needs to compute and send a sign bit.  (I wouldn't
compute a sign bit for an ECDH public key unless I also wanted to use
it for something like Ace or a signature or commitment scheme.)

I don't think there's any real need to distinguish encoded points with
a sign bit from those which do not have a meaningful sign bit, though.
 The party who generates a public key is likely to know which
protocols it will be used in, and there isn't too much harm if someone
else tries to use it in a protocol that its owner doesn't want to
participate in.


(Also, Dragonfly does need to transmit the sign bits of its group elements.)


Robert Ransom