Comment by tombert
4 hours ago
Outside of the PQ algorithms not being as thoroughly vetted as others, is there any negatives to shifting algorithms? Like even if someone were to prove that quantum computing is a dud, is there any reason why we shouldn't be using this stuff anyway?
AFAIK, PQ certificates are significantly longer than current ones. I don't know exact numbers though.
they are much more thoroughly vetted than other schemes. They're more thoroughly vetted than elliptic curves were before we deployed them. Much more vetted than RSA was ever.
Practically though, there are some downsides. Elliptic curves tend to have smaller ciphertexts/keys/signatures/so are better on bandwidth. If you do everything right with elliptic curves, we're also more confident in the hardness of the underlying problems (cf "generic group lower bounds", and other extensions of this model).
The new algorithms tend to be easier to implement (important, as a big source of practical insecurity is implementation issues. historically much more than the underlying assumption breaking). This isn't uniformly, e.g. I still think that the FN-DSA algorithm will have issues of this type, but ML-DSA and ML-KEM are fine. They're also easier to "specify", meaning it is much harder to accidentally choose a "weak" instance of them (in several senses. the "weak curve" attacks are not really possible. there isn't really a way to hide a NOBUS backdoor like there was for DUAL_EC_DRBG). They also tend to be faster.
Post-quantum algorithms tend to be slower than existing elliptic curve algorithms and require more data to be exchanged to provide equivalent security against attacks run on non-quantum computers.
Any idea how much slower? Like are we talking half the speed? A quarter? 1%?
Sorry, I'm just very out of the loop on some of this stuff and I'm trying to play a game of catchup.
This page lists some figures for ML-KEM-768 (which is the PQ key exchange algorithm that's most widely deployed today): https://blog.cloudflare.com/pq-2025/#ml-kem-versus-x25519 This one is actually faster than X25519 (a highly optimized ECC algorithm) by about double but requires 1,184 bytes of data to be exchanged per keyshare vs 32 for X25519. In practice everyone today is using a hybrid algorithm (where you do both ECC and PQ in case the PQ algorithm has an undiscovered weakness) so an ECC+PQ key exchange will be strictly slower than an ECC-only key exchange.
This page lists some numbers for different PQ signature algorithms: https://blog.cloudflare.com/another-look-at-pq-signatures/#t... Right now the NIST has selected three different ones (ML-DSA, SLH-DSA, and Falcon a.k.a. FN-DSA) which each have different trade-offs.
SLH-DSA is slow and requires a large amount of data for signatures, however it's considered the most secure of the algorithms (since it's based on the well-understood security properties of symmetric hash algorithms) so it was selected primarily as a "backup" in case the other two algorithms are both broken (which may be possible as they're both based on the same mathematical structure).
ML-DSA and Falcon are both fairly fast (within an order of magnitude of Ed25519, the X25519 curve signature algorithm), but both require significantly larger keys (41x/28x) and signatures (38x/10x) compared to Ed25519. Falcon has the additional constraint that achieving the listed performance in that table requires a hardware FPU that implements IEEE-754 with constant-time double-precision math. CPUs that do not have such an FPU will need to fall back to software emulation of the required floating point math (most phone, desktop, and server CPUs have such an FPU but many embedded CPUs and microcontrollers do not).
The net result is that TLS handshakes with PQ signatures and key exchange may balloon to high single- or double-digit kilobytes in size, which will be especially impactful for users on marginal connections (and may break some "middle boxes" https://blog.cloudflare.com/nist-post-quantum-surprise/#dili...).