Composite order ECC and Ristretto

Question

I've been looking at the Ristretto group, and its really cool.

I understand that, for some protocols, we need curve points to behave as if they were from a prime order curve.

I have a few questions on this:

1. Do we call curves without prime order "composite"?
2. Why do some protocols demand prime order from the underlying curve?
3. Why isn't the fact that we work inside a prime order subgroup anyway good enough in the first place, is it that the curve arithmetic is done over the entire curve?

Answer 1

Here are some initial thoughts. Happy to clarify later on by editing.

Question 1: We call such curves "composite-order curves." I suppose "composite" would pass too, but might be a bit less precise.

Question 2: Some protocols demand either prime-order subgroups or prime-order groups because they are susceptible to small-subgroup attacks (see [VAS+16e, JSS15, LL97, BCM+15e]). Of course, the prime has to be sufficiently large.

Question 3: Working inside a prime order subgroup is good enough for security, it's just not good enough in other senses:

1. From an implementation complexity point of view, it can be error-prone when implementing cryptosystems (e.g., EdDSA) to have to remember to always check group elements are not of small order (see [CJ19e, JSS15]). Even worse, implementers might not even be aware they need to do this, since academic papers do not tend to stress for the reader that the most popular elliptic-curve groups are not prime-order.

2. From an implementation consistency point of view, even if you are a good implementer and remember to always check the order of elements, other people might not! This leads to inconsistent implementations of the same cryptosystem (e.g., see the lovely plethora of EdDSA issues [deVa20, CGN20e])!

3. From a performance point of view, checking prime order subgroup membership can be slow (sometimes fancy techniques can make up for it; see [Bowe19e]). If checking prime-order subgroup membership can be avoided by using a fast prime-order elliptic curve group (e.g., Ristretto), one should do so.

References

[deVa20]: It’s 255:19AM. Do you know what your validation criteria are?, by Henry de Valence, 2020, [URL]

[Bowe19e]: Faster Subgroup Checks for BLS12-381, by Sean Bowe, in Cryptology ePrint Archive, Paper 2019/814, 2019, [URL]

[BCM+15e]: Subgroup security in pairing-based cryptography, by Paulo S. L. M. Barreto and Craig Costello and Rafael Misoczki and Michael Naehrig and Geovandro C. C. F. Pereira and Gustavo Zanon, in Cryptology ePrint Archive, Paper 2015/247, 2015, [URL]

[CGN20e]: Taming the many EdDSAs, by Konstantinos Chalkias and François Garillot and Valeria Nikolaenko, in Cryptology ePrint Archive, Report 2020/1244, 2020, [URL]

[CJ19e]: Prime, Order Please! Revisiting Small Subgroup and Invalid Curve Attacks on Protocols using Diffie-Hellman, by Cas Cremers and Dennis Jackson, in Cryptology ePrint Archive, Paper 2019/526, 2019, [URL]

[JSS15]: Practical Invalid Curve Attacks on TLS-ECDH, by Jager, Tibor and Schwenk, Jörg and Somorovsky, Juraj, in Computer Security -- ESORICS 2015, 2015

[LL97]: A key recovery attack on discrete log-based schemes using a prime order subgroup, by Lim, Chae Hoon and Lee, Pil Joong, in Advances in Cryptology --- CRYPTO '97, 1997

[VAS+16e]: Measuring small subgroup attacks against Diffie-Hellman, by Luke Valenta and David Adrian and Antonio Sanso and Shaanan Cohney and Joshua Fried and Marcella Hastings and J. Alex Halderman and Nadia Heninger, in Cryptology ePrint Archive, Paper 2016/995, 2016, [URL]