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.
The communication is clearly inflected by Usenet conventions, but I think that's as forgiveable as the choice to have Banks' Culture starships named using our cultural references like "Just read the Instructions" or "Don't Try This At Home". I don't think we're told it actually is Usenet -- it's just that necessarily light speed comms is very slow compared to the pace of life at this scale so it will feel much like Usenet. So I actually thought this made lots of sense.
It's true that we have no apriori justification for the existence of symmetric cryptography and so in principle somebody might have a constructive proof that you can't do this at all and we're boned. There was no evidence for this when the book was written and there's no evidence for it now, but it's nowhere close to as crazy as the Zones of Thought physics so, sure.
[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.
"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for --"
Doesn’t mention anything about quantum there though. Symmetric keys are secure enough against a cryptographically relevant quantum computer, but OTP provides information theoretic security. As GGP mentioned AES should be fine as far as we know for the foreseeable future regardless, but for all we know some brilliant cryptographer will in fact find a flaw. With OTP one doesn’t have to worry about even the slightest chance that could happen. This excerpt also may be alluding to threshold cryptography (Shamir’s secret sharing) which got.. shared.. here recently as well, and also happens to be information theoretically secure.
Sure, but my overall point was meant to refute this:
> But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language […snip…] but they don't understand what's actually going on.
And to support the commenter who expressed surprise about that given Vernor Vinge is a mathematician. Clearly he does know what’s going on. And I think the fact you just posted supports this even more.
Anyways I have no horse in this race, haven’t read the book, just another internet pedant who saw something on HN that could be corrected.
For some context, I am guessing that people lower than the Transcend are uncertain about whether P=NP in the Transcend, which would make OTPs relevant.
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.
The "Zones of Thought" is a fun premise for a story but I'm not sure it actually holds up. It is at least an excuse (unlike in say Iain M Banks which just has Star-Trek style "la la la I can't hear you" FTL travel that's basically magic) but I think the abandoned Eschaton series by Stross had a better excuse and even then Stross accidentally blew it up.
Maybe since our universe doesn't have FTL any author trying to make this work will almost inevitably screw it up? Like how the only novel I've read with the "Protagonist is much, much smarter than everybody else" that works does it by cheating - it's "Tatja Grimm's World" and [spoiler] Tatja isn't actually smarter than us everybody else on her world is stupid by our standards for reasons the plot justifies eventually.
Greg Egan, like some of the newer Stross novels, mostly says no FTL, you can go a long way but it takes a long time, for everybody else if not for you - suck it up. Which isn't a bad excuse, but also isn't FTL at all.
sure, the premise doesn't hold up as rigorous "hard" sf, like anything else involving ftl (though I do like the idea in the eschaton series that fine, you have ftl, but that doesn't make spacetime magically non-einsteinean). what I was getting at was that within that setting you cannot apply laws from our universe as to what forms of cryptography are physically infeasible to crack.
btw one of my favourite "the protagonist is much smarter than everyone else" novels is kress's badly underrated "an alien light", where sort of like tatja grimm she's a genius in a primitive society, but that comes to light when aliens try to teach the natives some basic science and she figures out a lot more than they bargained for.
Meh. Not everything is hard scifi. Just because the author posits a universe different than our own does not mean they screwed up. Its holds up the same way all fiction holds up. Its no different than how lord of the rings has elves and stuff despite elves not being real.
I am confident that I do not live in a Newtonian world. Not as confident as the characters in Egan's "Incandescence" who live somewhere that those primary school spring balance experiments prove Einstein's physics not Newton's - but very sure considering.
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 agree.. Consider Math symbols and physical constants themselves are signs in a humans (or machines) interpretive system. They aren’t the actual thing, and treating them as precise blinds us to alternative interpretations. Conventional wisdom about Grover’s algorithm might be blinding cryptographers. I highly recommend semiotics as a lens peaking through this veil.
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.
Concern about that makes lots more sense. If your trusted couriers are moving some bits as part of a ratchet mechanism or something I'm onboard. But the volumes involved then are tiny, whereas the story beat is about a large volume of data.
It's the difference between stealing Bearer Bonds which you can notionally insist are arbitrarily valuable despite the modest amount in Die Hard†, and stealing literal Gold Bars in Die Hard with a Vengeance which is silly because we know how valuable each bar is and they're much too heavy for the heist to actually work as depicted.
† Die Hard is set after bearer bonds don't make sense for non-crooks and thus didn't exist for crooks to steal because their tax treatment changed, however the novel Die Hard is based on was set before these tax changes so it did make sense when it was written.
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).
First, it doesn't, because we don't use public-key encryption. Instead, we use key-encapsulation mechanisms, which you have to hybridize in another way.
Second, hybridization can add weaknesses in several ways
1. Hybridization may preserve some, but not all, security properties of the constituent parts. This is the case for hybrid signatures. In particular, ML-DSA signatures have a better than SUF-CMA type of security typically called "BUFF" security. Known hybridization techniques lose this security.
2. Hybridization is also more code (and more complex code) to write. Historically, the vast majority of cryptographic issues come from implementation issues, not fundamental weaknesses in the underlying hard problems. So suggesting to obtain security by doing more complex things may not always achieve the desired goal.
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.
It’s also because harvest now decrypt later is the main concern.
This means even if you think viable quantum computers are 20 years away, in contexts where HNDL is an issue that means really you should be thinking about this now.
In contexts where that isn’t an issue you can debate whether we have 5 years, 10 years, 20 years or 50 years but in the case of the SSL key exchange we need to think about it now regardless
these have always been an issue, and were the motivation for starting the NIST standardization in ~2016. My point is more that recent developments in quantum computing have caused many cryptographers to go from "we should do this so people are secure if progress happens in the decades from now" to "this may be a near-term issue, and we should prioritize transition for user safety issues". You can read some about this in a cloudflare article from 2 months ago, which mentions some recent developments that have people concerned about possible "Q-day" being in ~2029-2030". This is much earlier than what was the consensus 5 years ago.
Part of this is because of a 3rd reason to transition early, which is the "long tail" of deployments which will switch over (potentially very) slowly. Think embedded/iot devices that are either difficult to patch, or have vendors who are not as security-focused.
Yeah I think once this ball started rolling it was inevitable it would gain momentum from both sides.
More money for quantum research increases the possibility of breakthroughs, while simultaneously more money for PQC research means more practical, reliable post-quantum cryptosystems that can actually be implemented.
End result is fairly quickly you go from "this is a problem for the fairly distant future and ECDHE is fine" to "we should implement PQ key exchange basically right 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.
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.
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.
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.
worth clarifying that you're both right that this is often referred to as a "hybrid", and there is the exceedingly unfortunate naming collision that "Hybrid Encryption" can also mean something separate, namely using a PKE encryption scheme (or KEM) to solely encrypt a secret key, and then using the secret key for bulk encryption. See for example the Hybrid Public Key Encryption (HPKE) RFC
the unambiguous way to describe what you're talking about (not only for encryption) is the notion of a combiner, though it is admittedly mostly used in theoretical circles.
Also, your comparison between ML-KEM and ECC isn't right. ML-KEM is a KEM built from the Module Learning with Errors assumption, a lattice-based assumption. Part of how ML-KEM is built is by building a PKE scheme. This is an internal implementation detail though, and the FIPS standard explicitly states that they are only approved as part of building ML-KEM.
You can additionally build signatures from MLWE. For example, the ML-DSA scheme (which is a FIPS standard as well) does this. The issue is that lattice-based KEMs and signatures are atypically large compared to ECC precursors (this is what the blog post refers to).
> 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.
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?
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.
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.
The open source project I'm working on aims to authenticate artifact downloads (project name is asfaload, in short it is a sigstore alternative).
My understanding is that in a post-quantum world, the private key can be derived from an ed25519 pub key. That means that an attacker can generate new signatures. But I don't think an attacker would be able to generate a malicious artifact that matches an existing signature. It would seem that once we are nearing PQC, Asfaload would need to support PQC signatures, and its uses would need to migrate to new keys, but that existing signatures would still be safe to use for validation. Is that right?
That is how I understand it yes. I can create a new FW and sign it with the vendors key I cracked and it will be trusted to come from the vendor. But generating a malicious FW that has the same signature is still a hash collision problem.
Sigh, that argument again. I may have used the wrong example, sorry.
How about the current temperature in my bedroom? The battery status of my robomower, Or the vat/tax and total sum I paid at a cash register for the Plopp candy bar earlier today? I could share all this with you if you want.
Depending on where you live, all these systems may, quite possibly talk over TLS and other protocols that include encryption. In some cases unfortunately encryption is the only security mechanism used, when instead device identity, authentication and message authentication is needed. And all are examples where the secrecy requirement is zero or zero after a very short time.
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.
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.
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.
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).
I agree. If we're going the rally the industry to do the work, it should be the whole work in one shot. Any given project/infrastructure that implements both encryption and signing should adopt ML-DSA/SLH-DSA at the same time as ML-KEM, or at least in immediate succession.
My concern is that PQC is having a bit of a Y2K moment, and undercapitalizing on that sense of urgency may risk letting PQ signatures drag on for ages like IPv6. "We need $X engineering budget for PQC" is easy to understand, but "we need $X for PQ encryption now and $Y for PQ signing at some undefined future time" is murkier and may require getting into the weeds on cryptographic concepts and speculative CRQC timelines with non-expert stakeholders.
One of the biggest challenges with the signatures currently standardized is the signature + public key sizes. Demanding we hybridize both just maximizes the pain, and there's no real incentive for this.
Use ML-DSA-44. Don't combine it with other crap. It's good enough.
For KEMs, X-Wing (mlkem768x25519) is great, but ML-KEM-768 and ML-KEM-1024 are also fine on their own. Hybrids are the path of least resistance here, so I prefer them, but have no concerns over ML-KEM's security.
I wasn't implying that the two should be hybridized. I think both are great options to have in our toolkit. For example, in Cyph I chose ML-DSA for end user signing keys + certificates and SLH-DSA for code signing.
No worries, thanks for sharing that post anyway! Another post of yours[1] turned out to be a useful resource for me not too long ago, and the artwork is pretty entertaining.
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).
> all the post-quantum algorithms implemented by OpenSSH are "hybrids" that combine a post-quantum algorithm with a classical algorithm. For example mlkem768x25519-sha256 combines ML-KEM, a post-quantum key agreement scheme, with ECDH/x25519, a classical key agreement algorithm that was formerly OpenSSH's preferred default. This ensures that the combined, hybrid algorithm is no worse than the previous best classical algorithm, even if the post-quantum algorithm turns out to be completely broken by future cryptanalysis.
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.
> nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors.
Who do you trust, then?
> i have no knowledge, nor time to eval. (and probably few people do)
If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions?
Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced ML-KEM and ML-DSA?
Or do you just balk at experts and "trust no one" even to your own detriment?
> If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions?
>
> Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced > ML-KEM and ML-DSA?
>
> Or do you just balk at experts and "trust no one" even to your own detriment?
what detriment? there is no quantum treat, it is made up. at least not in the discussed timelines.
besides, experts are cheap and compromisable, especially for the nation state level bodies like nsa and eu.
it's not just those two institutions. South Korea is running their own standardization currently, and fundamentally similar algorithms are expected to win (some more modern insights might be incorporated, due to starting >=5 years after the NIST standardization did, but still).
The Chinese Academy of Science made their own professional recommendation to the Chinese government a few years ago to use fundamentally similar schemes. The Chinese government this year is planning to start on their own standardization. Again, it is expected they will use fundamentally similar schemes.
The German BSD has suggested their own schemes as well, which are fundamentally similar (they suggested unstructured lattices, which is mildly different. They've also made some incompetent suggestions regarding quantum networking though iirc, so it might be a BSD-specific quirk).
Cryptographers are paranoid by default. It's really the only reasonable way to evaluate things competently. Even among the paranoid though, there's been no plausible argument suggested that something bad is happening with the PQ transition. People will point various fingers, for example
1. a backdoor! Except we can typically detect the possible presence of a backdoor, and nobody has suggested anything despite the designs being fundamentally fixed over the last 15 years (again, except the "one obvious" possible backdoor of standardizing a ML-KEM lattice, which was decided against for this reason), or
2. lattice-based problems are classically weak! There is no publicly visible reason to suspect this. One might then conjecture that they're weak in only a way a nation-state can detect/exploit. Then it would be very weird that it appears that both the US and China will both adopt lattice-based schemes.
It takes more to be a competent cryptographer to be blindly paranoid. There has been zero credible reasons presented though, and the cryptographic community has been looking into these problems and constructions for well over a decade now.
That's not what you said. You said that the algorithms were "very likely backdoored", despite the fact that neither NSA nor the EU had any hand in actually designing them.
I'm not here to defend the NSA as it's treaded on liberties and rights countless times so far.
But understand this:
YES they have a vested interest in harvesting all of your private data for surveillance.
That doesn't mean they DON'T have a vested interest in safeguarding their own data and that of other gov't agencies.
They need the co-operation of the academic community and top cryptography experts to accomplish this. They cannot safeguard their own data or other agencies' data without publishing reports on what works and what doesn't.
So either they risk leaking the encryption algorithms that work for them by hiding them and only sharing the backdoored ones with the public, which is a violation of the [Kerchoff Principle](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) and a massive risk.
Or they simply cooperate with experts and publish algorithms that work for both them and everyone else.
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.
No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices.
People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.
Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU.
He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now.
In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world.
This is ignoring all of his other explicitly embarrassing behavior, for example
1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly.
2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust.
3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.
That he backed PQ crypto that turned out to be broken later should be an argument in favor of hybrid (belts-and-suspender) schemes rather than against it. Embarassing behavior amounts to not much more than ad hominems. Hybrid KEMs are a good idea.
I am pointing out a particular cryptographer's abysmal track record in understanding the security of PQ schemes to call into question their current criticisms of PQ schemes. They've always been (in my opinion obviously) fear-mongering in the past. None of this fear-mongering has been right. So I do not put particularly high weight on their current fear-mongering.
This is especially true because they often lie in their fear-mongering. For example, you appear to be a follower of Dan. You seem to think the argument against hybrids is an argument against hybrid KEMs. It's not. That is a lie. Even Dan's recent tirade on the TLS-WG mailing list has been against putting forward an informational RFC on ML-DSA, a (pure lattice) digital signature scheme.
Perhaps you misunderstood this, and Dan accurately described the setting he is fear-mongering over. Perhaps Dan misrepresented things again, as he has been doing for nearly a decade again. I don't particularly care either way. All that matters to me is accurate evaluation of our current options. It is exceedingly frustrating that a high-profile cryptographer seems incapable of doing this, either due to incompetence or malice.
The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places.
The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve.
So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.
If you encrypt your data twice (taken very literally):
c1 = E1(p, k1)
c2 = E2(p, k2)
If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p.
What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken.
This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated.
This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations.
I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
The thing is: Quantum computers don't break AES-GCM, ChaCha20-Poly1305, or any other modern authenticated cipher. Layering encryption or doing cipher cascades is pointless.
The thing a cryptography-relevant quantum computer does is break RSA and elliptic curve cryptography, so that the underlying key (k1 or k2) is recoverable from its corresponding public component.
Hybrid KEMs, such as mlkem768x25519 (a.k.a. X-Wing) is a simple abstraction with security proofs that does both classical (X25519 is elliptic curve) and post-quantum (ML-KEM-768 is lattice-based) cryptography and combines them securely into a single key agreement.
"Encrypt twice" is bad advice. Even if you get the same approximate security, you're giving up a lot of performance.
Encrypt once, but encrypt with a key you can be confident in the secrecy of.
Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? The change of jargon from "encryption" to "KEM" doesn't mean anything to most people talking about this post-quantum risk. To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption.
Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
"Intuition" about how cryptography works is notoriously bad. Many intuitive things about cryptography are false, and many true things about cryptography are non-intuitive. For this reason it is difficult to seriously discuss cryptography when people are vaguely referring to what they intuitively hope to achieve, framed in terms of concrete constructions that are not secure.
This is also completely ignoring that designing secure systems is about MUCH more than selecting the right "hard problem". Concretely
> They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
might mean requiring a much more complicated lock that, in its ideal implementation has the properties you want, but practically is easier to implement incorrectly, yielding a less secure scheme. Considerations of this form almost never appear, despite being very relevant to the end goal of protecting users.
Similarly, this "defense in depth" intuition is currently not particularly controversial for hybrid KEMs. it is currently quite controversial for hybrid signatures though. The intuitive story would work perfectly well for signatures though. So this intuition does not end up being particularly useful for understanding the actual discussion.
I don't disagree, but I think the folks who know this ought to remember the lay person perspective and try to address it more concretely.
Rather than rejecting the framing because they (we) aren't fluent in your jargon, provide a more constructive hint... E.g. "You may be thinking the symmetric cipher key is simply encrypted with the asymmetric cipher and concatenated to the bulk message. But, to mitigate known cryptographic system risks, modern solutions use specialized key encapsulation or key exchange methods (KEM) which are not directly encrypted messages containing key material."
> I think the folks who know this ought to remember the lay person perspective
That's fair. I hold Hacker News to a higher bar of technical proficiency than a general audience. My hope with insisting on correct framing is to nudge other experts in adjacent fields to teach your more general audiences how to think about these topics more correctly so it's more approachable to the general public.
I'm generally sympathetic to your point, it is just difficult for this particular topic. For example, I mentioned how precision in cryptographic language is important, as there was a discussion about combiners for encryption, when really people should use combiners for KEMs, along with hybrid encryption (here, meaning building public-key encryption from a KEM + symmetric key encryption).
The issue is that none of the above is relevant to the article that we are in the comments of. The article is about signatures. Why are we talking about encryption/KEMs in the first place?
One might hope the story for combiners for KEMs (which people may have intuition for due to combiners for encryption, which you could easily show in an undergraduate cryptography course) is broadly similar to the story for combiners for signatures. Unfortunately, that's not true at all. It would be a very reasonable perspective to have that we should use combiners for KEMs but not combiners for signatures. It would be very difficult to communicate this to a layperson without being very precise about the jargon.
This is especially true as this is a topic where a notable cryptographer has spent the last few years libeling several other cryptographers, and spreading a good deal of misinformation to laypeople. He is also extremely litigious, and has either sued or threatened to sue several cryptographers for what I view to be nonsense reasons. For some (at least myself), this makes precise language all the more important in topics he might have his eyes on.
So I both broadly agree with you for most topics, and also this particular topic requires a good deal more precision than most others in cryptography.
> Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs?
No, I'm saying that "hybrid KEM" or "chaining two KEMs" is very distinct from "encrypt twice". Confuse the two at your own peril.
> To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption.
Encryption is reversible. If you have the key, you can decrypt. It's not encryption if you can't decrypt.
KEMs are their own class of algorithms. They combine an asymmetric encryption scheme with an all-or-nothing one-way transform (usually a key derivation function built on hash functions). It's the safest way to hold asymmetric encryption in practice (even not considering PQ; RSA-KEM beats RSA-OAEP in implementation safety).
Calling KEMs "encryption" is misleading to the point of malpractice. I will push back on conflating the two.
> Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection.
Your only defense-in-depth should be in delivering a strong pseudorandom ephemeral key over an untrusted network, and then using the tried-and-true AEAD constructions that we're already using today. Encrypt once. Do whatever you need to do to get the key exchanged securely.
I write a blog that very regularly covers applied cryptography. I deal with newbie confusion all the time. It's very important that we talk about these things correctly on forums like Hacker News comment threads so that the people learning from us won't get more confused.
both encrypting in parallel and encrypting in the second way you mentioned are bad ideas, and are far from being what is seriously being discussed when people talk about hybrid KEMs. Encrypting in parallel is explicitly IND-CPA insecure if one of the ciphers is broken. Your construction is IND-CPA secure, but quite inefficient, and would not fit into modern protocols.
If this was a typical cryptographic topic, this might be fine, and is how I would likely phrase things for an undergraduate cryptography course. Unfortunately, this is a topic that a certain cryptographer with a decently large public following has been spreading conspiracy theories (and slandering other cryptographers about) for a number of years now. So, discussions on this topic often come from a place where the audience is misinformed, and more care is required in grounding the discussing in what is actually being discussed/considered.
# You kind of have to define this since most libraries don't have it
def classic_kem(pk):
[eph_sk, eph_pk] = classic_keygen()
d = classic_shared_secret(eph_sk, pk)
return hash(d + eph_pk + pk), eph_pk
# Two pieces ...
[ss1, ct1] = classic_kem(pk1)
[ss2, ct2] = postquantum_kem(pk2)
# ... combine into one:
# note: for some KEMs, ct1 and/or ct2 can safely be omitted
shared_secret = hash(ss1 + ss2 + ct1 + ct2)
ciphertext = symmetric_encrypt(plaintext, shared_secret, context)
send_to_other_party(
ct1,
ct2,
ciphertext
)
This sounds more complex, but I'm just filling in the details implied by your pseudocode and making it at least 2x as fast.
If you mean "doing two different KEMs and then securely combining them", then just say that. "Hybrid KEM" is short enough and distinct from other verbage.
"Encrypt" means something specific, not just the vague use of cryptography.
Trying to bridge this a bit since I'm closer to a layperson in this area.
Symmetric encryption does not need a quantum computer alternative, nor do we need a post quantum hashing algorithm. We may need larger keys and larger outputs from the existing algorithms, but that really depends on the level of paranoia.
It is the asymmetric keys that need post quantum replacement.
So I'm guessing the change to your proposed pseudocode you would have two derivation algorithms based on two input asymmetric keys - one post quantum and one classical. You would get from these two separate symmetric keys. You would then layer encryption using each of them, encrypting the cipher text output from the first with the second.
You can however just combine the two derived symmetric keys together to create a single symmetric key, and encrypt once. That is what hybrid algorithms propose.
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.
> 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.
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.
Yes, sorry, I didn't mean to imply they could only "factor". But the things they can do that they get the big advantage over classical computing I find underwhelming when considered against the entire scope of computing problems. Again, great for the people who have those problems, but I still am not sure that they are "worth" what are being poured into them in terms of any real economic impact they have. I do wonder if I could trace back all the money in the sector to their original source just how much of it would end up being the intelligence sector who wants their crackz, and how valuable it'll end up being to them in the end if they can't get a decent crack before we all go post-quantum encryption anyhow.
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)
Primality testing was essentially solved in the 70s with Miller-Rabin. AKS made that (randomized) algorithm deterministic, albeit at much higher (polynomial) running-time.
For your overall question, the current record-holders for integer factorization wrote a paper on this a few years ago that is probably a good reference
1. theoretically there's been no progress on factoring in ~30 years
2. practically, there have been both improved hardware + efficient implementations driving the progress. They estimate that current nation-states can (classically) break RSA-1024. The cost would be approximately 500,000 core-years of computation. At current cloud prices this is doable on aws for < $1B.
3. attacks against factoring use a technique ("index calculus") that can also be used to attack finite-field discrete logarithm. There were significant advances on that problem in the 2010s (at least for certain parameters, namely the "small characteristic" setting). An easy way to communicate this is that the RSA factoring record is ~830 bits, while the binary-field discrete logarithm record is > 30,000 bits. These significant advances have not been able to be ported over to factoring, nor have they been ported over to medium/large-characteristic discrete logarithm. It is a (very upsettingly) large open question of whether similar-magnitude improvements are possible more generally for index calculus algorithms.
> Has there been "no progress" on classical prime factorization?
Not recently. The primality tests don't really help all that much. We already had polynomial tests that are really fast since the 70-s.
Think about this idea: the output of the counting function for the number of primes ("Euler's totient function") lies almost on the logarithmic curve, and we can compute logarithms quickly to any precision. So we can easily find the general area of the curve that should contain the current prime. And then we can quickly test if the given number is in fact the prime number within it.
This is probabilistic because the prime distribution is not _strictly_ logarithmic. We can imagine that by computing a logarithm we might end up in the next "bucket" and check for the wrong prime.
The fascinating part is that zeroes of the Riemann zeta function encode these corrections on top of the logarithmic curve. If the Riemann hypothesis is correct, then these corrections are _bounded_ and we simply can not end up in a different "bucket" by accident.
It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.
Some well-known other problems are also HSP instances over non-abelian groups, for example
1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and
2. graph-isomorphism is a HSP instance over the symmetric group.
LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.
This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.
There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.
With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.
In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.
So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey
I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem.
I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc; things were wackier in the early aughts too) just as there is a diversity of implementation strategies for lattice KEMs.
The notion I'm hostile to is the one that poses lattices as moon math.
Yes I know. That was what my initial paragraph was about.
And yes, our formal understanding of LWE is much better than the original NTRU problem. NTRU itself
1. admits non-trivial attacks if the ciphertext modulus is too large, as well as
2. had a signature algorithm (NTRU-sign) that was completely broken.
Lattice-based signatures were actually a relatively thorny thing to develop. The first non-broken lattice-based signature was proposed in 2009 iirc. I think this was after Gentry developed fully homomorphic encryption (though his initial scheme is now broken as well). Even in modern treatments, it's a fair statement to say that constructing a secure lattice-based signature is of similar complexity to constructing a secure fully homomorphic encryption scheme (although there are some relatively-simple ones these days).
You can make stronger statements about our understanding of LWE though. I would say that it is relatively uncontentious to state that LWE and elliptic-curve DLOG are the two problems we understand the best theoretically in public-key cryptography, and it is not particularly close. The only remote contenders would be
1. finite-field DH, though arguably our understanding of this is still not great (are CDH and DDH equivalent? well sort of, but the details become quite messy).
2. RSA. There are still many basic questions about it that are wide-open, namely is it equivalent to factoring? There are other questions that are unknown as well, for example how hard it is to attack. "Everyone knows" that you just use GNFS, with L[1/3, c] complexity. But other index calculus attacks were improved to L[1/4, c] complexity in the 2010s. Can those attacks extend to factoring? Things get even worse when you consider the veritable zoo of attacks on RSA when you get a small detail wrong (Coppersmith-style attacks in the presence of some leaked key bits, improved attacks depending on what particular RSA exponents you've chosen, etc).
I think you could even go farther and say that we understand LWE better than elliptic curve DLOG. This would of course be contentious, but is meant to communicate just how good of a (theoretical) understanding we have of the LWE problem.
Of course, the main point in EC DLOG's favor is that, when correctly parameterized (which is a thorny point itself, but mostly fine these days), there are the generic group lower bounds (2^n time, poly space), and attacks have never beaten them. While for LWE attacks have always been of the form (exp time, exp space) (or 2^{n\log n} time, poly space), but the exponent in the "exp"'s doesn't have as clean of a conjectured lower bound, and has been reduced some over time.
(1) Cards on the table I don't pay attention to PQ signatures.
(2) I'm mostly just saying that LWE schemes and 90s NTRU are pretty closely related, more closely related than RSA and FFDH were (but less closely related than a binary Koblitz curve is to 25519).
They are, my point is that this only became obvious later. The initial NTRU preprint frames it as a scheme based on modular polynomial arithmetic, rather than anything related to lattices. At the end of section 4 they even explicitly describe it as a “ring based cryptosystem” (contrasted with “group based cryptosystems”). As you say, now we would call it a lattice-based cryptosystem (over an algebraically structured lattice).
> 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
I would say that SSS is a generalization of OTP, but OTP in practice is so dramatically and unbelievably simpler than SSS that it's not practically useful to consider it as "just" a special-case of SSS. Which is to say, if you were implementing OTP, you would not just implement SSS and then set the right parameters; you would use an entirely distinct implementation.
you can sort-of view it that way, but it's not particularly useful. There are settings where you can view (steps of) a cryptographic algorithm as applying a one-time pad with a pseudorandom pad (say counter-mode encryption for the most obvious example, though it appears elsewhere as well).
Alternatively, shamir's secret sharing can be extended to threshold settings pretty easily. So you can write a generalized scheme where you only recover things when "enough people" (but perhaps not everyone) tries to reconstruct. This generalized scheme doesn't look particularly like the one-time pad.
So they end up coinciding in the 2-party case over F2 but it seems to be mostly a coincidence.
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.
The communication is clearly inflected by Usenet conventions, but I think that's as forgiveable as the choice to have Banks' Culture starships named using our cultural references like "Just read the Instructions" or "Don't Try This At Home". I don't think we're told it actually is Usenet -- it's just that necessarily light speed comms is very slow compared to the pace of life at this scale so it will feel much like Usenet. So I actually thought this made lots of sense.
It's true that we have no apriori justification for the existence of symmetric cryptography and so in principle somebody might have a constructive proof that you can't do this at all and we're boned. There was no evidence for this when the book was written and there's no evidence for it now, but it's nowhere close to as crazy as the Zones of Thought physics so, sure.
The Usenet comms gave me a lot of laughs. It was so cleverly done. It’s been a very long time since I read it, but that is one of the memories I have.
[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.
From Chapter 8, available online at https://deepness.trmm.net/c08b/
"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for --"
Doesn’t mention anything about quantum there though. Symmetric keys are secure enough against a cryptographically relevant quantum computer, but OTP provides information theoretic security. As GGP mentioned AES should be fine as far as we know for the foreseeable future regardless, but for all we know some brilliant cryptographer will in fact find a flaw. With OTP one doesn’t have to worry about even the slightest chance that could happen. This excerpt also may be alluding to threshold cryptography (Shamir’s secret sharing) which got.. shared.. here recently as well, and also happens to be information theoretically secure.
> Doesn’t mention anything about quantum there though
Because the book was written 2 years before it was discovered quantum computers had applications to cryptanalysis of RSA.
Sure, but my overall point was meant to refute this:
> But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language […snip…] but they don't understand what's actually going on.
And to support the commenter who expressed surprise about that given Vernor Vinge is a mathematician. Clearly he does know what’s going on. And I think the fact you just posted supports this even more.
Anyways I have no horse in this race, haven’t read the book, just another internet pedant who saw something on HN that could be corrected.
For some context, I am guessing that people lower than the Transcend are uncertain about whether P=NP in the Transcend, which would make OTPs relevant.
It's a universe where hypercomputation exists if you're willing to risk visiting the gods.
Ah, hence the need for ITS.
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.
The "Zones of Thought" is a fun premise for a story but I'm not sure it actually holds up. It is at least an excuse (unlike in say Iain M Banks which just has Star-Trek style "la la la I can't hear you" FTL travel that's basically magic) but I think the abandoned Eschaton series by Stross had a better excuse and even then Stross accidentally blew it up.
Maybe since our universe doesn't have FTL any author trying to make this work will almost inevitably screw it up? Like how the only novel I've read with the "Protagonist is much, much smarter than everybody else" that works does it by cheating - it's "Tatja Grimm's World" and [spoiler] Tatja isn't actually smarter than us everybody else on her world is stupid by our standards for reasons the plot justifies eventually.
Greg Egan, like some of the newer Stross novels, mostly says no FTL, you can go a long way but it takes a long time, for everybody else if not for you - suck it up. Which isn't a bad excuse, but also isn't FTL at all.
sure, the premise doesn't hold up as rigorous "hard" sf, like anything else involving ftl (though I do like the idea in the eschaton series that fine, you have ftl, but that doesn't make spacetime magically non-einsteinean). what I was getting at was that within that setting you cannot apply laws from our universe as to what forms of cryptography are physically infeasible to crack.
btw one of my favourite "the protagonist is much smarter than everyone else" novels is kress's badly underrated "an alien light", where sort of like tatja grimm she's a genius in a primitive society, but that comes to light when aliens try to teach the natives some basic science and she figures out a lot more than they bargained for.
Meh. Not everything is hard scifi. Just because the author posits a universe different than our own does not mean they screwed up. Its holds up the same way all fiction holds up. Its no different than how lord of the rings has elves and stuff despite elves not being real.
Do you assume Lorentz relativity is necessary? In Newtonian world there should be no problem with FTL.
I am confident that I do not live in a Newtonian world. Not as confident as the characters in Egan's "Incandescence" who live somewhere that those primary school spring balance experiments prove Einstein's physics not Newton's - but very sure considering.
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.
I agree.. Consider Math symbols and physical constants themselves are signs in a humans (or machines) interpretive system. They aren’t the actual thing, and treating them as precise blinds us to alternative interpretations. Conventional wisdom about Grover’s algorithm might be blinding cryptographers. I highly recommend semiotics as a lens peaking through this veil.
In the High Beyond and the Lower Transcend, Horatio, there are more quantum algorithms than dreamt of in your philosophies.
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.
But how do you do the key exchange?
Concern about that makes lots more sense. If your trusted couriers are moving some bits as part of a ratchet mechanism or something I'm onboard. But the volumes involved then are tiny, whereas the story beat is about a large volume of data.
It's the difference between stealing Bearer Bonds which you can notionally insist are arbitrarily valuable despite the modest amount in Die Hard†, and stealing literal Gold Bars in Die Hard with a Vengeance which is silly because we know how valuable each bar is and they're much too heavy for the heist to actually work as depicted.
† Die Hard is set after bearer bonds don't make sense for non-crooks and thus didn't exist for crooks to steal because their tax treatment changed, however the novel Die Hard is based on was set before these tax changes so it did make sense when it was written.
> 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).
> If America was hoarding vulnerabilities, one might imagine America would have pressured Isreal to keep this secret.
just say no
I don't know about signatures, but wouldn't a hybrid encryption scheme just involve nesting? Why would that have weaknesses from the hybridization?
First, it doesn't, because we don't use public-key encryption. Instead, we use key-encapsulation mechanisms, which you have to hybridize in another way.
Second, hybridization can add weaknesses in several ways
1. Hybridization may preserve some, but not all, security properties of the constituent parts. This is the case for hybrid signatures. In particular, ML-DSA signatures have a better than SUF-CMA type of security typically called "BUFF" security. Known hybridization techniques lose this security.
2. Hybridization is also more code (and more complex code) to write. Historically, the vast majority of cryptographic issues come from implementation issues, not fundamental weaknesses in the underlying hard problems. So suggesting to obtain security by doing more complex things may not always achieve the desired goal.
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.
It’s also because harvest now decrypt later is the main concern.
This means even if you think viable quantum computers are 20 years away, in contexts where HNDL is an issue that means really you should be thinking about this now.
In contexts where that isn’t an issue you can debate whether we have 5 years, 10 years, 20 years or 50 years but in the case of the SSL key exchange we need to think about it now regardless
these have always been an issue, and were the motivation for starting the NIST standardization in ~2016. My point is more that recent developments in quantum computing have caused many cryptographers to go from "we should do this so people are secure if progress happens in the decades from now" to "this may be a near-term issue, and we should prioritize transition for user safety issues". You can read some about this in a cloudflare article from 2 months ago, which mentions some recent developments that have people concerned about possible "Q-day" being in ~2029-2030". This is much earlier than what was the consensus 5 years ago.
https://blog.cloudflare.com/post-quantum-roadmap/
Part of this is because of a 3rd reason to transition early, which is the "long tail" of deployments which will switch over (potentially very) slowly. Think embedded/iot devices that are either difficult to patch, or have vendors who are not as security-focused.
Yeah I think once this ball started rolling it was inevitable it would gain momentum from both sides.
More money for quantum research increases the possibility of breakthroughs, while simultaneously more money for PQC research means more practical, reliable post-quantum cryptosystems that can actually be implemented.
End result is fairly quickly you go from "this is a problem for the fairly distant future and ECDHE is fine" to "we should implement PQ key exchange basically right now"
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.
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.
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.
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
All your Bitcoin are belong to Us?
all my apes gone
> 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.
worth clarifying that you're both right that this is often referred to as a "hybrid", and there is the exceedingly unfortunate naming collision that "Hybrid Encryption" can also mean something separate, namely using a PKE encryption scheme (or KEM) to solely encrypt a secret key, and then using the secret key for bulk encryption. See for example the Hybrid Public Key Encryption (HPKE) RFC
https://datatracker.ietf.org/doc/rfc9180/
the unambiguous way to describe what you're talking about (not only for encryption) is the notion of a combiner, though it is admittedly mostly used in theoretical circles.
Also, your comparison between ML-KEM and ECC isn't right. ML-KEM is a KEM built from the Module Learning with Errors assumption, a lattice-based assumption. Part of how ML-KEM is built is by building a PKE scheme. This is an internal implementation detail though, and the FIPS standard explicitly states that they are only approved as part of building ML-KEM.
You can additionally build signatures from MLWE. For example, the ML-DSA scheme (which is a FIPS standard as well) does this. The issue is that lattice-based KEMs and signatures are atypically large compared to ECC precursors (this is what the blog post refers to).
[flagged]
> 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]
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?
The best introduction to verifiable indexes I know of offhand is https://www.youtube.com/watch?v=gfrXTgmbS1s and https://github.com/transparency-dev/incubator/tree/main/vind...
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.
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
The open source project I'm working on aims to authenticate artifact downloads (project name is asfaload, in short it is a sigstore alternative). My understanding is that in a post-quantum world, the private key can be derived from an ed25519 pub key. That means that an attacker can generate new signatures. But I don't think an attacker would be able to generate a malicious artifact that matches an existing signature. It would seem that once we are nearing PQC, Asfaload would need to support PQC signatures, and its uses would need to migrate to new keys, but that existing signatures would still be safe to use for validation. Is that right?
That is how I understand it yes. I can create a new FW and sign it with the vendors key I cracked and it will be trusted to come from the vendor. But generating a malicious FW that has the same signature is still a hash collision problem.
I'll believe that you believe that your bank statements only need to be private for a year, when you upload all of yours until a year ago.
Sigh, that argument again. I may have used the wrong example, sorry.
How about the current temperature in my bedroom? The battery status of my robomower, Or the vat/tax and total sum I paid at a cash register for the Plopp candy bar earlier today? I could share all this with you if you want.
Depending on where you live, all these systems may, quite possibly talk over TLS and other protocols that include encryption. In some cases unfortunately encryption is the only security mechanism used, when instead device identity, authentication and message authentication is needed. And all are examples where the secrecy requirement is zero or zero after a very short time.
Better examples?
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.
Sure, but that's a composite scheme, and I dislike those. :P
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.
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.
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
[flagged]
no quantum threat. keep ed25519 and rsa, they are fine.
Much love, from the NSA!
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.
"Industry quantum computing has made precipitous progress in the last few years":
the quantum industry in reality: "Using Shor’s algorithm, the largest integer factored into primes is 15" :)))
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).
I agree. If we're going the rally the industry to do the work, it should be the whole work in one shot. Any given project/infrastructure that implements both encryption and signing should adopt ML-DSA/SLH-DSA at the same time as ML-KEM, or at least in immediate succession.
My concern is that PQC is having a bit of a Y2K moment, and undercapitalizing on that sense of urgency may risk letting PQ signatures drag on for ages like IPv6. "We need $X engineering budget for PQC" is easy to understand, but "we need $X for PQ encryption now and $Y for PQ signing at some undefined future time" is murkier and may require getting into the weeds on cryptographic concepts and speculative CRQC timelines with non-expert stakeholders.
> signing should adopt ML-DSA/SLH-DSA at the same time as ML-KEM
I know you mean well, but this proposal maximizes the downsides of PQ signatures.
Both ML-DSA and SLH-DSA have enormous keys. SLH-DSA is also very slow, while ML-DSA is relatively fast: https://blog.cloudflare.com/another-look-at-pq-signatures/
One of the biggest challenges with the signatures currently standardized is the signature + public key sizes. Demanding we hybridize both just maximizes the pain, and there's no real incentive for this.
As I wrote in https://soatok.blog/2026/04/13/hybrid-constructions-the-post..., the justification for composite/hybrid signatures just isn't there.
Use ML-DSA-44. Don't combine it with other crap. It's good enough.
For KEMs, X-Wing (mlkem768x25519) is great, but ML-KEM-768 and ML-KEM-1024 are also fine on their own. Hybrids are the path of least resistance here, so I prefer them, but have no concerns over ML-KEM's security.
I wasn't implying that the two should be hybridized. I think both are great options to have in our toolkit. For example, in Cyph I chose ML-DSA for end user signing keys + certificates and SLH-DSA for code signing.
Sorry, I did entirely misread your words.
No worries, thanks for sharing that post anyway! Another post of yours[1] turned out to be a useful resource for me not too long ago, and the artwork is pretty entertaining.
1: https://soatok.blog/2021/08/20/lobste-rs-password-reset-vuln...
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).
This concern doesn't apply if a hybrid approach is used. From https://www.openssh.org/pq.html :
> all the post-quantum algorithms implemented by OpenSSH are "hybrids" that combine a post-quantum algorithm with a classical algorithm. For example mlkem768x25519-sha256 combines ML-KEM, a post-quantum key agreement scheme, with ECDH/x25519, a classical key agreement algorithm that was formerly OpenSSH's preferred default. This ensures that the combined, hybrid algorithm is no worse than the previous best classical algorithm, even if the post-quantum algorithm turns out to be completely broken by future cryptanalysis.
> 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.
> nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors.
Who do you trust, then?
> i have no knowledge, nor time to eval. (and probably few people do)
If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions?
Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced ML-KEM and ML-DSA?
Or do you just balk at experts and "trust no one" even to your own detriment?
> Who do you trust, then? the existing algos
> If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions? > > Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced > ML-KEM and ML-DSA? > > Or do you just balk at experts and "trust no one" even to your own detriment?
what detriment? there is no quantum treat, it is made up. at least not in the discussed timelines.
besides, experts are cheap and compromisable, especially for the nation state level bodies like nsa and eu.
it's not just those two institutions. South Korea is running their own standardization currently, and fundamentally similar algorithms are expected to win (some more modern insights might be incorporated, due to starting >=5 years after the NIST standardization did, but still).
The Chinese Academy of Science made their own professional recommendation to the Chinese government a few years ago to use fundamentally similar schemes. The Chinese government this year is planning to start on their own standardization. Again, it is expected they will use fundamentally similar schemes.
The German BSD has suggested their own schemes as well, which are fundamentally similar (they suggested unstructured lattices, which is mildly different. They've also made some incompetent suggestions regarding quantum networking though iirc, so it might be a BSD-specific quirk).
Cryptographers are paranoid by default. It's really the only reasonable way to evaluate things competently. Even among the paranoid though, there's been no plausible argument suggested that something bad is happening with the PQ transition. People will point various fingers, for example
1. a backdoor! Except we can typically detect the possible presence of a backdoor, and nobody has suggested anything despite the designs being fundamentally fixed over the last 15 years (again, except the "one obvious" possible backdoor of standardizing a ML-KEM lattice, which was decided against for this reason), or
2. lattice-based problems are classically weak! There is no publicly visible reason to suspect this. One might then conjecture that they're weak in only a way a nation-state can detect/exploit. Then it would be very weird that it appears that both the US and China will both adopt lattice-based schemes.
It takes more to be a competent cryptographer to be blindly paranoid. There has been zero credible reasons presented though, and the cryptographic community has been looking into these problems and constructions for well over a decade now.
That's not what you said. You said that the algorithms were "very likely backdoored", despite the fact that neither NSA nor the EU had any hand in actually designing them.
I'm not here to defend the NSA as it's treaded on liberties and rights countless times so far.
But understand this:
YES they have a vested interest in harvesting all of your private data for surveillance.
That doesn't mean they DON'T have a vested interest in safeguarding their own data and that of other gov't agencies.
They need the co-operation of the academic community and top cryptography experts to accomplish this. They cannot safeguard their own data or other agencies' data without publishing reports on what works and what doesn't.
So either they risk leaking the encryption algorithms that work for them by hiding them and only sharing the backdoored ones with the public, which is a violation of the [Kerchoff Principle](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) and a massive risk.
Or they simply cooperate with experts and publish algorithms that work for both them and everyone else.
Which sounds simpler?
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.
No. "Post-quantum" is not a kind of cryptography; it's an attribute of many different kinds of cryptography. SIKE and modular lattices are completely unrelated. SIKE is moon math that genuinely was introduced to mainstream cryptographers as a post-quantum construction. Lattices have been carefully studied for decades; in the 1990s, it was a live discussion whether the successor to RSA was going to be elliptic curves or lattices.
People bring up SIKE/SIDH in these discussions because Daniel Bernstein has used it as innuendo in his arguments against the MLKEM standard (always left out of those discussions: Bernstein himself backed a lattice KEM in the same competition). It's aggravating because its very clear that he's succeeded in getting people to believe that SIDH somehow reflects on lattice cryptography. That's not a problem because it's persuasive (no cryptographer would take that argument seriously) but rather because he's succeeded in making people say dumb things.
Worth mentioning the lattice KEM he backed (NTRU prime) is part of a class of lattice-based assumptions that admitted devastating attacks (though not in the parameter regime relevant to public-key cryptography applications). By this I mean the dense sub lattice attacks on NTRU.
He has also repeatedly pointed to (seemingly random) pieces of lattice cryptography and claimed that it is the cause for concern/plausibly where attacks may come from. Here, I mean the galois group structure, the whole “quotient vs product” stuff he was doing trying to pretend LWE is a variant of ntru (and less secure, which was explicitly wrong), and his “spherical models” claims. These last ones included an explicit claim of subexponential attacks to be presented later, which have been delayed for a number of years now.
In short, his fearmongering over lattices, while persistent, has never been right. He’s pointed fingers at things we have not found issues with, and either backed sides in debates which ended up being less secure (NTRU vs LWE), or completely missed other things (say the sPIP attacks a decade ago). He may plausibly be the least credible person to make predictions about lattices in the world.
This is ignoring all of his other explicitly embarrassing behavior, for example
1. Insinuating all lattice cryptographers are on the payroll of the NSA. The winning schemes were European teams predominantly.
2. Adding a license to all emails he sends in the IETF wg that is incompatible with the wg. This ends up with him getting censure, which he then argues is unjust.
3. Recently, finding a bug in a 2017 piece of software, and then fabricating 3 other bugs. He then wrote a 60 page paper on it, using it as justification to argue against lattices. All of the bugs would be caught by standard high quality testing procedures, eg mutation testing, which he appears unfamiliar with. I believe the “actual” bug (from the v1 reference impl a decade ago) is caught by current test vectors as well.
That he backed PQ crypto that turned out to be broken later should be an argument in favor of hybrid (belts-and-suspender) schemes rather than against it. Embarassing behavior amounts to not much more than ad hominems. Hybrid KEMs are a good idea.
I am pointing out a particular cryptographer's abysmal track record in understanding the security of PQ schemes to call into question their current criticisms of PQ schemes. They've always been (in my opinion obviously) fear-mongering in the past. None of this fear-mongering has been right. So I do not put particularly high weight on their current fear-mongering.
This is especially true because they often lie in their fear-mongering. For example, you appear to be a follower of Dan. You seem to think the argument against hybrids is an argument against hybrid KEMs. It's not. That is a lie. Even Dan's recent tirade on the TLS-WG mailing list has been against putting forward an informational RFC on ML-DSA, a (pure lattice) digital signature scheme.
Perhaps you misunderstood this, and Dan accurately described the setting he is fear-mongering over. Perhaps Dan misrepresented things again, as he has been doing for nearly a decade again. I don't particularly care either way. All that matters to me is accurate evaluation of our current options. It is exceedingly frustrating that a high-profile cryptographer seems incapable of doing this, either due to incompetence or malice.
The controversy lately isn’t for encryption. We have a fine hybrid KEM, and it’s being standardized/deployed most places.
The issue instead is for signatures. We don’t have a fine hybrid signature. Concretely, our current hybrid signatures achieve security in a weaker model (they do not achieve BUFF security) than what our PQ signatures achieve.
So the question is if we want explicitly weaker security to provide assurance against possible security issues in the PQ hardness assumption. Or we could delay standardization longer while people search for better ways of making hybrid signatures. Both seem stupid, especially as obtaining cryptographically relevant quantum computers recently seems less like “if” than “when”. Note that when cryptographically relevant quantum computers appear, we will NEED to have a PQ secure component. The main “pro hybrid” cryptographer (Bernstein) has himself predicted classical (public key) cryptography will likely be broken by 2032. Things must transition now.
> You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.
No. Don't do that.
If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway.
You want a Hybrid KEM, not encrypting twice. The nuance matters.
https://durumcrustulum.com/2024/02/24/how-to-hold-kems/
> If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway.
Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?
If you encrypt your data twice (taken very literally):
If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p.What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption) is preserved if any of the underlying KEMs is unbroken.
This in practice looks like a KDF based on a hash function where the component shared secrets (and, depending on the underlying KEM's binding properties, underlying ciphertexts too) are concatenated.This is very different than merely "encrypt your data twice". You only encrypt your data once. The KEY YOU ENCRYPT WITH is, instead, the result of multiple asymmetric operations.
I cannot stress enough how different these proposition are. It's like suggesting someone swim downstream in electric current. The words might make logical sense to a non-expert, but it's utterly unsafe taken literally.
It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).
The thing is: Quantum computers don't break AES-GCM, ChaCha20-Poly1305, or any other modern authenticated cipher. Layering encryption or doing cipher cascades is pointless.
The thing a cryptography-relevant quantum computer does is break RSA and elliptic curve cryptography, so that the underlying key (k1 or k2) is recoverable from its corresponding public component.
Hybrid KEMs, such as mlkem768x25519 (a.k.a. X-Wing) is a simple abstraction with security proofs that does both classical (X25519 is elliptic curve) and post-quantum (ML-KEM-768 is lattice-based) cryptography and combines them securely into a single key agreement.
"Encrypt twice" is bad advice. Even if you get the same approximate security, you're giving up a lot of performance.
Encrypt once, but encrypt with a key you can be confident in the secrecy of.
Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? The change of jargon from "encryption" to "KEM" doesn't mean anything to most people talking about this post-quantum risk. To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption.
Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
"Intuition" about how cryptography works is notoriously bad. Many intuitive things about cryptography are false, and many true things about cryptography are non-intuitive. For this reason it is difficult to seriously discuss cryptography when people are vaguely referring to what they intuitively hope to achieve, framed in terms of concrete constructions that are not secure.
This is also completely ignoring that designing secure systems is about MUCH more than selecting the right "hard problem". Concretely
> They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.
might mean requiring a much more complicated lock that, in its ideal implementation has the properties you want, but practically is easier to implement incorrectly, yielding a less secure scheme. Considerations of this form almost never appear, despite being very relevant to the end goal of protecting users.
Similarly, this "defense in depth" intuition is currently not particularly controversial for hybrid KEMs. it is currently quite controversial for hybrid signatures though. The intuitive story would work perfectly well for signatures though. So this intuition does not end up being particularly useful for understanding the actual discussion.
I don't disagree, but I think the folks who know this ought to remember the lay person perspective and try to address it more concretely.
Rather than rejecting the framing because they (we) aren't fluent in your jargon, provide a more constructive hint... E.g. "You may be thinking the symmetric cipher key is simply encrypted with the asymmetric cipher and concatenated to the bulk message. But, to mitigate known cryptographic system risks, modern solutions use specialized key encapsulation or key exchange methods (KEM) which are not directly encrypted messages containing key material."
> I think the folks who know this ought to remember the lay person perspective
That's fair. I hold Hacker News to a higher bar of technical proficiency than a general audience. My hope with insisting on correct framing is to nudge other experts in adjacent fields to teach your more general audiences how to think about these topics more correctly so it's more approachable to the general public.
I'm generally sympathetic to your point, it is just difficult for this particular topic. For example, I mentioned how precision in cryptographic language is important, as there was a discussion about combiners for encryption, when really people should use combiners for KEMs, along with hybrid encryption (here, meaning building public-key encryption from a KEM + symmetric key encryption).
The issue is that none of the above is relevant to the article that we are in the comments of. The article is about signatures. Why are we talking about encryption/KEMs in the first place?
One might hope the story for combiners for KEMs (which people may have intuition for due to combiners for encryption, which you could easily show in an undergraduate cryptography course) is broadly similar to the story for combiners for signatures. Unfortunately, that's not true at all. It would be a very reasonable perspective to have that we should use combiners for KEMs but not combiners for signatures. It would be very difficult to communicate this to a layperson without being very precise about the jargon.
This is especially true as this is a topic where a notable cryptographer has spent the last few years libeling several other cryptographers, and spreading a good deal of misinformation to laypeople. He is also extremely litigious, and has either sued or threatened to sue several cryptographers for what I view to be nonsense reasons. For some (at least myself), this makes precise language all the more important in topics he might have his eyes on.
So I both broadly agree with you for most topics, and also this particular topic requires a good deal more precision than most others in cryptography.
[flagged]
> Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs?
No, I'm saying that "hybrid KEM" or "chaining two KEMs" is very distinct from "encrypt twice". Confuse the two at your own peril.
> To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption.
Encryption is reversible. If you have the key, you can decrypt. It's not encryption if you can't decrypt.
KEMs are their own class of algorithms. They combine an asymmetric encryption scheme with an all-or-nothing one-way transform (usually a key derivation function built on hash functions). It's the safest way to hold asymmetric encryption in practice (even not considering PQ; RSA-KEM beats RSA-OAEP in implementation safety).
Calling KEMs "encryption" is misleading to the point of malpractice. I will push back on conflating the two.
> Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection.
Your only defense-in-depth should be in delivering a strong pseudorandom ephemeral key over an untrusted network, and then using the tried-and-true AEAD constructions that we're already using today. Encrypt once. Do whatever you need to do to get the key exchanged securely.
I write a blog that very regularly covers applied cryptography. I deal with newbie confusion all the time. It's very important that we talk about these things correctly on forums like Hacker News comment threads so that the people learning from us won't get more confused.
Please don't call KEMs "encryption".
both encrypting in parallel and encrypting in the second way you mentioned are bad ideas, and are far from being what is seriously being discussed when people talk about hybrid KEMs. Encrypting in parallel is explicitly IND-CPA insecure if one of the ciphers is broken. Your construction is IND-CPA secure, but quite inefficient, and would not fit into modern protocols.
If this was a typical cryptographic topic, this might be fine, and is how I would likely phrase things for an undergraduate cryptography course. Unfortunately, this is a topic that a certain cryptographer with a decently large public following has been spreading conspiracy theories (and slandering other cryptographers about) for a number of years now. So, discussions on this topic often come from a place where the audience is misinformed, and more care is required in grounding the discussing in what is actually being discussed/considered.
The idea would be:
I think this is different from what you wrote but I can't really tell.FWIW I am not advocating for "encrypt twice" at all, I'm just trying to understand.
A better idea is to do this:
This sounds more complex, but I'm just filling in the details implied by your pseudocode and making it at least 2x as fast.On the opposite side, their code looks like this:
If you mean "doing two different KEMs and then securely combining them", then just say that. "Hybrid KEM" is short enough and distinct from other verbage."Encrypt" means something specific, not just the vague use of cryptography.
Trying to bridge this a bit since I'm closer to a layperson in this area.
Symmetric encryption does not need a quantum computer alternative, nor do we need a post quantum hashing algorithm. We may need larger keys and larger outputs from the existing algorithms, but that really depends on the level of paranoia.
It is the asymmetric keys that need post quantum replacement.
So I'm guessing the change to your proposed pseudocode you would have two derivation algorithms based on two input asymmetric keys - one post quantum and one classical. You would get from these two separate symmetric keys. You would then layer encryption using each of them, encrypting the cipher text output from the first with the second.
You can however just combine the two derived symmetric keys together to create a single symmetric key, and encrypt once. That is what hybrid algorithms propose.
Why would you take the stupidest possible interpretation of that person's comment?
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.
> 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.
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
Yes, sorry, I didn't mean to imply they could only "factor". But the things they can do that they get the big advantage over classical computing I find underwhelming when considered against the entire scope of computing problems. Again, great for the people who have those problems, but I still am not sure that they are "worth" what are being poured into them in terms of any real economic impact they have. I do wonder if I could trace back all the money in the sector to their original source just how much of it would end up being the intelligence sector who wants their crackz, and how valuable it'll end up being to them in the end if they can't get a decent crack before we all go post-quantum encryption anyhow.
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)
Primality testing was essentially solved in the 70s with Miller-Rabin. AKS made that (randomized) algorithm deterministic, albeit at much higher (polynomial) running-time.
For your overall question, the current record-holders for integer factorization wrote a paper on this a few years ago that is probably a good reference
https://hal.science/hal-03691141/file/cryptography.pdf
The (rough) outline of the paper is that
1. theoretically there's been no progress on factoring in ~30 years
2. practically, there have been both improved hardware + efficient implementations driving the progress. They estimate that current nation-states can (classically) break RSA-1024. The cost would be approximately 500,000 core-years of computation. At current cloud prices this is doable on aws for < $1B.
3. attacks against factoring use a technique ("index calculus") that can also be used to attack finite-field discrete logarithm. There were significant advances on that problem in the 2010s (at least for certain parameters, namely the "small characteristic" setting). An easy way to communicate this is that the RSA factoring record is ~830 bits, while the binary-field discrete logarithm record is > 30,000 bits. These significant advances have not been able to be ported over to factoring, nor have they been ported over to medium/large-characteristic discrete logarithm. It is a (very upsettingly) large open question of whether similar-magnitude improvements are possible more generally for index calculus algorithms.
> Has there been "no progress" on classical prime factorization?
Not recently. The primality tests don't really help all that much. We already had polynomial tests that are really fast since the 70-s.
Think about this idea: the output of the counting function for the number of primes ("Euler's totient function") lies almost on the logarithmic curve, and we can compute logarithms quickly to any precision. So we can easily find the general area of the curve that should contain the current prime. And then we can quickly test if the given number is in fact the prime number within it.
This is probabilistic because the prime distribution is not _strictly_ logarithmic. We can imagine that by computing a logarithm we might end up in the next "bucket" and check for the wrong prime.
The fascinating part is that zeroes of the Riemann zeta function encode these corrections on top of the logarithmic curve. If the Riemann hypothesis is correct, then these corrections are _bounded_ and we simply can not end up in a different "bucket" by accident.
Would post-quantum encryption also be harder for regular computers to crack?
It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.
Some well-known other problems are also HSP instances over non-abelian groups, for example
1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and
2. graph-isomorphism is a HSP instance over the symmetric group.
LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.
The international standardization effort that led to ML-KEM and ML-DSA focused both on classical attacks (regular computers) and quantum attacks.
There were 5 levels being considered for each submission.
Level 1 - at least as difficult to attack as AES-128 (block cipher)
Level 2 - at least as difficult to attack as SHA-256 (hash function)
Level 3 - at least as difficult to attack as AES-192 (block cipher)
Level 4 - at least as difficult to attack as SHA-384 (hash function)
Level 5 - at least as difficult to attack as AES-256 (block cipher)
The security of attacking an N-bit block cipher is morally congruent to a birthday collision against a {2N}-bit hash function. With some caveats: https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th...
ML-DSA-44 (smallest parameter set) targets Level 2 for signatures.
ML-KEM-768 targets Level 3 for KEMs.
This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.
There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.
With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.
In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.
So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey
https://cims.nyu.edu/~regev/papers/lwesurvey.pdf
I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem.
I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc; things were wackier in the early aughts too) just as there is a diversity of implementation strategies for lattice KEMs.
The notion I'm hostile to is the one that poses lattices as moon math.
Yes I know. That was what my initial paragraph was about.
And yes, our formal understanding of LWE is much better than the original NTRU problem. NTRU itself
1. admits non-trivial attacks if the ciphertext modulus is too large, as well as
2. had a signature algorithm (NTRU-sign) that was completely broken.
Lattice-based signatures were actually a relatively thorny thing to develop. The first non-broken lattice-based signature was proposed in 2009 iirc. I think this was after Gentry developed fully homomorphic encryption (though his initial scheme is now broken as well). Even in modern treatments, it's a fair statement to say that constructing a secure lattice-based signature is of similar complexity to constructing a secure fully homomorphic encryption scheme (although there are some relatively-simple ones these days).
You can make stronger statements about our understanding of LWE though. I would say that it is relatively uncontentious to state that LWE and elliptic-curve DLOG are the two problems we understand the best theoretically in public-key cryptography, and it is not particularly close. The only remote contenders would be
1. finite-field DH, though arguably our understanding of this is still not great (are CDH and DDH equivalent? well sort of, but the details become quite messy).
2. RSA. There are still many basic questions about it that are wide-open, namely is it equivalent to factoring? There are other questions that are unknown as well, for example how hard it is to attack. "Everyone knows" that you just use GNFS, with L[1/3, c] complexity. But other index calculus attacks were improved to L[1/4, c] complexity in the 2010s. Can those attacks extend to factoring? Things get even worse when you consider the veritable zoo of attacks on RSA when you get a small detail wrong (Coppersmith-style attacks in the presence of some leaked key bits, improved attacks depending on what particular RSA exponents you've chosen, etc).
I think you could even go farther and say that we understand LWE better than elliptic curve DLOG. This would of course be contentious, but is meant to communicate just how good of a (theoretical) understanding we have of the LWE problem.
Of course, the main point in EC DLOG's favor is that, when correctly parameterized (which is a thorny point itself, but mostly fine these days), there are the generic group lower bounds (2^n time, poly space), and attacks have never beaten them. While for LWE attacks have always been of the form (exp time, exp space) (or 2^{n\log n} time, poly space), but the exponent in the "exp"'s doesn't have as clean of a conjectured lower bound, and has been reduced some over time.
Sure, two things:
(1) Cards on the table I don't pay attention to PQ signatures.
(2) I'm mostly just saying that LWE schemes and 90s NTRU are pretty closely related, more closely related than RSA and FFDH were (but less closely related than a binary Koblitz curve is to 25519).
They are, my point is that this only became obvious later. The initial NTRU preprint frames it as a scheme based on modular polynomial arithmetic, rather than anything related to lattices. At the end of section 4 they even explicitly describe it as a “ring based cryptosystem” (contrasted with “group based cryptosystems”). As you say, now we would call it a lattice-based cryptosystem (over an algebraically structured lattice).
https://www.ntru.org/f/hps96.pdf
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
Isn’t one time pad just a simple version of secret sharing?
I would say that SSS is a generalization of OTP, but OTP in practice is so dramatically and unbelievably simpler than SSS that it's not practically useful to consider it as "just" a special-case of SSS. Which is to say, if you were implementing OTP, you would not just implement SSS and then set the right parameters; you would use an entirely distinct implementation.
you can sort-of view it that way, but it's not particularly useful. There are settings where you can view (steps of) a cryptographic algorithm as applying a one-time pad with a pseudorandom pad (say counter-mode encryption for the most obvious example, though it appears elsewhere as well).
Alternatively, shamir's secret sharing can be extended to threshold settings pretty easily. So you can write a generalized scheme where you only recover things when "enough people" (but perhaps not everyone) tries to reconstruct. This generalized scheme doesn't look particularly like the one-time pad.
So they end up coinciding in the 2-party case over F2 but it seems to be mostly a coincidence.
Those are the only two known algorithms that have this property.
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.
Ugh. You're right. Thanks.
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.
Fair. I was quoting from memory from maybe 5 years ago.
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.