Breakthrough quantum algorithm can break advanced data encryption

For context, quantum factoring is a process capable of rendering widely-used encryption systems like RSA ineffective.

Threat to RSA encryption

RSA encryption is a cornerstone of digital communication. It derives its security from the inherent difficulty for classical computers to factorize large numbers.

“The system is based on the idea that factoring a 2,048-bit integer (a number with 617 digits) is too hard for a computer to do in a reasonable amount of time,” explained the researchers in a press release.

However, quantum computers leverage the unique principles of quantum mechanics and possess the theoretical capacity to execute this factorization at significantly faster speeds. But quantum computers are not free from shortcomings either. The key challenges they face include noise and resource constraints.

A quantum circuit aiming to factor a very large number would need to execute multiple runs, carrying out operations that include calculating powers such as 2 raised to the 100th power, according to the press release.

“But computing such large powers is costly and difficult to perform on a quantum computer, since quantum computers can only perform reversible operations,” it explained.

“Squaring a number is not a reversible operation, so each time a number is squared, more quantum memory must be added to compute the next square.”

Simplifying calculation

The researchers discovered a technique to calculate exponents using a series of Fibonacci numbers. This method only needs simple multiplication, which is reversible, instead of squaring. Importantly, it requires just two quantum memory units to calculate any exponent.

“It is kind of like a ping-pong game, where we start with a number and then bounce back and forth, multiplying between two quantum memory registers,” highlighted Vaikuntanathan.

Besides, quantum computers operate using quantum circuits comprised of quantum gates, which can introduce noise and lead to errors. However, achieving error-free quantum gates is not feasible on an actual machine.

The team resolved this issue by employing a technique that filters out corrupt results, ensuring that only the correct ones are processed.

“The end-result is a circuit that is significantly more memory-efficient. Plus, their error correction technique would make the algorithm more practical to deploy,” asserted the press release.

The road ahead

Although this breakthrough represents a significant stride towards practical quantum factoring, its implementation on actual quantum hardware remains a future goal.

Current quantum computers lack the capabilities necessary to execute such complex algorithms.

However, as Oded Regev, a computer scientist at New York University, noted, the MIT team’s work “brings quantum factoring algorithms closer to reality.”

This development highlights the pressing need to develop new cryptographic systems resistant to quantum attacks.

As quantum computers continue to evolve, advancements like this one bring us closer to a future where quantum machines could pose a genuine threat to our current encryption standards.