[curves] The great debate over point formats
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
>> 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
> 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
(Also, Dragonfly does need to transmit the sign bits of its group elements.)
More information about the Curves