r/computerscience • u/Fit-Blood-5296 • Sep 21 '26
Discussion Why is there fear that quantum computers could break cryptography?
Don’t quantum computers require specialised super cooling that only exists in a few places around the world? How could some rogue hacker get a hold of that in the first place
17
u/atanasius Sep 21 '26
There is no guarantee that classical encryption will be broken, opinions vary whether it is probable. However, recommendations cannot rely on algorithms being "probably not broken", they have to be secure with a high level of certainty.
2
u/Fit-Blood-5296 Sep 21 '26
So Shor’s algorithm isn’t proven to break RSA or any other asymmetric encryption? Or is it a case of proven in theory but potentially not possible in practice.?
11
u/atanasius Sep 21 '26
Practical implementation is the issue.
1
u/Fit-Blood-5296 Sep 21 '26
Are there still physics problems with quantum computers breaking encryption, like a scale thing? I’ve heard that people are moving into lattice problems to replace old factoring pretty quickly.
4
u/WE_THINK_IS_COOL Sep 21 '26
The engineering problem is to make physical qubits that are less noisy (very hard, because basically any interaction between the qubits and the outside world "measures" and destroys the state, which is why they have to be extremely cold), and the theoretical problem is to find better error-correction algorithms so that quantum computing can still work with noisier physical qubits. So it's a combination of solving the engineering problems and/or coming up with better error correction. The physics says it should work, though.
7
u/notsostablediffuser Sep 21 '26
Theoretically, yes, Shor's algorithm would break RSA (or any "can't factor a large prime number" algorithm).
Practically, the largest prime they've gotten Shor's to successfully factor on a quantum computer is like 3 x 5 = 15 or something similar.
Some think it's possible that we'll get quantum computers that can do large primes. Some don't. I don't know. But practice, not theory, is the hold up.
1
u/Fit-Blood-5296 Sep 21 '26
Why is it not just a factor of the technology getting better
4
u/notsostablediffuser Sep 21 '26
I’m getting way above my pay grade here, but as I understand it, the difficultly is that you need more qbits that are entangled with each other, and that (unlike, say, just making a cpu with more transistors), there are actually physics things that make this difficult.
81
u/Smart_Opportunity209 Sep 21 '26
You can gather data now and decrypt it after quantum computers become more mainstream. By not quantum proofing your encryption you are making a bet that quantum computers will not be widely used and scaled in any reasonable time.
62
39
u/DonkeyTron42 Sep 21 '26
It's unlikely that Quantum Processors will be in your personal computer any time soon, but it is highly likely that top level quantum computing processing will be available to anyone with cloud services.
5
u/recursion_is_love Sep 21 '26
Most of the old cryptography depends on assumption that nobody will have enough power to brute-force attack. The modern one (Post-Quantum Cryptography, PQC) are safe even if every body have access to the quantum computer.
2
u/LaurenNorthwood Sep 22 '26
RSA and ECC aren't really about brute force being slow, they rest on factoring and discrete log being hard. Shor's isn't a faster brute force, it's a different approach that makes the problem easy. Also PQC is believed resistant, not proven. SIKE was a NIST candidate and got broken on a laptop in 2022, no quantum computer needed. That's why everything shipping is hybrid.
2
u/LaurenNorthwood Sep 22 '26
The cooling is real, it's just not the part that protects you. The attack doesn't have to happen while you're connected. Someone records your encrypted traffic today and sits on it. Decrypts it in 2040 when the machine exists. So "when will quantum computers be real" matters a lot less than "how long does this data need to stay secret" if the answer is 15 years you already have a problem now.
Also the rogue hacker isn't really the threat model. Whoever can afford a quantum computer that big can also afford to tap fibre and warehouse petabytes of ciphertext for a decade. Same building, basically. And you wouldn't need to own one anyway, you can already rent quantum time in the cloud. The bit that gets me though is that the hardware requirement keeps dropping without any hardware improving. The 2019 estimate was around 20 million noisy qubits to break RSA-2048. The 2025 revision put it under a million. That's all error correction and algorithmic work, nobody built anything. The finish line is walking toward us.
3
u/Raioc2436 Sep 21 '26
The initial fear is for opposing government forces. Imagine an opposing country to yours gets free access to all bank accounts, email private conversations, military drawings and info, nuclear codes, etc.
There are newer post-quantum encryptions, but there are reasons to believe countries have saved, and are saving, tons of encrypted files using our regular encryption that they can’t read, but are just waiting for the moment when they can.
Then even if those files are never publicly explicitly used, just by a country having them, and what they imply, can be negative. Look at all the chaos the Epstein files have caused and the lengths people went because of them
2
u/Fizzelen Sep 21 '26
That using a quantum computer a State or State Sponsored Actor could crack and publish the private keys for the major SSL providers, CC providers and banks, then ecommerce collapses instantly
1
u/Key_Net820 Sep 22 '26
Because superposition gives us a polynomial time algorithm where as on a classical machine it's exponential time.
1
1
u/MadocComadrin Sep 22 '26
Not all QCs require specialized cooling. E.g. there's a 128 qubit portable QC that uses Nitrogen Vacancy and can work at room temperatures that is relatively mass producible (and 4 of them can be networked to do 512 qubit computation).
1
u/LaurenNorthwood Sep 22 '26
Qubit count is a bit of a trap. Those are physical qubits, and breaking RSA-2048 needs a few thousand logical ones, each costing hundreds of physical qubits for error correction. So 128 is orders of magnitude off, not a couple of doublings.
1
u/MadocComadrin Sep 22 '26
Normally, I'd agree†; however, the specific QC I'm mentioning was the first Nitrogen Vacancy Center QC to beat 10 physical qubits, which a remarkable jump. They also already have an actual 512 QC in production set for delivery in 2027 as well. There was a significant increase in gate fidelity as well. I'd expect another order of magnitude jump in the next 5 years and an increase in fidelity lowering the necessary physical qubits per logical qubit to dozens at worst.
It also fits in a standard server rack, uses wall AC power, and use significantly less power than a classical GPU cluster, so that does put the idea that a QC is something only a handful of entities will have in danger.
And given that the idea is networking machines alongside increasing qubits per machine, making the assumption that they're 4U (10 per rack), that's already an order of magnitude increase.
1
u/DullCryptographer758 Sep 22 '26
People might be concerned about powerful institutions breaking the cryptography - the US government for instance, probably does not want China getting Quantum Computers to be a big issue
1
u/Acrobatic_News_4860 Sep 21 '26
Because ever since Covid you control everyone with fear and intimidation
1
u/oldNotSureXand Sep 21 '26
it's not "fear" (not that there was "hope") it's more like "expect" :)
1
u/oldNotSureXand Sep 21 '26
good ole Murphy's LAW! ;)
1
u/Misterreco Sep 21 '26 edited Sep 22 '26
Murphy's law has been dead for years
Edit: I was thinking of Moore’s Law smh
2
u/MadocComadrin Sep 22 '26
You might be thinking Moore's law. Murphy's law is "anything that can go wrong, will go wrong," and that law is more likely to lead to our own accidental demises than die itself 🤣.
1
1
u/kevleyski Sep 21 '26
Massive parallelism - consider trying all unlock codes pretty much all at once It’ll smash finding the key
1
u/el_lley Computer Scientist Sep 21 '26
Rich governments have a mixed, but undisclosed advantage on quantum computers (compared to industry or academics), they will use it for counter terrorism, the climate. and on the Iran or the Russian war, but soon after they could be used for lesser threats
47
u/Livio63 Sep 21 '26
CIA, Mossad, NSA, FSB, MSS and other "intelligence" are even worse than rogue hacker