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.
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]
> 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.
That feels a bit harsh when reading a book written in 1992. Shor's algorithm was only invented in 1994. There was no indication about our quantum future at the time that novel was written
A Fire upon the deep is set in the far future. Its easy to imagine all non information-theoretic secure cryptosystems failing thousands of years from now. I think that prediction is more reasonable than most far-future scifi predictions.
If i remember right, i think that is the novel that predicts we'd still be using usenet when talking between planets (i read a long time ago), so i think the crypto prediction aged a lot better than that.
[Vinge](https://en.wikipedia.org/wiki/Vernor_Vinge) was a professor of mathematics and computer science. I'd expect him to get things right. Funny enough I don't remember that bit at all from fire upon the deep.
it's worth noting that the zones of thought universe literally had different physics; things like superintelligence and ftl travel were physically impossible closer to the galactic centre but commonplace further out. so the notion of "not physically practical" doesn't apply here.
It's worth noting that the above assumes that grover's is optimal for symmetric crypto. There are not that many quantum attacks against symmetric crypto that are better than grover's, so in some sense this is justified. But there are some attacks for particular constructions
So there is a risk that there are even more improved attacks that people aren't looking for due to the conventional wisdom that grover's is the best you can do for symmetric crypto. Hopefully this risk doesn't end up materializing.
I have come to the conclusion that it doesn't matter. What matters is that people believe quantum computers will break encryption. And pulling that lever on their seeded fears, via subterfuge, backdoors, surveillance, and maybe a _little math, is too valuable for it not to be pulled.
I'd argue it's closer to a cheap insurance, just in case.
Take the encryption of a TLS connection itself, for example: you want to protect against a possible "store now, decrypt later" attack on your connection, 60 years from now, by an attacker with an NSA-level budget. Even if you judge the probability of it happening as "exceedingly unlikely", migrating to a hybrid scheme is a no-loss scenario, so it would be silly not to. In a way it's almost a Pascal's Wager.
And then there's of course the NSA itself, who are heavily pushing for post-quantum-only schemes and trying to suppress the hybrid schemes as they almost certainly have weaknesses for some of those new PQ schemes already lying around.
> as they almost certainly have weaknesses for some of those new PQ schemes already lying around
why believe this about PQ schemes vs about pre-existing schemes? Or any other schemes?
It's also worth mentioning that it appears that other countries (in particular China) will adopt fundamentally similar schemes. The NSA loves vulnerabilities, but generally only vulnerabilities of a certain type. These are generally referred to as "NOBUS"
It includes things like backdoors (say DUAL_EC_DRBG), as well as historically things like reducing the key size of DES, where the US thought they'd be able to brute force it (but other countries would lack the compute). Historically the NSA has actually assisted in removing non-NOBUS vulnerabilities (at least they did this with the SBOX design of DES, which was vulnerable to differential/linear cryptanalysis --- I forget which).
The NSA hasn't publicly assisted/disclosed any vulnerabilities with currently suggested schemes, though a close US ally (Isreal, through an IDF group known by Matzov) has. If America was hoarding vulnerabilities, one might imagine America would have pressured Isreal to keep this secret.
A final point is that it's not clear where the NSA would source the vulnerabilities. By a peculiar chain of coincidences, nearly all of the most successful lattice cryptanalysts are European. None have "gone dark" in a way that would be concerning (say how Don Coppersmith did, when he moved to a NSA affiliate in the mid 2000s). This isn't to say that it would be impossible for the NSA to have better-than-public vulnerabilities, but more to say that they can't just take some of the most successful people who have publicly attacked the problem, and throw more money at them. Their "talent-pipeline" for this particular problem is not as available (and many cryptographers soured on working with them post-Snowden anyway).
This is the second time in my life I’ve heard of this book. It was a wickedly weird book. I think I was 1/3rd through it before I figured out the plurality of the characters.
it's worth mentioning opinions have started to shift away from this. Quantum computing has made quite concrete progress in the last ~2 years. No guarantee this continues, but among people I know it has changed their perspectives from (roughly) similar things as that essay, to thinking we really must transition now.
Like if you want to go from history - yes the make a giant artillery piece thing didn't work.
You know what did work? A surprising application of quantum physics known as nuclear bombs.
I'm not neccesarily saying quantum computers will work out the same way, but if you follow the logic of the presentation, nuclear bombs fit it so much better than the example they use. It was a step-change. People went from saying it was theoretically interesting without practical application to actually having a bomb very quickly. Basically replace everything in that presentation using nukes as the running example and suddenly the argument sounds really stupid.
note that OTP is only "perfectly secure" for a rather limited notion of security, namely IND-CPA. This is (roughly) an "honest but curious" adversary who looks at data on the wire (or wherever), but never tampers with it.
This is not a particularly realistic attack model. People typically instead want security against an "active" adversary who does whatever they can (say IND-CCA2 security). You can achieve this information-theoretically, given enough pre-shared randomness, by (roughly) taking some standard Authenticated Encryption with Associated Data (AEAD) construction, and swapping out whatever primitives that are used with information-theoretically secure components. A OTP for the block cipher and a Wegmen-Carter MAC for the MAC should work.
Note that this gives you a scheme with roughly the same practical security as standard ones (unless you think someone can break AES), but it still can be subject to non-trivial attacks that AES cannot. In particular
1. randomness used on both sides MUST never be repeated, and MUST stay in sync throughout, so
2. both sides MUSt stay in sync as to where 1. they are in terms of the randomness they're using, and where 2. the other half of the communication is. Realistically these should be two completely different randomness streams to guard against race conditions where otherwise each side may accidentally reuse a block of randomness
3. having to stay in sync adds several difficulties. In particular, network issues become much more annoying to deal with. This is true for e.g. environmental network disruptions, but also (plausibly) an adversary can disrupt the network temporarily. If this causes you to lose synchronization, then best case this temporary network disruption becomes a permanent network disruption. Worst case it manages to get randomness re-used on one side, which then breaks everything.
The above is likely not an exhaustive list of the problems you have to deal with. But still, you can see how it quickly becomes unclear if things are easy to implement.
Most of the ways of making the “duplicated at each end” thing practical are just figuring out where to hide the stream cipher. Like, if you just use /dev/*random to generate the random bitstream, what you have is a convoluted output-feedback-mode cipher with a key of whatever was fed into the os's prng, not a one-time-pad.
In terms of actually doing it, it's still very remote, but not as remote as it would have to be for us to completely ignore it. And the NSA has massive data centers full of hard drives storing our encrypted internet traffic.
No, the idea is that the actual key is the XOR of 3 completely independent keys. I think you were thinking of XORing a key with itself 3 times, which would just return the original key.
In the book, there is a cargo ship carrying 1/3 of a OTP. Other two other ships from two other companies are carrying the other thirds. This actually is a fairly decent method of transporting a OTP (I'm assuming there's some kind of physical security preventing tampering).
The book even talks later on about how only using the pad isn't enough, since it provides no proof of authorship or tampering. Vinge did a pretty good job w/compsci in the book.
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.
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.
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.
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".
Okay that choice of words was a bit harsh. My struggles are partly also due to logs barely complying, that I can't even monitor as quickly as they grow from one IP (mainly looking at you, trustasia, though at least there now is a static log).
Thank you for the explanations. I think I should read the draft RFC.
The last part of your comment caught my attention, seems great if that is being worked on. Can I find more information on it somewhere?
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).
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.
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?
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.
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.
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.
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.
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.
> 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.
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.
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?
On Linux and similar systems, I'm hoping github.com/rustls/upki will handle landmark distribution, and that non-browser clients can use that. Of course Rustls will support their own project, but I'm hopeful other TLS stacks do too. Ubuntu announcing they're deploying it should help with that.
On other OSes (like Mac OS and Windows), there's also OS-level services which could support this.
It would be a shame if we end up with a bunch of copies of this data, so I think a shared OS service is the only reasonable approach.
The hardest part is going to be smaller embedded systems.
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.
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?
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.
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.
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 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.
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
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.
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!
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.
> 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."
Yes, totally agreed, but the problem is that most people tend to simplify this as "let's just bother with PQ encryption, forget about signatures". I know experts can handle the nuance, but execs and most industry folks can't. Or, at least, this is the trend that I have personally observed countless times, maybe I was just unlucky with my data points, but I have seen this in "technical" settings as well (case in point: GnuPG prioritized inclusion of PQ hybrid encryption, to the point of rushing the standard against OpenPGP, the well-known "GnuPG schism", but I'm not aware of concrete plans for PQ signature adoptions there).
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.
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).
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.
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?
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)
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.
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.
this is broadly true. I've heard some criticisms of industrial QC research along these lines, namely that it runs into the issue that its entire TAM ends up being some combination of
1. defense contracting, which can definitely be lucrative, but (hopefully) will dry up quickly after the PQ transition (and especially will if we successfully transition before QCs are advanced enough, which is the goal), and
2. theft, with things like e.g. stealing bitcoins or whatever.
The second is plausibly a large market. It may be difficult to put it on a quarterly report though. So the economic basis industrial QC research may not end up panning out.
> 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.
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.
Has there been "no progress" on classical prime factorization? What about the AKS primality test, a polynomial-time algorithm to test the primality of a number, published in 2002? (This is not my field of expertise; I'm genuinely curious if there's a good reason to discount this as progress towards efficient prime factorization)
> except for pre-shared one time pads when used correctly
The relevant property here is known as "information-theoretic security", and I'm not sure if one-time pads are the only way to achieve it, e.g. Shamir's secret sharing also has this property (although the use case is slightly different): https://en.wikipedia.org/wiki/Information-theoretic_security
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.
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)
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.
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!
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.
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.
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.
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.
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]
> 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.
That feels a bit harsh when reading a book written in 1992. Shor's algorithm was only invented in 1994. There was no indication about our quantum future at the time that novel was written
A Fire upon the deep is set in the far future. Its easy to imagine all non information-theoretic secure cryptosystems failing thousands of years from now. I think that prediction is more reasonable than most far-future scifi predictions.
If i remember right, i think that is the novel that predicts we'd still be using usenet when talking between planets (i read a long time ago), so i think the crypto prediction aged a lot better than that.
2 replies →
[Vinge](https://en.wikipedia.org/wiki/Vernor_Vinge) was a professor of mathematics and computer science. I'd expect him to get things right. Funny enough I don't remember that bit at all from fire upon the deep.
8 replies →
it's worth noting that the zones of thought universe literally had different physics; things like superintelligence and ftl travel were physically impossible closer to the galactic centre but commonplace further out. so the notion of "not physically practical" doesn't apply here.
5 replies →
It's worth noting that the above assumes that grover's is optimal for symmetric crypto. There are not that many quantum attacks against symmetric crypto that are better than grover's, so in some sense this is justified. But there are some attacks for particular constructions
https://arxiv.org/pdf/2110.02836
So there is a risk that there are even more improved attacks that people aren't looking for due to the conventional wisdom that grover's is the best you can do for symmetric crypto. Hopefully this risk doesn't end up materializing.
2 replies →
I have come to the conclusion that it doesn't matter. What matters is that people believe quantum computers will break encryption. And pulling that lever on their seeded fears, via subterfuge, backdoors, surveillance, and maybe a _little math, is too valuable for it not to be pulled.
In the High Beyond and the Lower Transcend, Horatio, there are more quantum algorithms than dreamt of in your philosophies.
But how do you do the key exchange?
1 reply →
> a near term risk we are planning for
I'd argue it's closer to a cheap insurance, just in case.
Take the encryption of a TLS connection itself, for example: you want to protect against a possible "store now, decrypt later" attack on your connection, 60 years from now, by an attacker with an NSA-level budget. Even if you judge the probability of it happening as "exceedingly unlikely", migrating to a hybrid scheme is a no-loss scenario, so it would be silly not to. In a way it's almost a Pascal's Wager.
And then there's of course the NSA itself, who are heavily pushing for post-quantum-only schemes and trying to suppress the hybrid schemes as they almost certainly have weaknesses for some of those new PQ schemes already lying around.
> as they almost certainly have weaknesses for some of those new PQ schemes already lying around
why believe this about PQ schemes vs about pre-existing schemes? Or any other schemes?
It's also worth mentioning that it appears that other countries (in particular China) will adopt fundamentally similar schemes. The NSA loves vulnerabilities, but generally only vulnerabilities of a certain type. These are generally referred to as "NOBUS"
https://en.wikipedia.org/wiki/NOBUS
It includes things like backdoors (say DUAL_EC_DRBG), as well as historically things like reducing the key size of DES, where the US thought they'd be able to brute force it (but other countries would lack the compute). Historically the NSA has actually assisted in removing non-NOBUS vulnerabilities (at least they did this with the SBOX design of DES, which was vulnerable to differential/linear cryptanalysis --- I forget which).
The NSA hasn't publicly assisted/disclosed any vulnerabilities with currently suggested schemes, though a close US ally (Isreal, through an IDF group known by Matzov) has. If America was hoarding vulnerabilities, one might imagine America would have pressured Isreal to keep this secret.
A final point is that it's not clear where the NSA would source the vulnerabilities. By a peculiar chain of coincidences, nearly all of the most successful lattice cryptanalysts are European. None have "gone dark" in a way that would be concerning (say how Don Coppersmith did, when he moved to a NSA affiliate in the mid 2000s). This isn't to say that it would be impossible for the NSA to have better-than-public vulnerabilities, but more to say that they can't just take some of the most successful people who have publicly attacked the problem, and throw more money at them. Their "talent-pipeline" for this particular problem is not as available (and many cryptographers soured on working with them post-Snowden anyway).
1 reply →
I don't know about signatures, but wouldn't a hybrid encryption scheme just involve nesting? Why would that have weaknesses from the hybridization?
1 reply →
This is the second time in my life I’ve heard of this book. It was a wickedly weird book. I think I was 1/3rd through it before I figured out the plurality of the characters.
If we take near term to mean “while any of the participants in this thread are still alive”, I think we’re going to be safe for a while.
https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf
it's worth mentioning opinions have started to shift away from this. Quantum computing has made quite concrete progress in the last ~2 years. No guarantee this continues, but among people I know it has changed their perspectives from (roughly) similar things as that essay, to thinking we really must transition now.
2 replies →
That was very unconvincing.
Like if you want to go from history - yes the make a giant artillery piece thing didn't work.
You know what did work? A surprising application of quantum physics known as nuclear bombs.
I'm not neccesarily saying quantum computers will work out the same way, but if you follow the logic of the presentation, nuclear bombs fit it so much better than the example they use. It was a step-change. People went from saying it was theoretically interesting without practical application to actually having a bomb very quickly. Basically replace everything in that presentation using nukes as the running example and suddenly the argument sounds really stupid.
> 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.
Almost. Quantum is neither a remote risk nor a near-term possibility. Woof, woof, woof! https://eprint.iacr.org/2025/1237
I've always thought creating an ssh-otp should be easy to implement.
(meaning xor the packets themselves with a huge bundle of random data duplicated at each side, and never re-used)
But I think it would probably still qualify as a munition and have export restrictions.
note that OTP is only "perfectly secure" for a rather limited notion of security, namely IND-CPA. This is (roughly) an "honest but curious" adversary who looks at data on the wire (or wherever), but never tampers with it.
This is not a particularly realistic attack model. People typically instead want security against an "active" adversary who does whatever they can (say IND-CCA2 security). You can achieve this information-theoretically, given enough pre-shared randomness, by (roughly) taking some standard Authenticated Encryption with Associated Data (AEAD) construction, and swapping out whatever primitives that are used with information-theoretically secure components. A OTP for the block cipher and a Wegmen-Carter MAC for the MAC should work.
Note that this gives you a scheme with roughly the same practical security as standard ones (unless you think someone can break AES), but it still can be subject to non-trivial attacks that AES cannot. In particular
1. randomness used on both sides MUST never be repeated, and MUST stay in sync throughout, so
2. both sides MUSt stay in sync as to where 1. they are in terms of the randomness they're using, and where 2. the other half of the communication is. Realistically these should be two completely different randomness streams to guard against race conditions where otherwise each side may accidentally reuse a block of randomness
3. having to stay in sync adds several difficulties. In particular, network issues become much more annoying to deal with. This is true for e.g. environmental network disruptions, but also (plausibly) an adversary can disrupt the network temporarily. If this causes you to lose synchronization, then best case this temporary network disruption becomes a permanent network disruption. Worst case it manages to get randomness re-used on one side, which then breaks everything.
The above is likely not an exhaustive list of the problems you have to deal with. But still, you can see how it quickly becomes unclear if things are easy to implement.
One time pads are absurdly easy to implement. They're just impossible to use. What would be the benefit of ssh-otp?
Most of the ways of making the “duplicated at each end” thing practical are just figuring out where to hide the stream cipher. Like, if you just use /dev/*random to generate the random bitstream, what you have is a convoluted output-feedback-mode cipher with a key of whatever was fed into the os's prng, not a one-time-pad.
In terms of actually doing it, it's still very remote, but not as remote as it would have to be for us to completely ignore it. And the NSA has massive data centers full of hard drives storing our encrypted internet traffic.
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
> The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise.
Thus creating a two-time pad, which is completely insecure…
No, the idea is that the actual key is the XOR of 3 completely independent keys. I think you were thinking of XORing a key with itself 3 times, which would just return the original key.
In the book, there is a cargo ship carrying 1/3 of a OTP. Other two other ships from two other companies are carrying the other thirds. This actually is a fairly decent method of transporting a OTP (I'm assuming there's some kind of physical security preventing tampering).
The book even talks later on about how only using the pad isn't enough, since it provides no proof of authorship or tampering. Vinge did a pretty good job w/compsci in the book.
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.
Is there any value in first encrypting with a battle tested algorithm, and then encrypt again with the new algorithm?
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.
1 reply →
[flagged]
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.
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".
Okay that choice of words was a bit harsh. My struggles are partly also due to logs barely complying, that I can't even monitor as quickly as they grow from one IP (mainly looking at you, trustasia, though at least there now is a static log).
Thank you for the explanations. I think I should read the draft RFC.
The last part of your comment caught my attention, seems great if that is being worked on. Can I find more information on it somewhere?
1 reply →
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).
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.
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?
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.
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-t...
[1] https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA...
[2] https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf
4 replies →
There's an IETF RFC draft for mldsa-44 keys for OpenSSH. 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.
OpenSSH's Damien Miller has https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-e... defining ssh-mldsa44-ed25519@openssh.com which seems more likely given the authorship.
1 reply →
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://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.
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.
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.
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.
> 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.
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.
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?
On Linux and similar systems, I'm hoping github.com/rustls/upki will handle landmark distribution, and that non-browser clients can use that. Of course Rustls will support their own project, but I'm hopeful other TLS stacks do too. Ubuntu announcing they're deploying it should help with that.
On other OSes (like Mac OS and Windows), there's also OS-level services which could support this.
It would be a shame if we end up with a bunch of copies of this data, so I think a shared OS service is the only reasonable approach.
The hardest part is going to be smaller embedded systems.
I too was wondering how they feel about the potential downsides which is not really mentioned.
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.
[flagged]
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?
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)
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.
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 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.
[flagged]
no quantum threat. keep ed25519 and rsa, they are fine.
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/
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.
Much love, from the NSA!
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!
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.
> 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."
Yes, totally agreed, but the problem is that most people tend to simplify this as "let's just bother with PQ encryption, forget about signatures". I know experts can handle the nuance, but execs and most industry folks can't. Or, at least, this is the trend that I have personally observed countless times, maybe I was just unlucky with my data points, but I have seen this in "technical" settings as well (case in point: GnuPG prioritized inclusion of PQ hybrid encryption, to the point of rushing the standard against OpenPGP, the well-known "GnuPG schism", but I'm not aware of concrete plans for PQ signature adoptions there).
5 replies →
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.
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).
> and very likely backdoored post-quantum algorithms
Citation needed
Here's mine: https://keymaterial.net/2025/11/27/ml-kem-mythbusting/
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.
5 replies →
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?
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)
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.
21 replies →
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.
this is broadly true. I've heard some criticisms of industrial QC research along these lines, namely that it runs into the issue that its entire TAM ends up being some combination of
1. defense contracting, which can definitely be lucrative, but (hopefully) will dry up quickly after the PQ transition (and especially will if we successfully transition before QCs are advanced enough, which is the goal), and
2. theft, with things like e.g. stealing bitcoins or whatever.
The second is plausibly a large market. It may be difficult to put it on a quarterly report though. So the economic basis industrial QC research may not end up panning out.
it's not just factoring, but general discrete log over abelian groups
1 reply →
> 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.
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.
Has there been "no progress" on classical prime factorization? What about the AKS primality test, a polynomial-time algorithm to test the primality of a number, published in 2002? (This is not my field of expertise; I'm genuinely curious if there's a good reason to discount this as progress towards efficient prime factorization)
2 replies →
Would post-quantum encryption also be harder for regular computers to crack?
9 replies →
I would find BQP = NP ≠ P more surprising than P = NP. But maybe it’s just me :)
> except for pre-shared one time pads when used correctly
The relevant property here is known as "information-theoretic security", and I'm not sure if one-time pads are the only way to achieve it, e.g. Shamir's secret sharing also has this property (although the use case is slightly different): https://en.wikipedia.org/wiki/Information-theoretic_security
4 replies →
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.
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)
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.
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-unveilin... )
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!
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.
1 reply →
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-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.
1 reply →
These are/will be the fundamentals of quantum logic.
https://en.wikipedia.org/wiki/Quantum_logic_gate
Bruce Schneier's books explain that there is far more to security than better encryption. Most are implemented incorrectly or used incorrectly.
I also liked the memes. Too bad they died out after he failed with Skein.