When you send an email or make an online purchase, your data is protected by encryption—a system that ensures only the intended recipient can access the information.
One of the most common encryption methods is based on the idea that breaking a large number into its factors (like finding two numbers that multiply to make a big number) is nearly impossible for even the fastest classical computers.
However, quantum computers promise to solve this problem quickly, which could undermine the security of many online communications.
In 1994, Peter Shor, now a professor at MIT, proposed a quantum algorithm that could crack these large numbers, threatening the very foundation of our current cryptographic systems.
But while this algorithm was a groundbreaking discovery, building a quantum computer powerful enough to run it has proven to be a huge challenge.
Even 30 years later, researchers are still working on it.
As scientists continue to develop larger quantum computers, others are focusing on improving Shor’s algorithm to make it run on smaller, more efficient quantum circuits.
Last year, New York University computer scientist Oded Regev made a significant improvement to Shor’s algorithm. His version could run faster, but it required a lot more memory, which is a big challenge in quantum computing.
Building on Regev’s work, researchers at MIT have now developed a new quantum algorithm that combines the speed of Regev’s approach with the memory efficiency of Shor’s.
This new algorithm uses fewer quantum bits (or qubits), which are the basic units of quantum information, and is more resistant to the noise that often disrupts quantum computations. This makes it more practical for future use.
Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering at MIT and a senior author of the study, explained the significance of their work.
“If we ever build large-scale quantum computers, traditional methods of encryption, like the ones we use today, will become vulnerable. Our work could be a step towards making quantum factoring more practical, which is important for the future of cryptography.”
The study, led by MIT graduate student Seyoon Ragavan, was presented at the 2024 International Cryptology Conference (Crypto 2024). Their research suggests that this new algorithm could eventually lead to the development of encryption methods that can withstand the power of quantum computers.
Understanding the threat Most online communications today rely on an encryption method known as RSA, named after its inventors, MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman.
RSA encryption is based on the difficulty of factoring very large numbers, such as a 2,048-bit integer (a number with 617 digits). For a classical computer, this task would take an impractical amount of time.
But in 1994, Peter Shor showed that a quantum computer could factor such large numbers quickly, potentially breaking RSA encryption. However, building a quantum computer large enough to run Shor’s algorithm has been a major hurdle.
It’s estimated that a quantum computer would need around 20 million qubits to break RSA encryption, while the largest quantum computers today have only about 1,100 qubits.
Quantum computers use quantum circuits, just like classical computers use classical circuits. Each quantum circuit is made up of operations known as quantum gates, which perform calculations using qubits. However, quantum gates can introduce noise, so the fewer gates a quantum circuit has, the better its performance.
This is where Regev’s improvement to Shor’s algorithm came into play. His version required fewer quantum gates but demanded a lot more qubits for memory, creating a new problem. As Vaikuntanathan explained, “Qubits can decay over time, so you want to minimize the number you need to keep around.”
A better solution Inspired by Regev’s work, the MIT researchers found a way to reduce the memory requirements while maintaining the speed of the algorithm.
Instead of performing operations like squaring numbers, which require more memory, they used a clever method involving Fibonacci numbers and simple multiplication. This approach only needs two quantum memory units to compute any large power.
Vaikuntanathan compared their method to a ping-pong game, where a number bounces back and forth between two quantum memory registers. They also developed a technique to correct errors in quantum operations, making their algorithm more practical for real-world use.
The result is a quantum circuit that is not only more memory-efficient but also more tolerant of errors. While this algorithm is still not ready to break RSA encryption, it brings us closer to that possibility.
“The authors have addressed the two biggest challenges in earlier quantum factoring algorithms,” Regev said. “While still not immediately practical, their work brings quantum factoring algorithms closer to reality.”
Looking ahead, the researchers hope to further refine their algorithm and eventually test it on a real quantum computer. “The big question now is whether this work actually brings us closer to breaking RSA encryption,” Ragavan said. “We’re not there yet, but this is a step in the right direction.”
As quantum computing continues to advance, developing encryption methods that can resist quantum attacks will be crucial for ensuring the security of our digital communications in the future.
