Chinese Researchers Claim To Find Way To Break Encryption Using Quantum Computers (ft.com) 50
Computer security experts were struggling this week to assess a startling claim by Chinese researchers that they have found a way to break the most common form of online encryption [the link may be paywalled] using the current generation of quantum computers, years before the technology was expected to pose a threat. Financial Times: The method, outlined in a scientific paper [PDF] published in late December, could be used to break the RSA algorithm that underpins most online encryption using a quantum machine with only 372 qubits -- or quantum bits, a basic unit of quantum computing -- according to the claims from 24 researchers from a number of academic bodies and state laboratories. IBM has already said that its 433 qubit Osprey system, the most powerful quantum computer to have been publicly unveiled, will be made available to its customers early this year.
If correct, the research would mark a significant moment in the history of computer security, said Roger Grimes, a computer security expert and author. "It's a huge claim," he said. "It would mean that governments could crack other governments secrets. If it's true -- a big if -- it would be a secret like out of the movies, and one of the biggest things ever in computer science." Other experts said that while the theory outlined in the research paper appeared sound, trying to apply it in practice could well be beyond the reach of today's quantum technology. "As far as I can tell, the paper isn't wrong," said Peter Shor, the Massachusetts Institute of Technology scientist whose 1994 algorithm proving that a quantum machine could defeat online encryption helped to trigger a research boom in quantum computing. Shor's method requires machines with many hundreds of thousands, or even millions, of qubits, something that many experts believe is a decade or more away.
If correct, the research would mark a significant moment in the history of computer security, said Roger Grimes, a computer security expert and author. "It's a huge claim," he said. "It would mean that governments could crack other governments secrets. If it's true -- a big if -- it would be a secret like out of the movies, and one of the biggest things ever in computer science." Other experts said that while the theory outlined in the research paper appeared sound, trying to apply it in practice could well be beyond the reach of today's quantum technology. "As far as I can tell, the paper isn't wrong," said Peter Shor, the Massachusetts Institute of Technology scientist whose 1994 algorithm proving that a quantum machine could defeat online encryption helped to trigger a research boom in quantum computing. Shor's method requires machines with many hundreds of thousands, or even millions, of qubits, something that many experts believe is a decade or more away.
Calculating chance (Score:5, Insightful)
What are the chances that a Chinese team would find a way to crack a code that according to TFS secures a lot of the traffic on the internet.... and then tell the world about it instead of giving its government an ace up its sleeve?
Re: (Score:2)
Re: Calculating chance (Score:2, Insightful)
the idea that Chinese researchers are all pawns of thier state or equally Malovent without state influence is absurd... some people love thier jobs and Confucius actually taught this joy... now, my expertize cannot provide meaningful discovery if they found a trick but I would no doubt expect in the frontier of computing, man tricks aren't yet understood and China invests heavily in quantum and AI... this maybe they would find them. More so the good will of exposing these issues may be in Thier favor when a
Re: Calculating chance (Score:5, Insightful)
the idea that Chinese researchers are all pawns of thier state or equally Malovent without state influence is absurd... some people love thier jobs and Confucius actually taught this joy... now, my expertize cannot provide meaningful discovery if they found a trick but I would no doubt expect in the frontier of computing, man tricks aren't yet understood and China invests heavily in quantum and AI... this maybe they would find them. More so the good will of exposing these issues may be in Thier favor when a silicon war is on Thier doorstep... many things to consider and biases often deceive us
The only thing more absurd than the idea that Chinese researchers are all pawns of their state or equally malevolent without state influence is the belief that the CCP would grant Chinese researchers agency on whether they become pawns of the state.
Re: (Score:2)
... at least publicly
Re: (Score:2)
Why would the CCP care? They must assume that everyone else is working on quantum computers to decrypt Chinese internet data, and everyone else is working on post-quantum crypto too. There is nothing to gain by suppressing it.
In fact there is everything to gain by releasing it. Demand for quantum resistant crypto is mounting, and China demonstrating mastery of it makes their products more attractive.
Don't like your CDS prevent you from thinking rationally about these things.
Re:Calculating chance (Score:5, Insightful)
What are the chances that a Chinese team would find a way to crack a code that according to TFS secures a lot of the traffic on the internet.... and then tell the world about it instead of giving its government an ace up its sleeve?
If you actually *can't* break someone's encryption, making them think you have will occasionally make them switch to a new encryption that you *can* break.
Also, given that there's a bit of economic belligerence going on between China and other nations right now, maybe they just want to take a jab at Western consumer confidence in online transactions.
Re:Calculating chance [that it's just FUD?] (Score:2, Flamebait)
Nice FP, though I'm not sure it deserves the "Insightful" moderation because that was also my initial reaction. A simple "Interesting" might have sufficed?
My other initial thought is that it would be good if international cooperation were improving so that it might even make sense for them to share their analytic results with other researchers. Sad joke, that. Or a sick joke, as it applies to the dangerous politicization of pandemic responses.
However my more considered reaction is that the paper might make
Re: (Score:2)
There's no way that's going to stop people from using one kind of encryption before they've got a better one. After all, quantum computers are in short supply. So that reasoning doesn't work.
My guess is they're letting people know "We can peek at you", but they aren't going to release enough info to let it be duplicated. OTOH, that's a *guess*. Time will reveal the script.
Re: (Score:1)
Your tone sounds like you want to disagree but your substance seems to be in concurrence with my theory? Or maybe some confusion about how FUD works? There's also the question of how much control the Chinese government has over exactly what Chinese researchers can publish. It might be a weaker degree of control than either of us seem to think?
Maybe a historical anecdote will clarify my position, though it's kind of on the other side of the topic. The Japanese continued using their cyphers partly because the
Re: (Score:2)
OK, but "Secret" information isn't most of what's protected by encryption. Most of it's just https stuff. With quantum computers in really short supply, that isn't going to get decrypted with this. (OTOH, other comments seem to say that the current quantum computers are still orders of magnitude away from finding this approach useful even for high priority stuff. But even if they were up to it, only governments or REALLY large financial operations would be targets.)
One exception that occurs to me is tec
Re: (Score:2)
Seems more basic concurrence, though I thought there were technical solutions that make the "record for later" options untenable or infeasible.
Please, please (Score:4, Insightful)
Quit linking to articles that are completely paywalled.
Re:Please, please (Score:4, Informative)
Here ya go
https://archive.is/susf8 [archive.is]
Re:Please, please (Score:4, Funny)
Quit linking to articles that are completely paywalled.
Don't worry.
With this development, it won't be long before every paywall account gets cracked, and all the content will be freely available anyway.
Re: (Score:2)
and all the content will be freely available anyway.
Unless you live in China, where it's likely still censored.
Re: (Score:2)
ssshhh, you're ruining my excuse to not RTFA.
Re: (Score:2)
If you're a guy, you don't need an excuse not to read anything. Articles, manuals, installation instructions... not reading them should be a point of pride!
Re: (Score:1)
You do risk the accusation of being a misandrist.
Not quite there yet (Score:5, Informative)
From the paper:
We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits. However, it should be noted that some of the factored integers have been carefully selected with special structures, thus the largest integer factored by a general method in a real physical system by now is 249919 (18-bit).
We find that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 even in the simplest 1D-chain system.
Yes, a 372-qbit machine may be able to factorize a carfully selected 2048-bit number.
But one would need way more qbits for a "general RSA-2048 private key".
Still a very interesting breakthrough, but no need to panic yet.
Re:Not quite there yet (Score:4, Informative)
You've cherry-picked and reorganized what the paper says and therefore appear to have come to the wrong conclusion.
What the paper actually says is:
--------
Alternatively, integer factorization can be transformed into an optimization problem, which can be solved by adiabatic quantum computation (AQC) [19–22] or QAOA [23]. Larger numbers have been factored using these approaches, in various physical systems [24–27]. The maximum integers factorized are 291311 (19-bit) in NMR system [26], 249919 (18- bit) in D-Wave quantum annealer [25], 1099551473989 (41-bit) in superconducting device [27]. However, it should be noted that some of the factored integers have been carefully selected with special structures [28], thus the largest integer factored by a general method in a real physical system by now is 249919 (18-bit). ...
Using this algorithm, we have successfully factorized the integers 1961 (11-bit), 48567227 (26-bit) and 261980999226229 (48-bit), with 3, 5 and 10 qubits in a superconducting quantum processor, respectively. The 48-bit integer, 261980999226229, also refreshes the largest integer factored by a general method in a real quantum device. We proceed by estimating the quantum resources required to factor RSA-2048. We find that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 even in the simplest 1D-chain system. Such a scale of quantum resources is most likely to be achieved on NISQ devices in the near future.
---------
The first paragraph talks about EXISTING experiments, the second is talking about the NEW techniques and experiments. The new algorithm is claimed to be a GENERAL method (ie, NOT requiring specially selected integers).
The authors are claiming their GENERAL technique should be able to crack any RSA-2048 encryption using 372 qubits and since quantum computers with 400+ bits exist today that would in fact make this a real threat. It all depends on whether the paper itself and the estimates given are accurate. If they are then things are about to get really interesting in the world of espionage.
Re: (Score:3)
The authors are claiming their GENERAL technique should be able to crack any RSA-2048 encryption using 372 qubits and since quantum computers with 400+ bits exist today that would in fact make this a real threat. It all depends on whether the paper itself and the estimates given are accurate. If they are then things are about to get really interesting in the world of espionage.
The number of qubits in a system is a totally meaningless indication of computing power used exclusively for PR/marketing purposes. The promise of quantum computers was addressing search spaces of 2^qubits offering exponential scaling with number of qubits.
With todays machines you can't simply count up the number of qubits in a system and draw any conclusions as to computing power of that system. What those qubits do and how they are arranged are critical.
If for example you have two parallel machines and
Re: (Score:1)
the largest integer factored by a general method in a real physical system by now is 249919 (18-bit).
This one can be done with pencil and paper or a pocket calculator
sqrt(249919) = 499.91899 then round to next integer
sqrt(500*500 - 249919) = 9
your factors are 500 + 9 and 500 - 9 or 249919 = 509 * 491
What about Elliptic Curve? (Score:2)
It seems likely that EC will fall to a quantum approach too, but does the described method weaken EC as well as RSA?
And yeah, the paywalled articles suck.
"secret like out of the movies" (Score:4, Interesting)
Re: (Score:2)
Re: (Score:2)
IF they can do, why don't they steal bitcoin? (Score:2)
Re: (Score:1)
Clickbait Lies (Score:4, Insightful)
If anyone actually broke factoring and wanted to prove it, they could publish the factors to some of the The Cunningham Project's most wanted [purdue.edu]
These jokers have a method for factoring that they think will work on a quantum computer, if they had one which they don't, and they aren't willing to estimate how long it would take.
Color me unimpressed.
Re: (Score:3)
They claim to have access to one:
Using this algorithm, we have successfully factorized the integers 1961 (11-bit), 48567227 (26-bit) and 261980999226229 (48-bit), with 3, 5 and 10 qubits in a superconducting quantum processor, respectively. The 48-bit integer, 261980999226229, also refreshes the largest integer factored by a general method in a real quantum device
Just not one with 372 bits which they estimate is needed for 2048 bit RSA
Isn't Schnorr's algorithm bunk to begin with? (Score:2)
If the smooth relation pairs simply don't exist, adding quantum to Schnorr's algorithm won't help.
Critical note (Score:5, Informative)
Here's Bruce Schneier's take, with feedback from Roger Grimes. https://www.schneier.com/blog/... [schneier.com]
TL;DR: "this Chinese paper is based on a flawed paper that works on smaller numbers, not on larger ones. The Chinese team claims they solved the flaw, yet still only solve for small numbers."
Please help (Score:2)
I can't even figure out if the paper is written by chatGPT3 or by "real humans".
I have limited understanding of QC, but this paper indeed sounds very promising and it will require increasing bit length (we have done this few times, so not a problem) to 4096 in short term and finding a new QC proof encryption.
Re: (Score:1)
> I can't even figure out if the paper is written by chatGPT3 or by "real humans".
So it passed the "PHB Complete" test: it can fool a PHB.
TFS Exhibits Ignorance (Score:5, Informative)
> The method, outlined in a scientific paper [PDF] published in late December, could be used to break the RSA... using a quantum machine with only 372 qubits
> IBM has already said that its 433 qubit Osprey system, ... , will be made available to its customers early this year.
Those two numbers are not referring to the same thing. Quantum computers are very unreliable and as you extend the number of entangled bits and the number of iterations it gets less reliable. A way to mitigate this is to run the same computation many time. When it's easy to check if you have the right answer, this is fine, like factoring. Rerun until you get the right answer. The IBM machine referenced achieves entanglement of a total of *9* bits, not 433. The 433 qbits are there so you can run the same algorithm over 9 bits many times in parallel, to speed up the time to get a right answer factoring number below 512.
The iteration count of the factoring algorithm (Shor's) (where noise is accumulating, so it's a limiter) for RSA2048 is of the order of 2048. I don't remember where the IBM machine is on this. It may be about 10. So 9 bits x 10 iterations is not even close to 372 bits x 2048 iterations.
Re: (Score:3)
None of that is a criticism of the paper. The paper is (1) Well written and readable and (2) documents a neat trick where they can run an algorithm like Shor's in fewer qbits than it would otherwise take (I.E. 372 rather than 2048). That there remains no machine to run it doesn't alter the cool ideas in the paper.
The error is all in the reporting.
But Robert Redford already showed us how (Score:2)
Itâ(TM)s all crackable (Score:2)
All encryption should be considered crackable, so it is simply a question of deciding who you are protecting against, the time period and computational resources.
Most people arenâ(TM)t super powers throwing huge amounts of money and resources to crack high levels of encryption. At the same a 2048 bit key will be crackable by more people
in a few years than today, but that is a natural evolution of the encryption arms race.
If it *really* worked, Xi's goons would (Score:2)
...lock them on a skunk-works compound to work on spyware, and they'd have to STFU. Thus, I suspect a marketing gimmick.
Scott Aaronson on it (Score:2)
Uh huh (Score:2)
Even if the algorithm scales the way they predict, there's more to it than just the number of bits. That "depth of thousands" is there too. If I'm reading IBM's graph correctly, their at maximum width is pretty consistently around... 1.
https://research.ibm.com/blog/... [ibm.com]
Also, if your government is encrypting sooper sektrit stuff with RSA, they really should expect it to g
RSA Encryption in Transit Only? (Score:1)
Wouldn't this only break encryption in transit using the RSA algorithm? Most encryption at rest uses AES or something similar, which it's currently uncertain whether a quantum computer could break (but generally assumed that it could). Also, other encryption in transit methods aren't affected yet either.
âoeSneakersâ (Score:1)
Should already be taking precautions (Score:2)
Debunked already (Score:4, Interesting)