End of cryptography in sight? So far, data encryption has withstood the computing power of quantum computers — but that could soon change. US researchers have now developed a method that makes quantum-based cracking of common RSA encryption faster and more efficient. Instead of millions of qubits and error-free quantum operations as required by Shor’s algorithm, significantly smaller, less perfect quantum computers are sufficient. Is the imminent end of RSA encryption looming?
Whether it’s emails, online shopping, or other digital communication: Most data is transmitted in encrypted form today. A common method is RSA cryptography, which uses large numbers generated by multiplying prime numbers as keys. Because determining which factors were used to generate this number is almost impossible for classical computers due to the large selection of possibilities — it requires enormous computational effort.
Shor’s algorithm and its weaknesses
But not for quantum computers: Because their qubits can simultaneously check countless potential solutions through quantum superposition, RSA encryption is no longer uncrackable for them — at least in theory. US mathematician Peter Shor published an algorithm that could achieve this as early as 1994. “That was a turning point. But in 1994, no one knew how to build a quantum computer of the necessary size,” explains Vinod Vaikuntanathan from the Massachusetts Institute of Technology (MIT).
The problem: Shor’s algorithm is inefficient. To crack the currently common 2048-bit RSA encryption with it, you would need about 20 million error-free qubits — which is hardly feasible due to the susceptibility of qubits to interference. “Some people even think that it will never be possible to develop a large enough quantum computer,” says Vaikuntanathan. In fact, most current quantum computers have only a few dozen qubits, with the largest quantum computer to date having just over 1,100 qubits.
New Method is Faster and More eEconomical
But there is another possibility — and Vaikuntanathan and his colleague Seyoon Ragavan have now used it: They have developed an improvement to Shor’s algorithm that makes it much faster and more economical. The starting point for this is an algorithm developed by Oded Regev from New York University almost a year ago. While this can accelerate crypto code cracking compared to Shor’s algorithm, it still requires more quantum bits as memory.
This is where the two MIT researchers come in: They have now developed a solution that is as fast as Regev’s approach but requires fewer qubits. Their quantum algorithm also includes a method that reduces the error rate and makes quantum calculations more robust against interference. “Our work could thus bring us one step closer to practical implementation,” says Vaikuntanathan.
Ping-Pong in the Memory Register
Specifically, the new method comprises two approaches. Firstly, the two MIT researchers circumvent the need to work with squarings. This is because calculations with powers of two are not directly reversible and are therefore complex and memory-intensive. “We avoid this by using Fibonacci exponentiation. This method does not use modular squaring and instead only uses modular multiplication,” explain Vaikuntanathan and Ragavan. This variant of mathematical matrix exponentiation allows power calculations to be carried out more quickly and efficiently.
In the case of code cracking via quantum computer, this means: For each exponent that needs to be calculated when factoring the cryptographic code, the new algorithm only requires two quantum memory units. “It’s like a kind of ping-pong game: We start with a number and then jump back and forth between the two quantum memory registers when multiplying,” explains Vaikuntanathan. “As a result, our algorithm uses at least 13 times fewer qubits than Regev’s for 2048 bits.”
Errors Are Filtered Out
The second improvement concerns error correction: For the quantum algorithms of Shor and Regev, each quantum operation must run virtually error-free — a requirement that is practically impossible to implement in the foreseeable future. Although physicists have already developed some methods to reduce the error rate of quantum computers, even record models currently only achieve a reliability of around 35 percent.
The two MIT researchers circumvent this by identifying potentially defective outputs of the qubit circuits based on certain characteristics. “Based on this, we develop a filter procedure that allows us to detect and filter out these corrupted units,” explain Vaikuntanathan and Ragavan. “This gives us a collection of intact units that can then be fed into the classical post-processing according to Regev’s algorithm.”
Two Hurdles of Quantum Factorization Overcome
Together, the team has thus succeeded in cracking two major hurdles of cryptography breaking using quantum computers. “The big question, however, is whether this brings us closer to cracking RSA encryption,” says Ragavan. “So far, this is not quite clear, because our improvements only take effect with numbers larger than 2048 bits.” Whether the algorithm can be further optimized to crack the common 2048-bit number keys remains to be seen.
Nevertheless, this brings the end of RSA encryption a small step closer, Regev also believes: “The two researchers overcome the two most important bottlenecks of earlier algorithms for quantum factorization,” he comments. “Even if their work is not immediately practically implementable, it brings quantum factorization closer to reality.”
