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.
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.
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.
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.
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.
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.
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)
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.
> 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
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.
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.
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.
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)
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!
> 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).
> 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 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.
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.
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.
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
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.
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.
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.
> 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.
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.
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)
Would post-quantum encryption also be harder for regular computers to crack?
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.
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.
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?
Those are the only two known algorithms that have this property.
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.
it's not just factoring, but general discrete log over abelian groups
> 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.
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.
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... )
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)
These are/will be the fundamentals of quantum logic.
https://en.wikipedia.org/wiki/Quantum_logic_gate
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!
> 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).
> 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.
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.