Comment by lukan
1 day ago
Better encryption sounds good to me in general, but I don't really understand, how we can make quantum safe encryption, when we don't know yet, what capabilities it will have (or if it is possible at all).
I am obviously not in the field, but as far as I know, no QC is close of working for a practical purpose(aside quantum research), but to make it practical, it needs a groundbraking brakethrough of some sort. But if a brakethrough happens, can we really estimate the consequences?
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.
3 replies →
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/
15 replies →
In addition to the other fine answers, I personally find the additional operations that quantum computers enable to be surprisingly inapplicable to a lot of real problems. It's really kind of unimpressive when you dig down into it. It is not a revolution of computing as we know it, it's a very, very expensive accelerator card for a few niche problems. Neat for people who have those problems. But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does.
I think there is a sense in which we have a historical accident that has make quantum computers sound bigger than they are, in that we ended up with "factoring prime numbers" being the first thing we had to make practical encryption out of, and by what is from a human perspective mostly a coincidence, it so happens that quantum computers may be really good at that. But the problem is that quantum computers happen to be good at factorizing that is the problem, not that quantum computers are somehow "good at breaking encryption". It seams to me that in some sense "post-quantum computing" is actually "all practical encryption schemes except those based on factoring large numbers". Breaking large prime number-based schemes is the exception that QC happens to be good at, not the rule.
this is broadly true. I've heard some criticisms of industrial QC research along these lines, namely that it runs into the issue that its entire TAM ends up being some combination of
1. defense contracting, which can definitely be lucrative, but (hopefully) will dry up quickly after the PQ transition (and especially will if we successfully transition before QCs are advanced enough, which is the goal), and
2. theft, with things like e.g. stealing bitcoins or whatever.
The second is plausibly a large market. It may be difficult to put it on a quarterly report though. So the economic basis industrial QC research may not end up panning out.
it's not just factoring, but general discrete log over abelian groups
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.
> But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does.
I think it's very funny to consider that if you were a time traveler tasked with making sure that humanity had the economic incentive to develop quantum computers, the most efficient way to ensure that in a single stroke would be by suggesting the use of prime factorization as a trapdoor function to Rivest, Shamir, or Adleman.
By this standard, there is no current encryption method (except for pre-shared one time pads when used correctly) that is known to be unbreakable. For example, it is not proven that prime factoring can't be done much more efficiently on a classical computer - for all we know, it's possible that tomorrow someone will come up with a novel algorithm that can break RSA in just a small number of operations. Same is true for elyptic curves - we don't have any mathematical proof that it's impossible for a much better algorithm than the currently known ones is possible.
However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't.
In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP.
So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.
Has there been "no progress" on classical prime factorization? What about the AKS primality test, a polynomial-time algorithm to test the primality of a number, published in 2002? (This is not my field of expertise; I'm genuinely curious if there's a good reason to discount this as progress towards efficient prime factorization)
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.
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.
6 replies →
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?
2 replies →
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.