SoylentNews

Quantum Computers Can Break Major Encryption Method, Researchers Claim

upstart [soylentnews.org] writes:

████ # This file was generated bot-o-matically! Edit at your own risk. ████

Quantum computers can break major encryption method, researchers claim [newscientist.com]:

A group of researchers has claimed that quantum computers [newscientist.com] 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.

However, security experts have expressed doubt about the new claim, saying that although the code-breaking technique appears valid, there is no reason to expect it could crack encrypted data in a practical timescale or that current quantum hardware …

VIEW JANUARY SALE OFFERS [newscientist.com]

No commitment, cancel anytime*

Offer ends 14th March 2023. *Cancel anytime within 14 days of payment to receive a refund on unserved issues.

Existing subscribers, please log in [newscientist.com] with your email address to link your account access.

Inclusive of applicable taxes (VAT)

Offer ends 14th March 2023. *Cancel anytime within 14 days of payment to receive a refund on unserved issues.

Existing subscribers, please log in [newscientist.com] with your email address to link your account access.

Inclusive of applicable taxes (VAT)

Advertisement TrendingLatestVideoFree

1. Quantum camera takes images of objects that haven’t been hit by light [newscientist.com]
2. Quantum computers can break major encryption method, researchers claim [newscientist.com]
3. Largest ever animal may have been Triassic ichthyosaur super-predator [newscientist.com]
4. AI legal assistant will help defendant fight a speeding case in court [newscientist.com]
5. Ship taller than Eiffel Tower will build biggest offshore wind farm [newscientist.com]

1. Amazon deforestation may shrink Himalayan snow and Antarctic ice [newscientist.com]
2. Reef fish are more placid around islands infested with invasive rats [newscientist.com]
3. Quantum computers can break major encryption method, researchers claim [newscientist.com]
4. Pre-eclampsia and hypertension in pregnancy linked to 19 gene variants [newscientist.com]
5. Physicists should take time to ponder the strangest ideas [newscientist.com]

1. The scientific guide to a better Christmas dinner [newscientist.com]
2. Porvenir massacre: Did US army have larger role in 1918 killings? [newscientist.com]
3. Watch Orion capsule splash down as NASA’s Artemis I mission ends [newscientist.com]
4. Livestream: Watch Hawaii’s Mauna Loa volcano erupting [newscientist.com]
5. Lee Berger: Rewriting human history [newscientist.com]

1. Amazon deforestation may shrink Himalayan snow and Antarctic ice [newscientist.com]
2. Reef fish are more placid around islands infested with invasive rats [newscientist.com]
3. Low-carb diet reduces seizures for people with drug-resistant epilepsy [newscientist.com]
4. Synthetic tissue restores erections in pigs with penis injuries [newscientist.com]
5. Crystal device could be used to build tiny particle accelerators [newscientist.com]

MORE FROM NEW SCIENTIST Europe’s fastest supercomputer is now connected to a quantum computer A small quantum computer has been connected to Europe’s fastest supercomputer. This connection could help researchers work out how to best pair quantum computers together with powerful supercomputers to solve complex problems faster Physics [newscientist.com] IBM quantum computer runs largest quantum program yet Large quantum programs build up errors as they run, but a technique for mitigating these errors has allowed researchers at IBM to run over 1700 operations on their quantum computer Physics [newscientist.com] Google calls for urgent switch to quantum-safe encryption as US delays A US body in charge of choosing new encryption algorithms that can withstand quantum computers has delayed announcing them due to undisclosed legal reasons, while a team at Google is calling for an immediate switch Technology [newscientist.com] Quantum encryption could stop scammers from faking their locations A technique that uses quantum computers to verify a device's location can only be hacked with a quantum machine thousands of times larger than those currently in existence Physics [newscientist.com] ;

Breaking RSA With a Quantum Computer - Schneier on Security

upstart [soylentnews.org] writes:

████ # This file was generated bot-o-matically! Edit at your own risk. ████

Breaking RSA with a Quantum Computer - Schneier on Security [schneier.com]:

Breaking RSA with a Quantum Computer

A group of Chinese researchers have just published [arxiv.org] 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 [ibm.com] 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 [arxiv.org]”

Abstract: Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN ), which is sublinear in the bit length of the integer N , making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

In email, Roger Grimes [amazon.com] 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 [iacr.org] 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.

EDITED TO ADD (1/4): A reporter just asked me my gut feel about this. I replied that I don’t think this will break RSA. Several times a year the cryptography community received “breakthroughs” from people outside the community. That’s why we created the RSA Factoring Challenge: to force people to provide proofs of their claims. In general, the smart bet is on the new techniques not working. But someday, that bet will be wrong. Is it today? Probably not. But it could be. We’re in the worst possible position right now: we don’t have the facts to know. Someone needs to implement the quantum algorithm and see.

Posted on January 3, 2023 at 12:38 PM [schneier.com] • 42 Comments [schneier.com]

Yikes?

Original Submission #1  Original Submission #2