MIT scientists have created a new quantum algorithm that could bring us closer to cracking complex cryptographic systems. This advancement combines the speed of recent breakthroughs with improved memory efficiency, potentially paving the way for more practical quantum computing applications in cryptography.
The Quest for Quantum Code-Breaking
Most of our digital communication relies on encryption methods that classical computers can’t crack in a reasonable timeframe. The widely used RSA encryption system, for instance, depends on the difficulty of factoring extremely large numbers. A 2,048-bit RSA key (a number with 617 digits) is considered secure against conventional computing attacks.
However, quantum computers promise to change this landscape dramatically. In 1994, Peter Shor, now an MIT professor, proposed a quantum algorithm that could theoretically break RSA encryption far more quickly than any classical computer.
Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering at MIT, explains the potential impact: “If large-scale quantum computers ever get built, then factoring is toast and we have to find something else to use for cryptography. But how real is this threat? Can we make quantum factoring practical? Our work could potentially bring us one step closer to a practical implementation.”
Despite significant progress in quantum computing over the past three decades, we’re still far from building a quantum computer powerful enough to run Shor’s algorithm effectively. Current estimates suggest that about 20 million qubits (quantum bits) would be needed, while the largest quantum computers today have only around 1,100 qubits.
A New Approach to Quantum Factoring
The MIT team, led by Vaikuntanathan and graduate student Seyoon Ragavan, built upon recent theoretical improvements proposed by New York University computer scientist Oded Regev. Their new algorithm combines the speed of Regev’s approach with improved memory efficiency.
Quantum computers use quantum circuits composed of quantum gates that manipulate qubits to perform calculations. However, these gates introduce noise, which can lead to errors. The MIT researchers tackled this challenge by developing a technique to filter out corrupt results and only process the correct ones.
Vaikuntanathan explains their novel approach to handling large numbers: “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.” This method allows them to compute any exponent using just two quantum memory units, significantly reducing the required resources.
The result is an algorithm that is not only faster but also more resilient to quantum noise and requires fewer qubits. This combination of features could make it more feasible to implement on real quantum hardware in the future.
Oded Regev, commenting on the MIT team’s work, says: “The authors resolve the two most important bottlenecks in the earlier quantum factoring algorithm. Although still not immediately practical, their work brings quantum factoring algorithms closer to reality.”
Why it matters: This research represents a significant step towards making quantum factoring more practical. As quantum computers continue to advance, improvements in algorithms like this one could accelerate the timeline for when quantum machines might be able to break current encryption methods. This underscores the urgency of developing new, quantum-resistant cryptographic systems to protect sensitive data in the future.
However, it’s important to note that we’re still far from seeing these algorithms implemented on real quantum hardware. Ragavan raises a crucial question: “Does it actually bring us closer to breaking RSA cryptography? That is not clear just yet; these improvements currently only kick in when the integers are much larger than 2,048 bits. Can we push this algorithm and make it more feasible than Shor’s even for 2,048-bit integers?”
The research, which will be presented at the 2024 International Cryptology Conference, was supported by various organizations including the U.S. Defense Advanced Research Projects Agency and the National Science Foundation. As work continues in this field, we can expect to see further refinements and potentially new breakthroughs that could reshape the landscape of digital security.
