A Post-Quantum Future for Let's Encrypt

Doesn’t mention anything about quantum there though. Symmetric keys are secure enough against a cryptographically relevant quantum computer, but OTP provides information theoretic security. As GGP mentioned AES should be fine as far as we know for the foreseeable future regardless, but for all we know some brilliant cryptographer will in fact find a flaw. With OTP one doesn’t have to worry about even the slightest chance that could happen. This excerpt also may be alluding to threshold cryptography (Shamir’s secret sharing) which got.. shared.. here recently as well, and also happens to be information theoretically secure.

You are right in that there are cases where signatures need to be quantum-safe, and they need to be urgently replaced because they will be long-lived.

But WebPKI, which letsencrypt is concerned with, doesn't need long-lived signatures at all. TLS connections live a few days at the most, that's how long the connection signatures have to hold up. The only thing that really needs some lifetime are CA certificate signatures and the CA keys themselves. And even for those CA certificates currently, CRQCs won't be a problem before they expire. And browser update cycles are quick enough that new CA certificates aren't that much of a problem anymore.

In a way it's just more of what we're already dealing with today.

The entire Linux ecosystem simply trusts Firefox's root CA store, and we're happy with distros repackaging and shipping it to us as-is every once in a while. OCSP has failed, so now Firefox is regularly shipping kilobyte-sized bloom filter updates to every browser to replace it with CRLite.

Doing the same for MTC landmark updates doesn't sound like too big of a change to me. The biggest challenge is going to be to get the wider ecosystem to adopt it: some kind of system-wide cron job to download the updates, or perhaps a "systemd-validate-mtc" helper.

The real challenge is going to be the embedded world. This kind of overhead is trivial for a desktop or a server, but a tiny embedded chip with only a few megs of ram and flash?

worth clarifying that you're both right that this is often referred to as a "hybrid", and there is the exceedingly unfortunate naming collision that "Hybrid Encryption" can also mean something separate, namely using a PKE encryption scheme (or KEM) to solely encrypt a secret key, and then using the secret key for bulk encryption. See for example the Hybrid Public Key Encryption (HPKE) RFC

https://datatracker.ietf.org/doc/rfc9180/

the unambiguous way to describe what you're talking about (not only for encryption) is the notion of a combiner, though it is admittedly mostly used in theoretical circles.

Also, your comparison between ML-KEM and ECC isn't right. ML-KEM is a KEM built from the Module Learning with Errors assumption, a lattice-based assumption. Part of how ML-KEM is built is by building a PKE scheme. This is an internal implementation detail though, and the FIPS standard explicitly states that they are only approved as part of building ML-KEM.

You can additionally build signatures from MLWE. For example, the ML-DSA scheme (which is a FIPS standard as well) does this. The issue is that lattice-based KEMs and signatures are atypically large compared to ECC precursors (this is what the blog post refers to).

there is no even conjectured candidate for a backdoor in the standardized PQ schemes. This is different from other backdoors in the past, for example

1. for DUAL_EC_DRBG, the fact that it could hold a backdoor was understood quite early on

2. The S-box in the russian block ciphers Kuznyechik and Streebog was said to be randomly generated, but it was discovered to have extremely particular structure, which makes it exceedingly unlikely to be randomly generated.

Note that both of these "warning signs" are able to be seen even without understanding yet how to exploit them. To this day we do not know if Kuzynyechik and Streebog are backdoored (though it seems exceedingly likely).

Another point worth mentioning is that the design underlying ML-KEM could be instantiated in a way that would admit a backdoor. Very roughly, we would instantiate a "ML-KEM lattice", akin to how DLOG-based schemes instantiate DLOG groups (e.g. curve 25519, etc). This ML-KEM lattice could plausibly be attacked with a precomputation attack, akin to things like the LogJam attack against finite-field DH (there are even more fun things you can do if this standardized ML-KEM is just e.g. written down, rather than generated akin to a "nothing up my sleeve" number).

ML-KEM was specifically designed around this issue, and instead freshly samples a ML-KEM lattice for each exchanged key. Fortunately, it is quite easy to do this efficiently and securely for ML-KEM (freshly sampling a DLOG group to work in is neither efficient nor secure for elliptic-curve based cryptography).