PQC At A Crossroads and the ECC Seatbelt

Well, RSA has done us well for nearly five decades, and elliptic curve cryptography has fixed many of the problems caused by discrete logarithms. In the past few decades, when it looked like we were getting near RSA or ECC being cracked, we just ratcheted up the parameters. For RSA, we are now at 2,048 bits for the modulus, and for ECC, we typically use the 256-bit curves of secp256k1, NIST P256 and Curve 25519. But, now, with Schorr’s algorithm, we cannot keep ramping up the parameters, especially for ECC. With RSA, we could probably keep going with it and keep increasing the RSA modulus, but performance would be terrible.

So, we end up with the methods that have some degree of security against quantum computers: lattice methods (based on the Learning With Errors approach); multivariate cryptography (eg Rainbow); isogenies (eg SIKE); code-based signatures (eg HQC and Classic McEliece); and MPC-in-the-Head (eg MAYO). In the first set of NIST standardisations, it was the lattice methods that proved to have the best balance between performance and key/signature/ciphertext sizes. With digital signatures, NIST approved Dilithium (aka ML-DSA), Falcon (aka FN-DSA) and SPHINCS+ (aka SLH-DSA), and for key exchange, they went with Kyber (aka ML-KEM) and HQC. NIST, in the end, has ended up with two main lattice standards, and not a great deal of alternatives at the current time: