6 ms·

A Post-Quantum Future for Let's Encrypt

320 points by SGran 4mo ago

lukan 4mo ago
Better encryption sounds good to me in general, but I don't really understand, how we can make quantum safe encryption, when we don't know yet, what capabilities it will have (or if it is possible at all). I am obviously not in the field, but as far as I know, no QC is close of working for a practical purpose(aside quantum research), but to make it practical, it needs a groundbraking brakethrough of some sort. But if a brakethrough happens, can we really estimate the consequences?
- rcxdude 4mo ago
  The capabilities of quantum computing, in theory, are pretty well known. There's basically a few extra operations which can be done efficiently on it and so that can be built into the threat model, even if no-one's built a quantum computer yet. (Of course, basically all encryption, especially asymmetric encryption, is predicated on there not being some as-yet-undiscovered exploitable structure to the mathematics on which it is built. Modern cryptography, AFAIK, tends to have some decent arguments for why this is not expected to be the case, but it's never completely proven top-to-bottom outside of fairly niche/trivial cases. It's always in principle possible that someone discovers an attack on these new algorithms, classical or quantum)
  - chadgpt3 4mo ago
    Supersingular Isogeny Key Exchange is one that was invented to be quantum-safe but turned out to be unsafe at any speed, so hybrid encryption is still a good idea. You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.
    - some_furry 4mo ago
      > You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken. No. Don't do that. If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. You want a Hybrid KEM, not encrypting twice. The nuance matters. https://durumcrustulum.com/2024/02/24/how-to-hold-kems/ https://durumcrustulum.com/2024/02/24/how-to-hold-kems/
      - insanitybit 4mo ago
        > If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?
        some_furry 4mo ago
        If you encrypt your data twice (taken very literally): c1 = E1(p, k1) c2 = E2(p, k2) If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p. What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken. ss1, ct1 = KEM1(pk1) ss2, ct2 = KEM2(pk2) secret = Combiner(ss1, ss2, [ct1, [ct2]]) This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated. This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations. I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
        3form 4mo ago
        It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
    - tptacek 4mo ago
      No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices. People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.
      - mswphd 4mo ago
        Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU. He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now. In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world. This is ignoring all of his other explicitly embarrassing behavior, for example 1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly. 2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust. 3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.
    - mswphd 4mo ago
      The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places. The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve. So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.
- n4r9 4mo ago
  The problem is perhaps more theoretical than you might think. The security of post-quantum schemes basically comes down to the fact that researchers have thought long and hard about whether there are efficient classical or quantum algorithms to solve a given problem, and haven't found any yet. That's not necessarily anything new. Even RSA is predicated on no one having a fast factorisation algorithm.
- BoppreH 4mo ago
  To answer your "if it's possible at all" question: it's full of hard engineering problems, but none of it looks unsolvable, and the investments are there. And even if there was only a 10% chance of QC breaking crypto, the community is not comfortable with a 10% chance of such a catastrophic scenario. This is part of my day job, so here's another interesting fact: for migrating encryption use cases, you have to consider that attackers can capture your encrypted data today to break in the future. So, as a rule of thumb, your migration timeline is much shorter for encryption than for signatures.
- thenthenthen 4mo ago
  I guess how technology and policy paths are layed out? It is basically a wish list. Like we already have the spec for 7G mobile comms decades ahead …(https://www.techsciresearch.com/blog/5g-vs-6g-vs-7g-unveiling-the-future-of-connectivity/4485.html https://www.techsciresearch.com/blog/5g-vs-6g-vs-7g-unveilin... )
- fxwin 4mo ago
  Well similar to how turing machines are a sufficient theoretical model to make all kinds of arguments about runtime complexity of classical computers without relying on their actual physical implementation, we have theoretical models for the way we are approaching quantum computation that do the same thing (Namely the quantum circuit model)
- tsimionescu 4mo ago
  By this standard, there is no current encryption method (except for pre-shared one time pads when used correctly) that is known to be unbreakable. For example, it is not proven that prime factoring can't be done much more efficiently on a classical computer - for all we know, it's possible that tomorrow someone will come up with a novel algorithm that can break RSA in just a small number of operations. Same is true for elyptic curves - we don't have any mathematical proof that it's impossible for a much better algorithm than the currently known ones is possible. However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't. In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP. So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.
  - Cider9986 4mo ago
    Would post-quantum encryption also be harder for regular computers to crack?
    - some_furry 4mo ago
      The international standardization effort that led to ML-KEM and ML-DSA focused both on classical attacks (regular computers) and quantum attacks. There were 5 levels being considered for each submission. Level 1 - at least as difficult to attack as AES-128 (block cipher) Level 2 - at least as difficult to attack as SHA-256 (hash function) Level 3 - at least as difficult to attack as AES-192 (block cipher) Level 4 - at least as difficult to attack as SHA-384 (hash function) Level 5 - at least as difficult to attack as AES-256 (block cipher) The security of attacking an N-bit block cipher is morally congruent to a birthday collision against a {2N}-bit hash function. With some caveats: https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/ https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th... ML-DSA-44 (smallest parameter set) targets Level 2 for signatures. ML-KEM-768 targets Level 3 for KEMs.
- chasil 4mo ago
  These are/will be the fundamentals of quantum logic. https://en.wikipedia.org/wiki/Quantum_logic_gate https://en.wikipedia.org/wiki/Quantum_logic_gate
- jerf 4mo ago
  In addition to the other fine answers, I personally find the additional operations that quantum computers enable to be surprisingly inapplicable to a lot of real problems. It's really kind of unimpressive when you dig down into it. It is not a revolution of computing as we know it, it's a very, very expensive accelerator card for a few niche problems. Neat for people who have those problems. But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does. I think there is a sense in which we have a historical accident that has make quantum computers sound bigger than they are, in that we ended up with "factoring prime numbers" being the first thing we had to make practical encryption out of, and by what is from a human perspective mostly a coincidence, it so happens that quantum computers may be really good at that. But the problem is that quantum computers happen to be good at factorizing that is the problem, not that quantum computers are somehow "good at breaking encryption". It seams to me that in some sense "post-quantum computing" is actually "all practical encryption schemes except those based on factoring large numbers". Breaking large prime number-based schemes is the exception that QC happens to be good at, not the rule.
  - kibwen 4mo ago
    > But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does. I think it's very funny to consider that if you were a time traveler tasked with making sure that humanity had the economic incentive to develop quantum computers, the most efficient way to ensure that in a single stroke would be by suggesting the use of prime factorization as a trapdoor function to Rivest, Shamir, or Adleman.
  - adgjlsfhk1 4mo ago
    it's not just factoring, but general discrete log over abelian groups
    - jerf 4mo ago
      Yes, sorry, I didn't mean to imply they could only "factor". But the things they can do that they get the big advantage over classical computing I find underwhelming when considered against the entire scope of computing problems. Again, great for the people who have those problems, but I still am not sure that they are "worth" what are being poured into them in terms of any real economic impact they have. I do wonder if I could trace back all the money in the sector to their original source just how much of it would end up being the intelligence sector who wants their crackz, and how valuable it'll end up being to them in the end if they can't get a decent crack before we all go post-quantum encryption anyhow.
- hylaride 4mo ago
  It's essentially the laws of physics. To oversimplify, Quantum computing can essentially do certain kinds of operations extremely fast (like factoring prime numbers) because it can calculate all the permutations almost instantly. But if you add intentional complexity to it in ways that all those states can't be "seen" then the quantum computer falls flat. That's one of the issues with adding post-quantum algorithms, they're by design less efficient in certain ways, meaning slower and/or with more overhead. The way a quantum mechanics PhD explained it to me years ago in layman's terms is similar to nuclear science. We "knew" that a nuclear explosion was possible before a bomb was created and what conditions it would work. The Nagasaki bomb was a completely different type of bomb than the trinity test and Hirosima, plutonium instead of uranium, and it was never even tested before it's first use!
  - mswphd 4mo ago
    this is not an accurate description/heuristic of how quantum computing works. It would predict quantum computers can solve problems that they cannot solve. For a more accurate account see e.g. https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/ https://www.quantamagazine.org/thirty-years-later-a-speed-bo... And the post-quantum algorithms are not by design less efficient either. For example, RLWE-based schemes are more cycle-efficient than elliptic curve schemes. They're not uniformly more efficient (key/ciphertext sizes are generally longer), but this has nothing to do with intentional design choices to make them post-quantum secure. Just different things are different.
    - hylaride 4mo ago
      Fair. I was quoting from memory from maybe 5 years ago.
  - tatersolid 4mo ago
    Clarification/correction: The Nagasaki “Fat Man” bomb was the same plutonium implosion design tested at Trinity. The Hiroshima “Little Boy” bomb was the uranium “gun” design that was never tested before combat use. The physics and engineering were comparably straightforward so the scientists were very sure it would work assuming the Urnaium enrichment was pure enough.
- Tangurena2 4mo ago
  Bruce Schneier's books explain that there is far more to security than better encryption. Most are implemented incorrectly or used incorrectly.
  - avadodin 4mo ago
    I also liked the memes. Too bad they died out after he failed with Skein.
BoppreH 4mo ago
Interesting development. Merkle Tree Certificates throw away decades of cruft, but also decades of battle testing and ancillary tools. I trust the teams involved, but this will be a hell of a project. Still better than the alternatives that would saddle us with worse performance for ~ever.
- quantumscan 4mo ago
  [flagged]
- throwaway01632 4mo ago
  Is there any value in first encrypting with a battle tested algorithm, and then encrypt again with the new algorithm?
  - BoppreH 4mo ago
    Yes! It's called a hybrid cryptosystem, and what most projects are planning to use. The algorithms at risk are the asymmetric part (RSA, ECC, DH), not the symmetric parts (AES, ChaCha), so what is done for encryption is "generating" a secret with ML-KEM and another with ECC, combining them, and using that as key for AES or another symmetric algorithm for the actual encryption. So if you break only ECC or only ML-KEM, you don't get the combined secret. ML-KEM keys/ciphertext are small and efficient enough that this overhead is generally a non-issue. Note that ECC can be used in many ways: asymmetric encryption, key encapsulation, or signatures. ML-KEM, the new post-quantum standard, is only a Key Encapsulation Mechanism. Hence the "generate an AES key" step, instead of "encrypt a random AES key". For signatures, like in the announcement in the post, things are more complicated. The post is a very good introduction to the problem.
    - mswphd 4mo ago
      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/ 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).
kibwen 4mo ago
> In the common case, the entire authentication path in an MTC handshake is one signature, one public key, and one inclusion proof. That’s smaller than today’s Web PKI handshake, even though MTCs use post-quantum algorithms. [...] There is more to MTCs than size optimization. Because every certificate is part of a published Merkle tree, transparency becomes a property of issuance itself. Today’s Certificate Transparency ecosystem is bolted on after the fact: certificates are issued by CAs, then logged separately, with extra signatures riding along in the TLS handshake to attest to that logging. With MTCs, a certificate cannot exist outside the Merkle tree. Certificate Transparency is built in. These upsides seem extremely promising, but I'm curious to know if there are any notable downsides as well.
- 2close4comfort 4mo ago
  I too was wondering how they feel about the potential downsides which is not really mentioned.
- Cyfrit 4mo ago
  The main downside is shifting from inline validation to out-of-band state syncing. For handshakes to stay small, browsers must constantly cache fresh "landmarks." If a device has been offline and hits a flaky hotel captive portal, it lacks these landmarks and triggers a fallback with massive inline ML-DSA signatures—bloating the handshake to 10KB+ exactly when the network is at its worst. It essentially turns a crypto size problem into a browser background syncing challenge.
  - kmori_de 4mo ago
    [flagged]
- agwa 4mo ago
  The downside is that to get the size optimization, TLS servers will get moderately more complicated (they'll need to have multiple MTC certificates configured and select the right one depending on the client's state), and TLS clients will get considerably more complicated (they'll need to continuously download landmarks for each CA out-of-band from a trusted source). I expect many non-browser TLS clients won't support the small landmark-relative certificates, because there isn't a clear party to operate the landmark distribution service (Chrome has Google, and Firefox has Mozilla, but who does curl have?). I'm also worried that support will be lacking in open source TLS servers, though that's a more tractable problem. Consequentially, I expect the large standalone certificates to be quite common outside of connections between browsers and CDNs.
tomgag 4mo ago
Refreshing! Not wanting to be the "told you so" guy, I've been saying this for at least 2 years now: > Post-quantum authentication is no longer a problem the Web PKI ecosystem should defer. Long-lived keys (root certificate authorities, code-signing keys, identity systems) are particularly valuable targets, and new technology takes years to gain broad adoption, so the work has to start early. This is a problem that I have met so many times talking with people: they parrot the "Harvest-Now-Decrypt-Later is the only urgent problem, signatures can wait" mantra, and this piece of misinformation has spread so much that even AI repeats it (because it has been trained on open data, where the overwhelming sentiment has been following this trend), thereby reinforcing the problem. Ask Claude/ChatGPT/Gemini about the problem, and they will invariably tell you that signatures are less urgent because theyr are not subjective to retroactive compromise. There are two problems here. The first one is included by the Letsencrypt announcement: the migration path for signatures/certificates is typically longer and more complex than encryption: long-lived certificates, firmware update keys, secure boot certificates, these are all objects that are painful to migrate. The second one, even more serious in my opinion, is: "retroactive" in respect to what? "Retroactive" presupposes you can observe the trigger (the arrival of a cryptanalytically-relevant quantum computer), but this is precisely the kind of capability an adversary keeps secret, and a quantum forgery is operationally indistinguishable from, e.g., key exfiltration, a library bug, or a classical break. You may see a forged signature, a drained wallet, a failing certificate, and have no way to attribute it to quantum cryptanalysis. The threat is dark: reactive migration against an unobservable trigger is structurally impossible. This is not to say that Harvest-Now-Decrypt-Later is a less urgent threat, but it's not so asymmetric as people have been believing so far. Glad to see things are changing!
- some_furry 4mo ago
  > Refreshing! Not wanting to be the "told you so" guy, > This is a problem that I have met so many times talking with people: they parrot the "Harvest-Now-Decrypt-Later is the only urgent problem, signatures can wait" mantra, and this piece of misinformation has spread so much that even AI repeats it (because it has been trained on open data, where the overwhelming sentiment has been following this trend), thereby reinforcing the problem. Ask Claude/ChatGPT/Gemini about the problem, and they will invariably tell you that signatures are less urgent because theyr are not subjective to retroactive compromise. I can't speak to public sentiment, but the stance I've held for years was roughly: HNDL is more urgent because people are already encrypting messages today that could be decrypted in the future if a quantum computer is ever built in the foreseeable future, and that harms their privacy for the entirety of human history until PQC is rolled out. That's not the same as "authentication doesn't matter at all". It was, if you must pick a problem to solve today, this one will stop the bleeding sooner. But they were always both important to solve. The question was whether we could delay PQ auth until better signature algorithms were deployed. The Google/Cloudflare 2029 decision signaled to the rest of us: "No, we need to start the migration now."
skmurphy 4mo ago
We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for. In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise.
- firesteelrain 4mo ago
  That sounds a lot like Shamir Secret Sharing Algorithm similar to unsealing / sealing HashiCorp Vault. I did read the books 20 years ago and forgot this aspect of the story
- tialaramex 4mo ago
  But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on. OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" approach barely dents our symmetric cryptography. I've written about this before, DES was standardized in 1977, almost 50 years ago and you might think "Well but DES is broken". Yes, DES broke exactly the way it was designed to. Literally nothing went wrong, when it was standardized we knew the keys are too small (yup, you can break it by trying all the keys) and the blocks are too small (yup, you can "just" make duplicate blocks) and it was broken by leaning on these weaknesses with huge fast modern computers. AES is an entirely different cryptosystem, but the two most important choices were that the keys are big enough (128-bit or 256-bit commonly) and the blocks are too (128 bits). And those may seem like a small upgrade, only 2-4x as big, who cares? Well those are bit lengths so that's an exponential increase, and your quantum computer barely helps (assuming it magically is the same price rather than incredibly expensive). It is not physically practical for the necessary computation to be done, AES is broken only if there's some mathematical backdoor we didn't know about. "We'll crack AES with a quantum computer" is a Hollywood movie plot, it's not a thing that makes any actual sense. [Edited: I wrote "Bruce Sterling" but I meant "William Gibson", I apologise to both people for muddling them, though not for my opinion]
z3ratul163071 4mo ago
nsa and eu pushing for replacement of the reliable algorithms with unproven and very likely backdoored post-quantum algorithms, when there is no real threat at all, is highly suspicious.
- some_furry 4mo ago
  > and very likely backdoored post-quantum algorithms Citation needed Here's mine: https://keymaterial.net/2025/11/27/ml-kem-mythbusting/ https://keymaterial.net/2025/11/27/ml-kem-mythbusting/
  - z3ratul163071 4mo ago
    nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. i have no knowledge, nor time to eval. (and probably few people do) all i am saying is there is no good reason to depreciate proven algs, especially not because those two institutions said so.
    - tptacek 4mo ago
      That's not what you said. You said that the algorithms were "very likely backdoored", despite the fact that neither NSA nor the EU had any hand in actually designing them.
    - some_furry 4mo ago
      > nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. Who do you trust, then? > i have no knowledge, nor time to eval. (and probably few people do) If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions? Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced ML-KEM and ML-DSA? Or do you just balk at experts and "trust no one" even to your own detriment?
raphinou 4mo ago
I've been working on a new project using ed25519 signatures and discovered they are not quantum resistant.... I went with ed25519 due to possibility of using openssh keys. Any opinion on this choice at the light of this article and other quantum computing news?
- some_furry 4mo ago
  There's an IETF RFC draft for mldsa-44 keys for OpenSSH. https://datatracker.ietf.org/doc/draft-rpe-ssh-mldsa https://datatracker.ietf.org/doc/draft-rpe-ssh-mldsa I'm not aware if it has any real traction, but that's what I found with a quick search.
  - mcpherrinm 4mo ago
    OpenSSH's Damien Miller has https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-ed25519-composite-sigs/ https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-e... defining ssh-mldsa44-ed25519@openssh.com which seems more likely given the authorship.
    - some_furry 4mo ago
      Sure, but that's a composite scheme, and I dislike those. :P
- tardedmeme 4mo ago
  Signatures aren't as urgent to replace as encryption keys are. You can wait until someone is about to build a quantum computer, then change all your signatures. Encrypted data is more critical because the NSA's going to store all internet traffic for centuries if it thinks it can decrypt it later.
  - JoachimS 4mo ago
    No, very much no. If store now decrypt later is the problem, then we basically have no problem (Just like what Peter Gutmann argues [2]). The vast, basically all communication over for example TLS need confidentiality in minutes, hours. Not 30-100 years. My bank statement right now, the plans we discuss for the project next year etc. But what is very important crucial, what makes our digital world including secure communication, web commerce possible is the web of trust - identification and authentication. I'd claim that the important part of TLS including certs is this part. We could by and large not need the confidentiality. But since it costs so comparatively little we can just as well always encrypt too. You seem to think that changing a certificate is something we can fix in minutes. Globally. The reality is far from that. Esp in things that are not just your browser. Things like network equipment, FW for basically every embedded system, cars, busses. And crucially for critical entities. These things have long lifespans (decades), often need manual intervention to change certificates (connect a JTAG, serial intercace), possible even replacement. But replacing root certs in all our normal devices - phones, laptops etc are also far from easy and done in minutes. Then you have all digital identification solutions - from ID cards, car fobs, 2FA tokens, passports, credit cards. You may have to replace millions of physical things, even distribute to whole populations. And back to the web. If we can crack an RSA-2048 key in 24 hours (which is the measure used when guessing we have QC capable enough [1]). We really don't have that many CAs. The times they have had problems have caused problems that have taken days, weeks to trickle down. Having CA issue new rootcerts several times a day isn't viable. So I'd wager that transitioning to PQC safe certificates, authentication isn't something we can wait with. It will take years and huge efforts - not minutes and when the problem hits us. If you look at time plans for transitioning to PQC from CNSA, EU, UK and others, the area they all list as most critical to complete transition as soon as possible for is SW, FW-signing for infrastructure, embedded systems [1]. So, in reality unless you have a legal responsibility for keeping state secrets then store now, decrypt later is not really your main reason for PQC transitioning. Authentication very much is. Unfortunately most cryptographers by large seems to miss this. And people in uniform have a large saying, influence in the debate. My guess is that this is because gov to a large degree finance a lot of the QC research and they have a different threat model that most of the world. But that is just my guess. As Gutmann argues, we don't even really know that there even is a viable store now, decrypt later threat. Unless you can pinpoint the exact TLS session that is interesting, you can't store or decrypt all traffic that may be the interesting ones (if we assume that the cost of breaking a single RSA is not zero and takes minutes, seconds. Not 24 hours). And if indeed if TLS and normal key exchange mechanisms, are really used for those juicy messages. [0] https://globalriskinstitute.org/publication/quantum-threat-timeline-report-2025b/ https://globalriskinstitute.org/publication/quantum-threat-t... [1] https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS.PDF https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA... [2] https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf
some_furry 4mo ago
https://soatok.blog/2026/04/13/hybrid-constructions-the-post-quantum-safety-blanket/ https://soatok.blog/2026/04/13/hybrid-constructions-the-post... I wrote this in April. Many folks' misconceptions about post-quantum cryptography and "hybrid" constructions are answerable with this blog post.
- thyristan 4mo ago
  There is nothing answered in there. Just "It'll be fine" and vague pointing at unrelated ecc vulnerabilities in some libs. It totally lacks any rational arguments.
  - some_furry 4mo ago
    No shit. It is a blog post, not an academic paper or Lean proof. My blog posts are supposed to be informal and conversational, not pure logic. If you want "ratioanl arguments", look elsewhere than personal blogs.
  - mswphd 4mo ago
    the rational argument is that this time is not particularly worse than prior transitions, and arguably is one we are doing much more clear-eyed (think about all the ECC vulnerabilities during their first few years of deployment due to not knowing how to "pick safe curves". The analogous issue for standardized NIST PQ schemes is understood very well). So the hysteria around the transition, from an expert's perspective, is misplaced. This doesn't guarantee things will work. In cryptography there are no guarantees. In particular, failing to transition fast enough can also lead to vulnerabilities (by this I mean quantum attacks. Cryptographers are increasingly worried this may happen very soon. I've seen some estimate as soon as 2030). So there is an underlying tension in changing, and also a clear worry about not changing.
LoganDark 4mo ago
This post completely fails to address one of my biggest fears with a batched approach: waiting for a brand new certificate to be provisioned for a server that does not already have one. If batches are executed too frequently, then clients will have too big a database to maintain. If batches are executed too infrequently, then I have to wait a while to get my first certificate. Are they doing anything about this or is this just how it'll be with these new quantum-resistant certificates?
- some_furry 4mo ago
  They can't address it because nobody knows the answer yet. That's why their plans https://letsencrypt.org/2026/06/03/pq-certs#our-plans https://letsencrypt.org/2026/06/03/pq-certs#our-plans are to work with experts to solve the engineering challenges in the coming years, rather than announce a gift-wrapped solution today. If this fear of yours is particularly poignant, I invite you to share it with the forum so they have it in writing. It makes it easier for them to consider it as they work on a solution.
- mcpherrinm 4mo ago
  Great question! Of course, we'll continue to provide more information as we firm up more details. This is an area that's not locked down yet, but I can give a sneak preview of what it might look like. We expect batches to be produced quickly, on the same order of magnitude as current CT logs - somewhere in the 0.5s to 5 second range. This is an existing problem since (at least some) CT logs do the same batched behaviour. Now, there is a catch with MTCA: That gets you a "standalone" certificate, which works just like a certificate does today. But it's big, still. To get the new, small certificates (landmark-relative), you will have to wait for the next landmark. Based on current planning and discussions with Chrome, we expect that to be hourly for short-lived certs, and 4 hours for longer-lived certificates. So you'll get a big cert instantly, but you might have to wait an hour or 4 to get a certificate. So your new website can be online quickly, but with some downsides until you get the small landmark-relative cert. (I work at Let's Encrypt)
- agwa 4mo ago
  You'll be able to immediately use use a "standalone certificate" while waiting for the batch to be created. The tradeoff is that the standalone certificate will have multiple huge ML-DSA signatures.
z3ratul163071 4mo ago
no quantum threat. keep ed25519 and rsa, they are fine.
- HDBaseT 4mo ago
  Much love, from the NSA!
- mswphd 4mo ago
  Nation states have been pouring billions into QC. It's hard to collect the varous announcements into clean figures, but rough estimates are that the US has allocated ~$5B to QC computation research, the EU (via the EU itself, and individual member states) have allocated more (closer to ~$10B-15B), and China has allocated a similar amount (again in the ~$10B range). Industry quantum computing has made precipitous progress in the last few years, leading to industry companies (e.g. Cloudflare) to upping their personal targets for transition to 2029. You can read their motivation in the first few paragraphs of the following https://blog.cloudflare.com/post-quantum-roadmap/ https://blog.cloudflare.com/post-quantum-roadmap/ We are currently in a place where it is entirely plausible that nation states will have quantum computers capable of breaking EC crypto (and RSA, although paradoxically it is mildly harder to break quantumly due to larger data sizes) by 2030. This is not guaranteed. But there have been increasingly many warning signs. Maybe you don't care, and want to bury your head in the sand. That's your prerogative. But cryptographers do care, and so are taking all of the above very seriously.
  - z3ratul163071 4mo ago
    "Industry quantum computing has made precipitous progress in the last few years": the quantum industry in reality: "Using Shor’s algorithm, the largest integer factored into primes is 15" :)))
emulio 4mo ago
[flagged]
sureglymop 4mo ago
From the article not everything is fully clear to me yet. What I do think though, is that Certificate Transparency as we currently have it is a fairly broken mess. Maybe partly due to RFC 6962. The easiest task might just be validating SCTs. Easy, you just validate a signature... But no, that doesn't yet prove that the cert has been logged, that requires doing an inclusion proof! So, someone can do inclusion and consistency proofs. If a log presents a split view that should be noticable through gossiping. But what gossiping is implemented? I think the only gossiping that happens is in the CT Google group/mailing list that probably few people know of. Then, what if you want to actually detect malicious or misissued certs for your domain? Ideally you want to do it yourself and not use some service. Probably you just have one server and IP. Now you have to download insane amounts of data from ~60 logs and hope that someone else is checking the consistency and correctness of those logs. And you have to scrape those logs faster than they grow. Now, what if everyone running a web server did monitor? Even static logs probably couldn't withstand that. Next, what about the log lists? One can talk all about sovereignty but really you rely on and have to trust Apple and Google with their policies and log lists if you want to meaningfully participate in this system and by extension, the encrypted web... CT is fully deployed to production but still has many design flaws and things that are still just theoretical. It seems many of them are addressed by MTCs. I hope it can be better. The one thing I didn't see addressed is the gossiping thing. Couldn't a malicious CA still present a split view under this model? And if I'll have to rely on mirrors then I still can't independently monitor.
- mcpherrinm 4mo ago
  Yes, many of the problems from CT are fixed. I wouldn't call it a "broken mess" though, as it has been relatively effective at detecting various problems, and to my knowledge hasn't been compromised. There are no SCTs, which were a compromise to get CT shipped. Each Merkle Tree Certificate has an actual inclusion proof in it. CT has multiple independent logs, and requires certs to be logged to 2+ of them. With MTC, you have one issuing log, along with signatures from other "witnesses" which monitor and mirror log integrity. Those co-signatures are validated when checking the certificate. Thus the witness network makes it much harder for logs to fork, as you can't present a forked view to just the client. You also need to present it to a witness. And it'll be much easier for folks to check all the witnesses are in sync. Monitoring the MTC logs will be easier than CT, as they'll actually be smaller than CT for a few reasons. At least for the initial version, there won't be a better way to monitor for mis-issued certificates for a particular domain than linear scanning all certificates, but that's a problem being worked on for both CT and MTC, called "verifiable indexes".
rmac 4mo ago
in-case core-devs from LE lurk here: check out Cordon, a draft-ietf-plants-merkle-tree-certs-03 compliant CA and ACME server. its being used in a private mixnet now. bonus points: its AOT compiled dotnet https://github.com/maceip/cordon https://github.com/maceip/cordon
alansaber 4mo ago
So what's the timeline for a quantum future? 20 years? 50 years? 100? My concern is that it's primarily a materials science problem (hence, it is going to take a very long time).
- upofadown 4mo ago
  If you specifically mean something that can embody Shor's algorithm, it is fairly clear these days that a fundamental breakthrough is required. So the timeline extends from tomorrow to never.

320 points by SGran 4mo ago

lukan 4mo ago

Better encryption sounds good to me in general, but I don't really understand, how we can make quantum safe encryption, when we don't know yet, what capabilities it will have (or if it is possible at all). I am obviously not in the field, but as far as I know, no QC is close of working for a practical purpose(aside quantum research), but to make it practical, it needs a groundbraking brakethrough of some sort. But if a brakethrough happens, can we really estimate the consequences?

rcxdude 4mo ago
The capabilities of quantum computing, in theory, are pretty well known. There's basically a few extra operations which can be done efficiently on it and so that can be built into the threat model, even if no-one's built a quantum computer yet. (Of course, basically all encryption, especially asymmetric encryption, is predicated on there not being some as-yet-undiscovered exploitable structure to the mathematics on which it is built. Modern cryptography, AFAIK, tends to have some decent arguments for why this is not expected to be the case, but it's never completely proven top-to-bottom outside of fairly niche/trivial cases. It's always in principle possible that someone discovers an attack on these new algorithms, classical or quantum)
- chadgpt3 4mo ago
  Supersingular Isogeny Key Exchange is one that was invented to be quantum-safe but turned out to be unsafe at any speed, so hybrid encryption is still a good idea. You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.
  - some_furry 4mo ago
    > You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken. No. Don't do that. If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. You want a Hybrid KEM, not encrypting twice. The nuance matters. https://durumcrustulum.com/2024/02/24/how-to-hold-kems/ https://durumcrustulum.com/2024/02/24/how-to-hold-kems/
    - insanitybit 4mo ago
      > If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?
      - some_furry 4mo ago
        If you encrypt your data twice (taken very literally): c1 = E1(p, k1) c2 = E2(p, k2) If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p. What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken. ss1, ct1 = KEM1(pk1) ss2, ct2 = KEM2(pk2) secret = Combiner(ss1, ss2, [ct1, [ct2]]) This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated. This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations. I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
        3form 4mo ago
        It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
  - tptacek 4mo ago
    No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices. People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.
    - mswphd 4mo ago
      Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU. He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now. In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world. This is ignoring all of his other explicitly embarrassing behavior, for example 1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly. 2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust. 3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.
  - mswphd 4mo ago
    The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places. The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve. So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.
n4r9 4mo ago
The problem is perhaps more theoretical than you might think. The security of post-quantum schemes basically comes down to the fact that researchers have thought long and hard about whether there are efficient classical or quantum algorithms to solve a given problem, and haven't found any yet. That's not necessarily anything new. Even RSA is predicated on no one having a fast factorisation algorithm.
BoppreH 4mo ago
To answer your "if it's possible at all" question: it's full of hard engineering problems, but none of it looks unsolvable, and the investments are there. And even if there was only a 10% chance of QC breaking crypto, the community is not comfortable with a 10% chance of such a catastrophic scenario. This is part of my day job, so here's another interesting fact: for migrating encryption use cases, you have to consider that attackers can capture your encrypted data today to break in the future. So, as a rule of thumb, your migration timeline is much shorter for encryption than for signatures.
thenthenthen 4mo ago
I guess how technology and policy paths are layed out? It is basically a wish list. Like we already have the spec for 7G mobile comms decades ahead …(https://www.techsciresearch.com/blog/5g-vs-6g-vs-7g-unveiling-the-future-of-connectivity/4485.html https://www.techsciresearch.com/blog/5g-vs-6g-vs-7g-unveilin... )
fxwin 4mo ago
Well similar to how turing machines are a sufficient theoretical model to make all kinds of arguments about runtime complexity of classical computers without relying on their actual physical implementation, we have theoretical models for the way we are approaching quantum computation that do the same thing (Namely the quantum circuit model)
tsimionescu 4mo ago
By this standard, there is no current encryption method (except for pre-shared one time pads when used correctly) that is known to be unbreakable. For example, it is not proven that prime factoring can't be done much more efficiently on a classical computer - for all we know, it's possible that tomorrow someone will come up with a novel algorithm that can break RSA in just a small number of operations. Same is true for elyptic curves - we don't have any mathematical proof that it's impossible for a much better algorithm than the currently known ones is possible. However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't. In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP. So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.
- Cider9986 4mo ago
  Would post-quantum encryption also be harder for regular computers to crack?
  - some_furry 4mo ago
    The international standardization effort that led to ML-KEM and ML-DSA focused both on classical attacks (regular computers) and quantum attacks. There were 5 levels being considered for each submission. Level 1 - at least as difficult to attack as AES-128 (block cipher) Level 2 - at least as difficult to attack as SHA-256 (hash function) Level 3 - at least as difficult to attack as AES-192 (block cipher) Level 4 - at least as difficult to attack as SHA-384 (hash function) Level 5 - at least as difficult to attack as AES-256 (block cipher) The security of attacking an N-bit block cipher is morally congruent to a birthday collision against a {2N}-bit hash function. With some caveats: https://soatok.blog/2024/07/01/blowing-out-the-candles-on-the-birthday-bound/ https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th... ML-DSA-44 (smallest parameter set) targets Level 2 for signatures. ML-KEM-768 targets Level 3 for KEMs.
chasil 4mo ago
These are/will be the fundamentals of quantum logic. https://en.wikipedia.org/wiki/Quantum_logic_gate https://en.wikipedia.org/wiki/Quantum_logic_gate
jerf 4mo ago
In addition to the other fine answers, I personally find the additional operations that quantum computers enable to be surprisingly inapplicable to a lot of real problems. It's really kind of unimpressive when you dig down into it. It is not a revolution of computing as we know it, it's a very, very expensive accelerator card for a few niche problems. Neat for people who have those problems. But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does. I think there is a sense in which we have a historical accident that has make quantum computers sound bigger than they are, in that we ended up with "factoring prime numbers" being the first thing we had to make practical encryption out of, and by what is from a human perspective mostly a coincidence, it so happens that quantum computers may be really good at that. But the problem is that quantum computers happen to be good at factorizing that is the problem, not that quantum computers are somehow "good at breaking encryption". It seams to me that in some sense "post-quantum computing" is actually "all practical encryption schemes except those based on factoring large numbers". Breaking large prime number-based schemes is the exception that QC happens to be good at, not the rule.
- kibwen 4mo ago
  > But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does. I think it's very funny to consider that if you were a time traveler tasked with making sure that humanity had the economic incentive to develop quantum computers, the most efficient way to ensure that in a single stroke would be by suggesting the use of prime factorization as a trapdoor function to Rivest, Shamir, or Adleman.
- adgjlsfhk1 4mo ago
  it's not just factoring, but general discrete log over abelian groups
  - jerf 4mo ago
    Yes, sorry, I didn't mean to imply they could only "factor". But the things they can do that they get the big advantage over classical computing I find underwhelming when considered against the entire scope of computing problems. Again, great for the people who have those problems, but I still am not sure that they are "worth" what are being poured into them in terms of any real economic impact they have. I do wonder if I could trace back all the money in the sector to their original source just how much of it would end up being the intelligence sector who wants their crackz, and how valuable it'll end up being to them in the end if they can't get a decent crack before we all go post-quantum encryption anyhow.
hylaride 4mo ago
It's essentially the laws of physics. To oversimplify, Quantum computing can essentially do certain kinds of operations extremely fast (like factoring prime numbers) because it can calculate all the permutations almost instantly. But if you add intentional complexity to it in ways that all those states can't be "seen" then the quantum computer falls flat. That's one of the issues with adding post-quantum algorithms, they're by design less efficient in certain ways, meaning slower and/or with more overhead. The way a quantum mechanics PhD explained it to me years ago in layman's terms is similar to nuclear science. We "knew" that a nuclear explosion was possible before a bomb was created and what conditions it would work. The Nagasaki bomb was a completely different type of bomb than the trinity test and Hirosima, plutonium instead of uranium, and it was never even tested before it's first use!
- mswphd 4mo ago
  this is not an accurate description/heuristic of how quantum computing works. It would predict quantum computers can solve problems that they cannot solve. For a more accurate account see e.g. https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/ https://www.quantamagazine.org/thirty-years-later-a-speed-bo... And the post-quantum algorithms are not by design less efficient either. For example, RLWE-based schemes are more cycle-efficient than elliptic curve schemes. They're not uniformly more efficient (key/ciphertext sizes are generally longer), but this has nothing to do with intentional design choices to make them post-quantum secure. Just different things are different.
  - hylaride 4mo ago
    Fair. I was quoting from memory from maybe 5 years ago.
- tatersolid 4mo ago
  Clarification/correction: The Nagasaki “Fat Man” bomb was the same plutonium implosion design tested at Trinity. The Hiroshima “Little Boy” bomb was the uranium “gun” design that was never tested before combat use. The physics and engineering were comparably straightforward so the scientists were very sure it would work assuming the Urnaium enrichment was pure enough.
Tangurena2 4mo ago
Bruce Schneier's books explain that there is far more to security than better encryption. Most are implemented incorrectly or used incorrectly.
- avadodin 4mo ago
  I also liked the memes. Too bad they died out after he failed with Skein.

BoppreH 4mo ago

Interesting development. Merkle Tree Certificates throw away decades of cruft, but also decades of battle testing and ancillary tools. I trust the teams involved, but this will be a hell of a project. Still better than the alternatives that would saddle us with worse performance for ~ever.

quantumscan 4mo ago
[flagged]
throwaway01632 4mo ago
Is there any value in first encrypting with a battle tested algorithm, and then encrypt again with the new algorithm?
- BoppreH 4mo ago
  Yes! It's called a hybrid cryptosystem, and what most projects are planning to use. The algorithms at risk are the asymmetric part (RSA, ECC, DH), not the symmetric parts (AES, ChaCha), so what is done for encryption is "generating" a secret with ML-KEM and another with ECC, combining them, and using that as key for AES or another symmetric algorithm for the actual encryption. So if you break only ECC or only ML-KEM, you don't get the combined secret. ML-KEM keys/ciphertext are small and efficient enough that this overhead is generally a non-issue. Note that ECC can be used in many ways: asymmetric encryption, key encapsulation, or signatures. ML-KEM, the new post-quantum standard, is only a Key Encapsulation Mechanism. Hence the "generate an AES key" step, instead of "encrypt a random AES key". For signatures, like in the announcement in the post, things are more complicated. The post is a very good introduction to the problem.
  - mswphd 4mo ago
    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/ 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).

kibwen 4mo ago

> In the common case, the entire authentication path in an MTC handshake is one signature, one public key, and one inclusion proof. That’s smaller than today’s Web PKI handshake, even though MTCs use post-quantum algorithms. [...] There is more to MTCs than size optimization. Because every certificate is part of a published Merkle tree, transparency becomes a property of issuance itself. Today’s Certificate Transparency ecosystem is bolted on after the fact: certificates are issued by CAs, then logged separately, with extra signatures riding along in the TLS handshake to attest to that logging. With MTCs, a certificate cannot exist outside the Merkle tree. Certificate Transparency is built in. These upsides seem extremely promising, but I'm curious to know if there are any notable downsides as well.

2close4comfort 4mo ago
I too was wondering how they feel about the potential downsides which is not really mentioned.
Cyfrit 4mo ago
The main downside is shifting from inline validation to out-of-band state syncing. For handshakes to stay small, browsers must constantly cache fresh "landmarks." If a device has been offline and hits a flaky hotel captive portal, it lacks these landmarks and triggers a fallback with massive inline ML-DSA signatures—bloating the handshake to 10KB+ exactly when the network is at its worst. It essentially turns a crypto size problem into a browser background syncing challenge.
- kmori_de 4mo ago
  [flagged]
agwa 4mo ago
The downside is that to get the size optimization, TLS servers will get moderately more complicated (they'll need to have multiple MTC certificates configured and select the right one depending on the client's state), and TLS clients will get considerably more complicated (they'll need to continuously download landmarks for each CA out-of-band from a trusted source). I expect many non-browser TLS clients won't support the small landmark-relative certificates, because there isn't a clear party to operate the landmark distribution service (Chrome has Google, and Firefox has Mozilla, but who does curl have?). I'm also worried that support will be lacking in open source TLS servers, though that's a more tractable problem. Consequentially, I expect the large standalone certificates to be quite common outside of connections between browsers and CDNs.

tomgag 4mo ago

Refreshing! Not wanting to be the "told you so" guy, I've been saying this for at least 2 years now: > Post-quantum authentication is no longer a problem the Web PKI ecosystem should defer. Long-lived keys (root certificate authorities, code-signing keys, identity systems) are particularly valuable targets, and new technology takes years to gain broad adoption, so the work has to start early. This is a problem that I have met so many times talking with people: they parrot the "Harvest-Now-Decrypt-Later is the only urgent problem, signatures can wait" mantra, and this piece of misinformation has spread so much that even AI repeats it (because it has been trained on open data, where the overwhelming sentiment has been following this trend), thereby reinforcing the problem. Ask Claude/ChatGPT/Gemini about the problem, and they will invariably tell you that signatures are less urgent because theyr are not subjective to retroactive compromise. There are two problems here. The first one is included by the Letsencrypt announcement: the migration path for signatures/certificates is typically longer and more complex than encryption: long-lived certificates, firmware update keys, secure boot certificates, these are all objects that are painful to migrate. The second one, even more serious in my opinion, is: "retroactive" in respect to what? "Retroactive" presupposes you can observe the trigger (the arrival of a cryptanalytically-relevant quantum computer), but this is precisely the kind of capability an adversary keeps secret, and a quantum forgery is operationally indistinguishable from, e.g., key exfiltration, a library bug, or a classical break. You may see a forged signature, a drained wallet, a failing certificate, and have no way to attribute it to quantum cryptanalysis. The threat is dark: reactive migration against an unobservable trigger is structurally impossible. This is not to say that Harvest-Now-Decrypt-Later is a less urgent threat, but it's not so asymmetric as people have been believing so far. Glad to see things are changing!

some_furry 4mo ago
> Refreshing! Not wanting to be the "told you so" guy, > This is a problem that I have met so many times talking with people: they parrot the "Harvest-Now-Decrypt-Later is the only urgent problem, signatures can wait" mantra, and this piece of misinformation has spread so much that even AI repeats it (because it has been trained on open data, where the overwhelming sentiment has been following this trend), thereby reinforcing the problem. Ask Claude/ChatGPT/Gemini about the problem, and they will invariably tell you that signatures are less urgent because theyr are not subjective to retroactive compromise. I can't speak to public sentiment, but the stance I've held for years was roughly: HNDL is more urgent because people are already encrypting messages today that could be decrypted in the future if a quantum computer is ever built in the foreseeable future, and that harms their privacy for the entirety of human history until PQC is rolled out. That's not the same as "authentication doesn't matter at all". It was, if you must pick a problem to solve today, this one will stop the bleeding sooner. But they were always both important to solve. The question was whether we could delay PQ auth until better signature algorithms were deployed. The Google/Cloudflare 2029 decision signaled to the rest of us: "No, we need to start the migration now."

skmurphy 4mo ago

We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for. In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise.

firesteelrain 4mo ago
That sounds a lot like Shamir Secret Sharing Algorithm similar to unsealing / sealing HashiCorp Vault. I did read the books 20 years ago and forgot this aspect of the story
tialaramex 4mo ago
But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on. OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" approach barely dents our symmetric cryptography. I've written about this before, DES was standardized in 1977, almost 50 years ago and you might think "Well but DES is broken". Yes, DES broke exactly the way it was designed to. Literally nothing went wrong, when it was standardized we knew the keys are too small (yup, you can break it by trying all the keys) and the blocks are too small (yup, you can "just" make duplicate blocks) and it was broken by leaning on these weaknesses with huge fast modern computers. AES is an entirely different cryptosystem, but the two most important choices were that the keys are big enough (128-bit or 256-bit commonly) and the blocks are too (128 bits). And those may seem like a small upgrade, only 2-4x as big, who cares? Well those are bit lengths so that's an exponential increase, and your quantum computer barely helps (assuming it magically is the same price rather than incredibly expensive). It is not physically practical for the necessary computation to be done, AES is broken only if there's some mathematical backdoor we didn't know about. "We'll crack AES with a quantum computer" is a Hollywood movie plot, it's not a thing that makes any actual sense. [Edited: I wrote "Bruce Sterling" but I meant "William Gibson", I apologise to both people for muddling them, though not for my opinion]

z3ratul163071 4mo ago

nsa and eu pushing for replacement of the reliable algorithms with unproven and very likely backdoored post-quantum algorithms, when there is no real threat at all, is highly suspicious.

some_furry 4mo ago
> and very likely backdoored post-quantum algorithms Citation needed Here's mine: https://keymaterial.net/2025/11/27/ml-kem-mythbusting/ https://keymaterial.net/2025/11/27/ml-kem-mythbusting/
- z3ratul163071 4mo ago
  nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. i have no knowledge, nor time to eval. (and probably few people do) all i am saying is there is no good reason to depreciate proven algs, especially not because those two institutions said so.
  - tptacek 4mo ago
    That's not what you said. You said that the algorithms were "very likely backdoored", despite the fact that neither NSA nor the EU had any hand in actually designing them.
  - some_furry 4mo ago
    > nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. Who do you trust, then? > i have no knowledge, nor time to eval. (and probably few people do) If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions? Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced ML-KEM and ML-DSA? Or do you just balk at experts and "trust no one" even to your own detriment?

raphinou 4mo ago

I've been working on a new project using ed25519 signatures and discovered they are not quantum resistant.... I went with ed25519 due to possibility of using openssh keys. Any opinion on this choice at the light of this article and other quantum computing news?

some_furry 4mo ago
There's an IETF RFC draft for mldsa-44 keys for OpenSSH. https://datatracker.ietf.org/doc/draft-rpe-ssh-mldsa https://datatracker.ietf.org/doc/draft-rpe-ssh-mldsa I'm not aware if it has any real traction, but that's what I found with a quick search.
- mcpherrinm 4mo ago
  OpenSSH's Damien Miller has https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-ed25519-composite-sigs/ https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-e... defining ssh-mldsa44-ed25519@openssh.com which seems more likely given the authorship.
  - some_furry 4mo ago
    Sure, but that's a composite scheme, and I dislike those. :P
tardedmeme 4mo ago
Signatures aren't as urgent to replace as encryption keys are. You can wait until someone is about to build a quantum computer, then change all your signatures. Encrypted data is more critical because the NSA's going to store all internet traffic for centuries if it thinks it can decrypt it later.
- JoachimS 4mo ago
  No, very much no. If store now decrypt later is the problem, then we basically have no problem (Just like what Peter Gutmann argues [2]). The vast, basically all communication over for example TLS need confidentiality in minutes, hours. Not 30-100 years. My bank statement right now, the plans we discuss for the project next year etc. But what is very important crucial, what makes our digital world including secure communication, web commerce possible is the web of trust - identification and authentication. I'd claim that the important part of TLS including certs is this part. We could by and large not need the confidentiality. But since it costs so comparatively little we can just as well always encrypt too. You seem to think that changing a certificate is something we can fix in minutes. Globally. The reality is far from that. Esp in things that are not just your browser. Things like network equipment, FW for basically every embedded system, cars, busses. And crucially for critical entities. These things have long lifespans (decades), often need manual intervention to change certificates (connect a JTAG, serial intercace), possible even replacement. But replacing root certs in all our normal devices - phones, laptops etc are also far from easy and done in minutes. Then you have all digital identification solutions - from ID cards, car fobs, 2FA tokens, passports, credit cards. You may have to replace millions of physical things, even distribute to whole populations. And back to the web. If we can crack an RSA-2048 key in 24 hours (which is the measure used when guessing we have QC capable enough [1]). We really don't have that many CAs. The times they have had problems have caused problems that have taken days, weeks to trickle down. Having CA issue new rootcerts several times a day isn't viable. So I'd wager that transitioning to PQC safe certificates, authentication isn't something we can wait with. It will take years and huge efforts - not minutes and when the problem hits us. If you look at time plans for transitioning to PQC from CNSA, EU, UK and others, the area they all list as most critical to complete transition as soon as possible for is SW, FW-signing for infrastructure, embedded systems [1]. So, in reality unless you have a legal responsibility for keeping state secrets then store now, decrypt later is not really your main reason for PQC transitioning. Authentication very much is. Unfortunately most cryptographers by large seems to miss this. And people in uniform have a large saying, influence in the debate. My guess is that this is because gov to a large degree finance a lot of the QC research and they have a different threat model that most of the world. But that is just my guess. As Gutmann argues, we don't even really know that there even is a viable store now, decrypt later threat. Unless you can pinpoint the exact TLS session that is interesting, you can't store or decrypt all traffic that may be the interesting ones (if we assume that the cost of breaking a single RSA is not zero and takes minutes, seconds. Not 24 hours). And if indeed if TLS and normal key exchange mechanisms, are really used for those juicy messages. [0] https://globalriskinstitute.org/publication/quantum-threat-timeline-report-2025b/ https://globalriskinstitute.org/publication/quantum-threat-t... [1] https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS.PDF https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA... [2] https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf

some_furry 4mo ago

https://soatok.blog/2026/04/13/hybrid-constructions-the-post-quantum-safety-blanket/ https://soatok.blog/2026/04/13/hybrid-constructions-the-post... I wrote this in April. Many folks' misconceptions about post-quantum cryptography and "hybrid" constructions are answerable with this blog post.

thyristan 4mo ago
There is nothing answered in there. Just "It'll be fine" and vague pointing at unrelated ecc vulnerabilities in some libs. It totally lacks any rational arguments.
- some_furry 4mo ago
  No shit. It is a blog post, not an academic paper or Lean proof. My blog posts are supposed to be informal and conversational, not pure logic. If you want "ratioanl arguments", look elsewhere than personal blogs.
- mswphd 4mo ago
  the rational argument is that this time is not particularly worse than prior transitions, and arguably is one we are doing much more clear-eyed (think about all the ECC vulnerabilities during their first few years of deployment due to not knowing how to "pick safe curves". The analogous issue for standardized NIST PQ schemes is understood very well). So the hysteria around the transition, from an expert's perspective, is misplaced. This doesn't guarantee things will work. In cryptography there are no guarantees. In particular, failing to transition fast enough can also lead to vulnerabilities (by this I mean quantum attacks. Cryptographers are increasingly worried this may happen very soon. I've seen some estimate as soon as 2030). So there is an underlying tension in changing, and also a clear worry about not changing.

LoganDark 4mo ago

This post completely fails to address one of my biggest fears with a batched approach: waiting for a brand new certificate to be provisioned for a server that does not already have one. If batches are executed too frequently, then clients will have too big a database to maintain. If batches are executed too infrequently, then I have to wait a while to get my first certificate. Are they doing anything about this or is this just how it'll be with these new quantum-resistant certificates?

some_furry 4mo ago
They can't address it because nobody knows the answer yet. That's why their plans https://letsencrypt.org/2026/06/03/pq-certs#our-plans https://letsencrypt.org/2026/06/03/pq-certs#our-plans are to work with experts to solve the engineering challenges in the coming years, rather than announce a gift-wrapped solution today. If this fear of yours is particularly poignant, I invite you to share it with the forum so they have it in writing. It makes it easier for them to consider it as they work on a solution.
mcpherrinm 4mo ago
Great question! Of course, we'll continue to provide more information as we firm up more details. This is an area that's not locked down yet, but I can give a sneak preview of what it might look like. We expect batches to be produced quickly, on the same order of magnitude as current CT logs - somewhere in the 0.5s to 5 second range. This is an existing problem since (at least some) CT logs do the same batched behaviour. Now, there is a catch with MTCA: That gets you a "standalone" certificate, which works just like a certificate does today. But it's big, still. To get the new, small certificates (landmark-relative), you will have to wait for the next landmark. Based on current planning and discussions with Chrome, we expect that to be hourly for short-lived certs, and 4 hours for longer-lived certificates. So you'll get a big cert instantly, but you might have to wait an hour or 4 to get a certificate. So your new website can be online quickly, but with some downsides until you get the small landmark-relative cert. (I work at Let's Encrypt)
agwa 4mo ago
You'll be able to immediately use use a "standalone certificate" while waiting for the batch to be created. The tradeoff is that the standalone certificate will have multiple huge ML-DSA signatures.

z3ratul163071 4mo ago

no quantum threat. keep ed25519 and rsa, they are fine.

HDBaseT 4mo ago
Much love, from the NSA!
mswphd 4mo ago
Nation states have been pouring billions into QC. It's hard to collect the varous announcements into clean figures, but rough estimates are that the US has allocated ~$5B to QC computation research, the EU (via the EU itself, and individual member states) have allocated more (closer to ~$10B-15B), and China has allocated a similar amount (again in the ~$10B range). Industry quantum computing has made precipitous progress in the last few years, leading to industry companies (e.g. Cloudflare) to upping their personal targets for transition to 2029. You can read their motivation in the first few paragraphs of the following https://blog.cloudflare.com/post-quantum-roadmap/ https://blog.cloudflare.com/post-quantum-roadmap/ We are currently in a place where it is entirely plausible that nation states will have quantum computers capable of breaking EC crypto (and RSA, although paradoxically it is mildly harder to break quantumly due to larger data sizes) by 2030. This is not guaranteed. But there have been increasingly many warning signs. Maybe you don't care, and want to bury your head in the sand. That's your prerogative. But cryptographers do care, and so are taking all of the above very seriously.
- z3ratul163071 4mo ago
  "Industry quantum computing has made precipitous progress in the last few years": the quantum industry in reality: "Using Shor’s algorithm, the largest integer factored into primes is 15" :)))

