SoylentNews is people
SoylentNews
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.
(Score: 5, Insightful) by JoeMerchant on Saturday January 07, @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.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2, Insightful) by shrewdsheep on Saturday January 07, @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, @03:26PM (2 children)
Stop bringing real life into this, we're talking about mathematics, and Bitcoin.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 4, Informative) by mcgrew on Saturday January 07, @03:37PM (1 child)
You misspelled "bitchcoin".
Carbon, The only element in the known universe to ever gain sentience
(Score: 2) by JoeMerchant on Saturday January 07, @03:58PM
There's gonna be a big "who's your Daddy now?" moment when they can break wallet keys.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by stormwyrm on Sunday January 08, @12:38PM
Numquam ponenda est pluralitas sine necessitate.