[curves] The great debate over point formats

Robert Ransom rransom.8774 at gmail.com
Wed Jan 29 00:20:53 PST 2014


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


More information about the Curves mailing list