emulio 4mo ago

[flagged]

sureglymop 4mo ago

From the article not everything is fully clear to me yet. What I do think though, is that Certificate Transparency as we currently have it is a fairly broken mess. Maybe partly due to RFC 6962. The easiest task might just be validating SCTs. Easy, you just validate a signature... But no, that doesn't yet prove that the cert has been logged, that requires doing an inclusion proof! So, someone can do inclusion and consistency proofs. If a log presents a split view that should be noticable through gossiping. But what gossiping is implemented? I think the only gossiping that happens is in the CT Google group/mailing list that probably few people know of. Then, what if you want to actually detect malicious or misissued certs for your domain? Ideally you want to do it yourself and not use some service. Probably you just have one server and IP. Now you have to download insane amounts of data from ~60 logs and hope that someone else is checking the consistency and correctness of those logs. And you have to scrape those logs faster than they grow. Now, what if everyone running a web server did monitor? Even static logs probably couldn't withstand that. Next, what about the log lists? One can talk all about sovereignty but really you rely on and have to trust Apple and Google with their policies and log lists if you want to meaningfully participate in this system and by extension, the encrypted web... CT is fully deployed to production but still has many design flaws and things that are still just theoretical. It seems many of them are addressed by MTCs. I hope it can be better. The one thing I didn't see addressed is the gossiping thing. Couldn't a malicious CA still present a split view under this model? And if I'll have to rely on mirrors then I still can't independently monitor.

