On 1/29/14, Mike Hamburg <[email protected]> wrote: > > On Jan 28, 2014, at 10:25 PM, Robert Ransom <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
