[curves] The great debate over point formats

[Mike Hamburg]

On Jan 29, 2014, at 12:20 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:

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

Thanks!  I knew it was somewhere...

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

Right.  I just meant that we'd have to spec at a protocol level, "this protocol doesn't use the sign bit, so don't generate one or send it, and in particular don't throw one into the hash at the end".  If the sign bit were free, we could just have a single "serializePoint" function, but it's not free.  So, fine.

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

Right, d'oh.

> The bigger question is “Which Edwards curve?”.  As long as the only
> Montgomery-form coordinate encoded is x, Montgomery curves are fairly
> well-defined given Montgomery A.  But the Edwards form has a
> two-dimensional parameter space (a, d), and in many cases there are
> multiple reasonable choices of a.

Good point.

> I would choose a=-1 as the encoded form for every curve in every
> coordinate field in which -1 is a square, and a=1 otherwise.  This is
> consistent with Ed25519; it makes safe, reasonably efficient
> implementations more convenient without adversely affecting more
> highly optimized implementations (e.g. implementations which use an
> a=-1 form of a curve specified with a=1 over a 3mod4 coordinate
> field); and it keeps the non-affine coordinates which arise when d/a
> is a square away from the point encoding/decoding operations.


In the 3 mod 4 cases, we're starting with an Edwards curve, and the Montgomery curve is isomorphic or isogenous to it, at least in the 3 mod 4 cases.  So I guess we have to choose there, isomorphic or isogenous?  It's probably gotta be isomorphic, right?  Do you know how point compression would interact with the isogeny, or should I try to work it out?  The advantage of the isogenous ones is that d = (A+2)/4 so you can use the well-known formulas, but there are obvious advantages to an isomorphism.

In the 5 mod 8 cases, it's the reverse.  I don't especially care whether it's +1 or -1 here.  Talking with Watson and Trevor, we might end up cutting all the 5 mod 8 cases except Curve25519, because they were generated under a mistaken idea of how Elligator2 works, and they aren't particularly better than the 3 mod 4 curves.  In the mean time, I dunno, your suggestion of -1 because that's how Ed25519 works is fine by me.

Cheers,
-- Mike