mcpherrinm 4mo ago
Yes, many of the problems from CT are fixed. I wouldn't call it a "broken mess" though, as it has been relatively effective at detecting various problems, and to my knowledge hasn't been compromised. There are no SCTs, which were a compromise to get CT shipped. Each Merkle Tree Certificate has an actual inclusion proof in it. CT has multiple independent logs, and requires certs to be logged to 2+ of them. With MTC, you have one issuing log, along with signatures from other "witnesses" which monitor and mirror log integrity. Those co-signatures are validated when checking the certificate. Thus the witness network makes it much harder for logs to fork, as you can't present a forked view to just the client. You also need to present it to a witness. And it'll be much easier for folks to check all the witnesses are in sync. Monitoring the MTC logs will be easier than CT, as they'll actually be smaller than CT for a few reasons. At least for the initial version, there won't be a better way to monitor for mis-issued certificates for a particular domain than linear scanning all certificates, but that's a problem being worked on for both CT and MTC, called "verifiable indexes".

rmac 4mo ago

in-case core-devs from LE lurk here: check out Cordon, a draft-ietf-plants-merkle-tree-certs-03 compliant CA and ACME server. its being used in a private mixnet now. bonus points: its AOT compiled dotnet https://github.com/maceip/cordon https://github.com/maceip/cordon

alansaber 4mo ago

So what's the timeline for a quantum future? 20 years? 50 years? 100? My concern is that it's primarily a materials science problem (hence, it is going to take a very long time).

upofadown 4mo ago
If you specifically mean something that can embody Shor's algorithm, it is fairly clear these days that a fundamental breakthrough is required. So the timeline extends from tomorrow to never.