Towards A Code-Breaking Quantum Computer
The most recent email you sent was most likely encrypted using a tried-and-true approach based on the assumption that even the fastest computer could not efficiently break down a massive number into factors.
Quantum computers, on the other hand, promise to quickly crack complicated cryptographic schemes that a traditional computer may never be able to decipher. This promise is based on a quantum factoring technique proposed in 1994 by Peter Shor, now an MIT professor.
While researchers have made significant progress in the last 30 years, they have yet to construct a quantum computer powerful enough to run Shor’s algorithms.
While some researchers aim to create larger quantum computers, others have attempted to enhance Shor’s algorithm so that it can run on a smaller quantum circuit. Oded Regev, a computer scientist at New York University, proposed a significant theoretical enhancement approximately a year ago. His algorithm could be faster, but it would require more memory.
Building on previous findings, MIT researchers presented a hybrid technique that combines Regev’s speed with Shor’s memory efficiency. This new algorithm is as quick as Regev’s, uses fewer quantum building units known as qubits, and is more resistant to quantum noise, making it more viable to execute in practice.
In the long run, this new technique could help to design unique encryption approaches that can survive quantum computers’ code-breaking power.
“If large-scale quantum computers are ever created, factoring will be obsolete, and we will need to find an alternative for cryptography. But how real is the threat? Can we make quantum factoring practical? “Our work may bring us one step closer to a practical implementation,” says Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and senior author of a paper explaining the technique.
The paper’s principal author is Seyoon Ragavan, a graduate student at MIT’s Department of Electrical Engineering and Computer Science. The findings will be presented at the 2024 International Cryptology Conference.
Cracking Cryptography
Service providers such as email clients and messaging apps often rely on RSA, an encryption system devised by MIT academics Ron Rivest, Adi Shamir, and Leonard Adleman in the 1970s (thus the name “RSA”). The approach is based on the assumption that factoring a 2,048-bit integer (a number with 617 digits) is too difficult for a computer to complete in a reasonable amount of time.
That theory was turned on its head in 1994, when Shor, then at Bell Labs, introduced a method that demonstrated that a quantum computer could factor quickly enough to break RSA cryptography.
“It was a tipping point. However, in 1994, no one knew how to construct a sufficiently massive quantum computer. And we’re still a long way from there. “Some people question whether they will ever be built,” says Vaikuntanathan.
Shor’s algorithm is predicted to require approximately 20 million qubits on a quantum computer. Right now, the largest quantum computers have approximately 1,100 qubits.
A quantum computer employs quantum circuits to do computations in the same way that a classical computer would. Each quantum circuit consists of a series of operations known as quantum gates. These quantum gates usequbits, the smallest building blocks of a quantum computer, to conduct calculations.
However, quantum gates generate noise, so having fewer gates might increase a machine’s performance. Researchers have been working to improve Shor’s algorithm so that it can operate on a smaller circuit with fewer quantum gates.
That is exactly what Regev accomplished with the circuit he presented a year ago.
“That was big news because it was the first real improvement to Shor’s circuit from 1994,” he explains.
Shor proposed a quantum circuit whose size is proportional to the square of the integer being factored. That is, if one were to factor a 2,048-bit integer, the circuit would require millions of gates.
Regev’s circuit requires far fewer quantum gates but many more qubits to provide adequate memory. This introduces a new problem.
“In some ways, qubits differ from one another. If you do not maintain them, they will degrade over time. Vaikuntanathan adds that the goal is to keep as few qubits as possible.
He heard Regev discuss his findings at a workshop last August. Regev ended his discussion with a question: Could someone modify his circuit such that it requires fewer qubits?. Vaikuntanathan and Ragavan took up the question.
Quantum Ping-Pong
To factor a really high number, a quantum circuit would have to run many times, executing operations that need computing power, such as 2 to the power of 100.
However, computing such enormous powers is expensive and difficult for a quantum computer, which can only do reversible operations. Squaring a number is not a reversible process; hence, more quantum memory is required to compute the next square.
The MIT researchers discovered a novel approach to computing exponents using a series of Fibonacci numbers that use simple, reversible multiplication rather than squaring. Their approach requires only two quantum memory units to compute 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,” he says.
They also addressed the issue of error correction. According to Vaikuntanathan, the circuits suggested by Shor and Regev require that all quantum operations be exact for their algorithm to execute. However, error-free quantum gates would be impractical on a real machine.
They solved this difficulty by utilizing a mechanism that filters out corrupt results and only processes the valid ones.
The ultimate result is a circuit with much higher memory efficiency. Furthermore, their error correction technique would make the program easier to deploy.
“The authors address the two most significant bottlenecks in the previous quantum factoring technique. Although not yet feasible, their work pushes quantum factoring methods closer to reality,” says Regev.
The researchers intend to improve their algorithm’s efficiency and eventually use it to test factoring on an actual quantum circuit.
“The elephant in the room following this work is whether it genuinely brings us closer to defeating RSA cryptography. That is not obvious yet; these enhancements are currently only effective when the numbers are significantly greater than 2,048 bits. Can we improve this approach to make it more viable than Shor’s, even for 2,048-bit integers?” says Ragavan.
