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 <[email protected]> wrote: > > On 12/14/14, Michael Hamburg <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
