Quantum Computers Can Break Major Encryption Method, Researchers Claim
Quantum computers can break major encryption method, researchers claim:
A group of researchers has claimed that quantum computers can now crack the encryption we use to protect emails, bank accounts and other sensitive data. Although this has long been a theoretical possibility, existing quantum computers weren't yet thought to be powerful enough to threaten encryption.
Breaking RSA With a Quantum Computer - Schneier on Security
Breaking RSA with a Quantum Computer - Schneier on Security:
A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it's not obviously wrong.
We have long known from Shor's algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what's possible today. (The IBM Osprey is a 433-qbit quantum computer, for example. Others are on their way as well.)
The Chinese group didn't have that large a quantum computer to work with. They were able to factor 48-bit numbers using a 10-qbit quantum computer. And while there are always potential problems when scaling something like this up by a factor of 50, there are no obvious barriers.
Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. And there's the nagging question of why the Chinese government didn't classify this research. But...wow...maybe...and yikes! Or not.
"Factoring integers with sublinear resources on a superconducting quantum processor"
In email, Roger Grimes told me: "Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers...but reviewers found a flaw in his algorithm and that guy had to retract his paper. But this Chinese team realized that the step that killed the whole thing could be solved by small quantum computers. So they tested and it worked."
EDITED TO ADD: One of the issues with the algorithm is that it relies on a recent factoring paper by Peter Schnorr. It's a controversial paper; and despite the "this destroys the RSA cryptosystem" claim in the abstract, it does nothing of the sort. Schnorr's algorithm works well with smaller moduli—around the same order as ones the Chinese group has tested—but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that's what's behind Grimes's comment) but don't give any details—and they haven't tested it with larger moduli. So if it's true that the Chinese paper depends on this Schnorr technique that doesn't scale, the techniques in this Chinese paper won't scale, either. (On the other hand, if it does scale then I think it also breaks a bunch of lattice-based public-key cryptosystems.)
I am much less worried that this technique will work now. But this is something the IBM quantum computing people can test right now.
Related Stories
Expert says the focus on quantum attacks may distract us from more immediate threats:
Three weeks ago, panic swept across some corners of the security world after researchers discovered a breakthrough that, at long last, put the cracking of the widely used RSA encryption scheme within reach by using quantum computing.
Scientists and cryptographers have known for two decades that a factorization method known as Shor's algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. That's because the secret prime numbers that underpin the security of an RSA key are easy to calculate using Shor's algorithm. Computing the same primes using classical computing takes billions of years.
[...]
The paper, published three weeks ago by a team of researchers in China, reported finding a factorization method that could break a 2,048-bit RSA key using a quantum system with just 372 qubits when it operated using thousands of operation steps. The finding, if true, would have meant that the fall of RSA encryption to quantum computing could come much sooner than most people believed.
(Score: 0) by Anonymous Coward on Saturday January 07 2023, @05:01AM (2 children)
Quantum computers aren't even real!
(Score: 5, Funny) by maxwell demon on Saturday January 07 2023, @06:30AM
They are complex, but not purely imaginary.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 4, Informative) by mcgrew on Saturday January 07 2023, @03:35PM
Neither were PCs when This Murray Leinster story about the internet [baen.com] was published the year the first computer, ENIAC, was patented.
Neither was getting more energy out of a fusion reaction that you put in... until last year.
Neither was television when Hugo Gernsback wrote of radio with pictures [mcgrewbooks.com].
There was no such thing as a robot when Edward S. Ellis wrote The Steam Man of the Praries [mcgrewbooks.com] in 1865, until three years later when someone built one.
Oh, what's the use...
mcgrewbooks.com mcgrew.info nooze.org
(Score: 3, Interesting) by RamiK on Saturday January 07 2023, @07:14AM (8 children)
Going from:
To:
Doesn't make sense to me. After all, if you don't understand why Schnorr's algorithm doesn't work for large numbers, there's no reason a small modification to the algorithm won't address the limitation... No?
compiling...
(Score: 3, Interesting) by driverless on Saturday January 07 2023, @08:19AM (1 child)
Yup, it's just a claim, no proof. And they're citing a paper by Schnorr that also doesn't do what it claims to. So it's an unverified claim built on another unverified claim.
So.... anyone want to buy some NFTs of this?
(Score: 2) by JoeMerchant on Sunday January 08 2023, @03:05AM
>want to buy some NFTs of this?
That would be like options trading, right? Value drops to zero after the option expires. All NFTs expire when their ownership secrets can be derived by non owners.
🌻🌻 [google.com]
(Score: 5, Insightful) by JoeMerchant on Saturday January 07 2023, @02:37PM (5 children)
The proof is in the pwnage, whether they show you how or not, one group of researchers provide the crackers with secure keys to break, and the crackers provide the cracked keys back to them at whatever rate they are capable of.
Bonus points if the crackers provide reproducible algorithms.
🌻🌻 [google.com]
(Score: 2, Insightful) by shrewdsheep on Saturday January 07 2023, @03:24PM (3 children)
Well, the algorithm is well-known, absolutely reproducible: https://xkcd.com/538/ [xkcd.com]
(Score: 3, Informative) by JoeMerchant on Saturday January 07 2023, @03:26PM (2 children)
Stop bringing real life into this, we're talking about mathematics, and Bitcoin.
🌻🌻 [google.com]
(Score: 4, Informative) by mcgrew on Saturday January 07 2023, @03:37PM (1 child)
You misspelled "bitchcoin".
mcgrewbooks.com mcgrew.info nooze.org
(Score: 2) by JoeMerchant on Saturday January 07 2023, @03:58PM
There's gonna be a big "who's your Daddy now?" moment when they can break wallet keys.
🌻🌻 [google.com]
(Score: 2) by stormwyrm on Sunday January 08 2023, @12:38PM
Numquam ponenda est pluralitas sine necessitate.
(Score: 3, Insightful) by darkfeline on Saturday January 07 2023, @07:50AM (3 children)
Keep in mind that the idea of "unbreakable" encryption is fairly new. Throughout history, encryption (ciphers) have always been breakable, it's just a matter of how much resources and effort are there. Paper mail is extremely insecure, yet we send things that require some amount of privacy and security anyway.
Even if we do break RSA, I expect it won't affect 99% of communications using it today. It would still be expensive and illegal (though that doesn't help against corrupt governments (which is all of them currently)). People will find ways to secure the things that truly need it, to a tolerable level.
Join the SDF Public Access UNIX System today!
(Score: 5, Insightful) by maxwell demon on Saturday January 07 2023, @08:07AM (2 children)
It being expensive is more important than it being illegal. Criminals don't care about things being illegal (else they'd not be criminals). They do usually care whether what they do is profitable, though. If breaking the encryption used to secure a bank account with a few thousand dollars on it costs a few million dollars, there's simply no incentive to do it.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by crafoo on Saturday January 07 2023, @05:42PM
legality does not matter at all. "legality", the act of writing down a law is a "letter to santa claus". No one cares. At all. The punishment, the money & dedication of competent men spent to investigate, enforce, and punish matter. You can write laws all day and call this or that illegal and no one cares. What matters are the resources and people dedicated to enforcing, punishing, and investigating.
If it costs one dollar more to break the lock than the goods are worth no one will ever steal it.
(Score: 0) by Anonymous Coward on Saturday January 07 2023, @05:48PM
(Score: 4, Funny) by Opportunist on Saturday January 07 2023, @09:18AM
I have a hunch if something in the field of cryptography goes over Schneier's head, I don't need to bother reading TFA.
(Score: 4, Interesting) by Mojibake Tengu on Saturday January 07 2023, @12:37PM
That 10qb machine is most probably a Qianshi, built by Baidu last year.
The problem is, Baidu also has a 36qb
machinechip(!) either under construction or already completed, unclassified. They could even have more complex contraptions built out of these.I'd rather expect the Chinese have the capability close to expectations secretly. Last time I checked, their experimental qubits were 10 billion times faster than Google's (Jiuzhang machine).
Respect Authorities. Know your social status. Woke responsibly.
(Score: 4, Informative) by toph on Saturday January 07 2023, @02:31PM (1 child)
(Score: 3, Interesting) by JoeMerchant on Saturday January 07 2023, @03:28PM
I also don't see the point of publishing a paper claiming you can break 2048 bit RSA when you haven't done it yet - why not break 1024 bit RSA as a demonstration and extrapolate to what will be required to break 2048.
By the way, US security recommendations for RSA have been a minimum of 3072 bits for at least a decade now.
🌻🌻 [google.com]
(Score: 2) by Snospar on Saturday January 07 2023, @03:48PM (1 child)
The Schneier article has been updated several times and it looks like this is a false alarm and in fact 2048-bit RSA has not been broken and is not likely to be broken using this technique.
Huge thanks to all the Soylent volunteers without whom this community (and this post) would not be possible.
(Score: 4, Insightful) by bzipitidoo on Saturday January 07 2023, @05:02PM
This was my hunch. If a quantum computer can factor numbers too large for factorization to be practical on a classical computer, that pretty strongly suggests that P≠NP. Then, either there is a way to implement the quantum algorithm on a classical computer in polynomial time after all, or there's some as yet undiscovered classical polynomial time method for factoring large numbers, or P≠NP.
Most people guess that P≠NP, but it remains stubbornly unproven. In the case that the majority guess is correct, it's not unreasonable to suppose that quantum computers could solve factorization problems that classical computers cannot practically do. But there's so much hype on all this that claims of having cracked the problem should be viewed with great skepticism, and carefully checked.