[curves] Another try at point compression

[Robert Ransom]

On 12/14/14, Michael Hamburg <mike at shiftleft.org> wrote:

> The main advantage vs Montgomery x + Edwards x sign is that the encoding I’m
> working on eliminates the cofactor for most practical purposes.  In
> particular:
>
> * you don’t need to multiply through by the cofactor;
> * you don’t need to worry about small-subgroup attacks;
> * the DH function becomes 1:1 again without any hacks;
> * the isogenous twisted Edwards curve with a’ = -1, d’ = d-1 effectively has
> complete addition formulas;
> * there is no fingerprinting or splitting attack based on how your signature
> scheme handles the cofactor;

This is a major benefit -- major enough that I would seriously
consider using Curve1174 instead of Curve25519 in an anonymity system
or any privacy system that needs to permit alternative
implementations, despite the relative lack of implementation
experience.

> * the wire format supports precisely those points which can actually come
> out of a legitimate implementation.

> Also, you can encode the identity point cleanly unlike Montgomery x + Edward
> x sign, which could be a blessing or a curse.  But if it’s a curse you can
> block it easily because the identity encodes to 0.
>
> Of course, there are significant downsides to the new design, the most
> important being that it doesn’t work for Curve25519.  Also, there are surely
> simpler formulas which are almost as good, so maybe we should just use them.

I don't think anyone is going to change Curve25519's point format now,
so not supporting that is not a problem.

Before you posted this, I would have preferred (Montgomery 1/x,
Edwards x sign bit) for any curve less widely deployed than
Curve25519, to encode the identity element properly.

In my opinion, the main disadvantage of your previous sgn(v)/sqrt(u)
format was that it absolutely required one exponentiation to pack each
point.  I didn't think that format had quite enough of a benefit to
justify standardizing it.

This new format has the same disadvantage, but a *much* bigger
benefit.  I think this one is worth standardizing.


The one thing to note is that if this requires a twist-secure curve
with cofactor 4, there aren't any over the Curve3617 field with
small-integer d < 50000.  (If this point format doesn't require twist
security, I think there's a suitable curve with d < 3617.)


Robert Ransom