[curves] Another try at point compression

[Michael Hamburg]

Intriguingly, the new format (and possibly other Legendre-symbol-dependent formats as well) *can* be made to work with p == 5 mod 8 with a moderate amount of hassle — basically requiring a better “isqrt_trick” function.  However, it still does not work for Ed25519, because of the cofactor.  It might work for the twist of Ed25519, though.

The notion is that you don’t actually need a way to compute, say, sqrt(a/b) so that it has Legendre symbol 1.  It’s enough to be able to compute sqrt(a/b) in a way that’s stable if you scale a and b, which is much easier.  For example, you can take the even square root.  Or you can compute the expression in such a way that its quartic symbol is either 1 or i, as opposed to -1 or -i.

This is true for the Edwards case.  I haven’t checked the Montgomery case yet, and I haven’t worked out yet the least-obnoxious formulation.

I don’t think this is going to convince anyone to switch to TwistEd25519 (or PinkBikeShed, heh), but I thought I’d share.

— Mike

> On Dec 17, 2014, at 8:12 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 
> 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