Handling cofactor 4

[fscoto]

Copying over from #1 with some changes.

There are a few options of how to handle the relationship between cofactor 4 curves and Ristretto. As far as I can glean from the Git history, ristretto448 used to be planned, but then quietly got cut.

Currently, the website presents Ristretto as this mixed bag between h = 4 as well as h = 8 and only h = 8:

Ristretto is a technique for constructing prime order elliptic curve groups with non-malleable encodings. It extends Mike Hamburg's Decaf approach to cofactor elimination to support cofactor-8 curves such as Curve25519.

[...]

Ristretto can be used in conjunction with Edwards curves with cofactor 4 or 8, and provides the following specific parameter choices:

However, ristretto448 for Ed448-Goldilocks, the other major Edwards curve going around, isn't actually defined. The reason specifying something for Ed448-Goldilocks at all is useful is because of I-D.draft-irtf-cfrg-voprf-03 specifying in § 8.1.4 that they only consider ciphersuites providing 196 bits of security (Not sure if this was supposed to be 192 or if they really did mean 196 bits but include NIST P-384 regardless). While the Internet Draft does account for required cofactor hacks, having a more elegant alternative to implement the IETF (V)OPRF on would probably be useful from an implementation perspective, and a lot less scary.

The curve selection page on the website of the Doppio group notes that Decaf is much easier and straightforward in the h = 4 case, both conceptionally and practically. And I agree in theory. Personally, I think the main issue with saying “just use Decaf”, however, is that there are no test vectors, plus the definition of what constitutes a negative number as well as encoding of field elements is implementation-defined. Making this well-defined (e.g. as Ristretto-flavored Decaf that just writes down Decaf and defines some missing elements and instantiates ristretto448 with that theory) would probably end up being a net gain. New curve designs could then pick up from the base decisions made for Ristretto-flavored Decaf, too, without having to specify a bunch of specific Decaf parameters for interop.

[bitwiseshiftleft]

My preference is to specify and make test vectors for the Decaf v1.1 format, as implemented in libdecaf ristretto.sage's Ed448GoldilocksPoint.

The formulas for that instantiation of Decaf are slightly different from Ristretto because of how things are attached, and in fact Ristretto descends in part from libdecaf. Curve25519 and Ed25519 are isomorphic, whereas Curve448 and Ed448 are 4-isogenous. The original Decaf design sits between Curve448 and Ed448, on the Jacobi quartic that's 2-isogenous to both. When porting this to Curve25519, you can choose to apply the Montgomery curve formulas to Curve25519, or the Edwards curve formulas to Ed25519. The first option gives Ristretto (give or take some changes in the meaning of "positive"). I chose (a predecessor of) this design in libdecaf because it keeps the A and d-coefficients of the curves small.

I can put some work into specification this weekend. Where's the right place to put it on this website?

[fscoto]

@bitwiseshiftleft Are you sure putting the spec on the website won't constitute a legal hazard for you? I seem to recall reading somewhere that the reason the Strobe protocol framework and libdecaf code are on SourceForge.

[bitwiseshiftleft]

@fscoto I don't think so?

Strobe and libdecaf and threebears are on Sourceforge because they might constitute US-made encryption software (Strobe has encryption modes, and libdecaf has x448 and x25519). In that case Sourceforge's "don't let Syria and DPRK download this" checkbox gives a veneer of compliance with export control law.

But a non-executable spec for a point serialization routine isn't encryption software.

[fscoto]

@bitwiseshiftleft Hm, I see. I can't say I'm well-versed in U.S. cryptography export laws, so I assume you'll have done your research.

In any case, if you want to work on it until there's an authoritative answer where to put it on the website, perhaps it would be easiest for you to take the existing Decaf paper and update it with Decaf v1.1 and perhaps a concrete instantiation for Curve448? That way, people who come in externally looking for Decaf from older sources would also find a current spec (as opposed to needing to know to look at the Ristretto website).

[Librechain]

Hey, just dropping in - was looking for the specs for ed448 over Ristretto. Like the other user above, was also curious on how the cofactor is handled in this case (more elaboration on jacobi quartic?)

As far as U.S. cryptography export laws go, I'd be more than happy to serve as a proxy for any & all issues you feel may arise (without stealing your IP / depriving you of authorship). I find these policies to be extremely racist (not one country where the majority has a darker skin-pigment has an exception ; but I digress).

Thank you for your efforts

[fscoto]

@Librechain For specs, you can turn to I-D.draft-irtf-cfrg-ristretto255-decaf448 for the time being. It'd still be nice to have this website up to date, but I suspect that the IETF draft will ultimately become the canonical source for Decaf and Ristretto anyway.