[curves] Another try at point compression

[Michael Hamburg]

> On Dec 14, 2014, at 2:14 PM, Trevor Perrin <trevp at trevp.net> wrote:
> 
> On Mon, Dec 8, 2014 at 2:07 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>> Hi curves,
>> 
>> Here is another try at a unified point compression system.
> 
> So why is this better than just using the Montgomery x-coordinate,
> plus the Edwards sign bit, for a "unified format"?
> 
> People have a lot of experience and code for dealing with Montgomery x
> in the case of Curve25519, so it would make sense to leverage that.
> 
> This format can be decompressed into Edwards form with very small
> efficiency loss (a few percent).  So these public keys could be used
> with Ed25519 or similar signature algorithms easily.  And for ECDH you
> can ignore the bit and just do the Montgomery ladder, so this is of
> course very efficient there.
> 
> I'm biased because TextSecure essentially does this, but I'm not sold
> on the merits of your more complicated encodings yet.
> 
> Trevor

Well, I’m not sold on merits of my formulas either, and it’s often wise to pick something people are experienced with vs some new-fangled design.  But I think the new design is at least worth investigating.  Especially this latest batch, because it has a cool property that the earlier ones didn’t.

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;
* the wire format supports precisely those points which can actually come out of a legitimate implementation.

Also, the new format is halfway between the untwisted and twisted curves, so you can just pick one (probably the twisted curve because it’s faster) and implement everything there.  You don’t have to worry about cases where you just want to add one point and can’t use the isogeny because it would quadruple the result.

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.

— Mike

PS: The signs aren't quite right in the first email I sent out.  I’m working on finalizing (one version of) the math to circulate, with some SAGE code to check that it’s correct.  But it looks like the idea works.