Quantum Computing Breakthrough Could Crack Modern Encryption
Cambridge, MA – Anew breakthrough in quantum computing could have significant implications for the future of cryptography, potentiallyrendering current encryption methods vulnerable. Researchers at MIT have developed a new algorithm that could significantly speed up the process of factoring large numbers, a task that is currently consideredcomputationally impossible for classical computers. This advancement could lead to the development of quantum computers capable of breaking widely used encryption schemes like RSA, which is used to secure onlinecommunications.
The new algorithm, described in a paper to be presented at the 2024 International Cryptology Conference, builds upon the work of Oded Regev, a computer scientist at New York University, who in 2023 proposed a significant theoretical improvement to Shor’s algorithm, a quantum algorithm for factoring large numbers. Shor’s algorithm, proposed in 1994 by Peter Shor, a professor at MIT, has been considered a majorthreat to modern cryptography for decades.
While researchers have made significant progress in building quantum computers, they have yet to build a machine powerful enough to run Shor’s algorithm. The new algorithm, developed by Seyoon Ragavan, a graduate student in MIT’s Department of Electrical Engineering and Computer Science, and VinodVaikuntanathan, a professor of engineering at MIT, offers a potential solution.
If large-scale quantum computers are eventually built, then factoring algorithms will break, and we will have to find other encryption methods, said Vaikuntanathan. But will that really be a threat? Can wemake quantum factoring algorithms practical? Our research may bring us closer to practicality.
The MIT researchers’ algorithm combines the speed of Regev’s algorithm with the memory efficiency of Shor’s algorithm. It is as fast as Regev’s algorithm but requires fewer quantum components, known as qubits, and is moretolerant to quantum noise, making it potentially easier to implement in practice.
This is a big deal because it is the first real improvement to the circuit that Shor proposed in 1994, said Vaikuntanathan.
The key to the new algorithm lies in its use of a series of Fibonaccinumbers to calculate powers, a process that requires only simple multiplication operations, which are reversible. This allows the algorithm to be performed with just two quantum memory units, significantly reducing the memory requirements compared to previous approaches.
It’s a bit like a ping-pong game, explained Vaikuntanathan. We start with a number, and then we bounce it back and forth between two quantum memory registers, performing multiplication operations.
The researchers also addressed the issue of error correction. Shor’s and Regev’s algorithms require every quantum operation to be perfect for the algorithm to work correctly. However, achieving error-freequantum gates in real machines is impossible. The MIT researchers overcame this challenge by using a technique to filter out erroneous results and only process correct ones.
The result is a significantly more memory-efficient circuit that is also more practical due to its error-correction capabilities.
The authors address two of the most important bottlenecksin previous quantum factoring algorithms, said Regev. While still not practical, their work brings quantum factoring algorithms closer to reality.
While the new algorithm represents a significant step forward, it is still not practical for breaking RSA encryption. The researchers hope to make their algorithm even more efficient and eventually test it on real quantumcircuits.
The question that remains after this work is: does this really bring us closer to breaking RSA encryption? It is not clear yet; these improvements only become apparent when the integers are much larger than 2048 bits. Can we push this algorithm to make it more feasible than Shor’s algorithmfor factoring 2048-bit integers? asked Ragavan.
The research was funded by the Akamai Presidential Fellowship, the Defense Advanced Research Projects Agency (DARPA), the National Science Foundation, the MIT-IBM Watson AI Lab, the Thornton Family Faculty Research Innovation Fellowship, and the Simons Investigator Award.
This breakthrough highlights the potential impact of quantum computing on cryptography and the need for researchers to develop new, quantum-resistant encryption methods. As quantum computers continue to improve, the race to secure our digital world is only getting more intense.
Views: 0