In an age where secure communication is paramount, a new breakthrough in quantum computing is poised to challenge the very foundation of cryptography. Traditional encryption methods, which rely on the complexity of factoring large numbers, may soon become obsolete as quantum computers demonstrate their potential to crack these codes at unprecedented speeds.
The Power of Quantum Factorization
The RSA encryption scheme, a widely-used method for secure data transmission, hinges on the idea that factoring a large number, such as a 2048-bit integer, is computationally infeasible for classical computers within a reasonable time frame. However, in 1994, Peter Shor, now a professor at the Massachusetts Institute of Technology (MIT), proposed a quantum algorithm that could efficiently factorize large numbers, potentially breaking RSA encryption.
Despite significant progress over the past three decades, scientists have yet to build a quantum computer powerful enough to run Shor’s algorithm. Some researchers are focused on constructing larger quantum computers, while others are working to improve Shor’s algorithm to make it feasible on smaller quantum circuits.
A Compromise Algorithm
Enter Oded Regev, a computer scientist at New York University, who last year proposed a theoretical improvement to Shor’s algorithm. Regev’s algorithm is faster but requires more memory. Building on these findings, researchers at MIT have proposed a new algorithm that combines the speed of Regev’s algorithm with the memory efficiency of Shor’s algorithm. This new method is as fast as Regev’s algorithm but requires fewer quantum components, known as qubits, and is more tolerant to quantum noise, making it potentially easier to implement in practice.
The new algorithm could provide guidance for developing new encryption methods that are resistant to quantum computer attacks. If large-scale quantum computers are eventually built, then factoring algorithms will become ineffective, and we must find other encryption methods. But is this really a threat? Can we make quantum factoring algorithms practical? Our research may have brought us a step closer to practicality, said Vinod Vaikuntanathan, a professor of engineering at the Ford Foundation and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT.
The lead author of the paper is Seyoon Ragavan, a graduate student in MIT’s Department of Electrical Engineering and Computer Science. The research is set to be presented at the International Cryptography Conference in 2024.
Breaking Cryptography
To securely transmit information over the internet, email clients and messaging apps often rely on RSA encryption, named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman of MIT in the 1970s. The system is based on the premise that factoring a 2048-bit integer is too difficult for computers to accomplish in a reasonable time. However, Shor’s algorithm, proposed in 1994, demonstrated that a quantum computer could factorize numbers quickly, potentially breaking RSA encryption.
That was a turning point. But in 1994, no one knew how to build a large enough quantum computer. And we are still far from achieving that goal. Some people even doubt whether they will ever be built, said Vaikuntanathan.
It is estimated that a quantum computer would need about 20 million qubits to run Shor’s algorithm. Currently, the largest quantum computers have only about 1100 qubits.
Quantum computers perform calculations using quantum circuits, similar to how classical computers use classical circuits. Each quantum circuit is composed of a series of operations called quantum gates that use qubits for computation. However, quantum gates introduce noise, so reducing the number of quantum gates can improve machine performance. Researchers have been working to improve Shor’s algorithm to make it run on smaller circuits with fewer quantum gates.
This was the innovation Regev proposed a year ago.
This was big news because it was the first real improvement since Shor proposed his circuit in 1994, said Vaikuntanathan.
Shor’s original quantum circuit size is proportional to the square of the number being factored. This means that to factor a 2048-bit integer, the circuit would require millions of quantum gates.
Regev’s circuit requires significantly fewer quantum gates but needs more qubits for memory, which poses a new challenge.
Some types of qubits are like apples or oranges. If you keep them for too long, they decay. You want to minimize the number of qubits you need to keep, explained Vaikuntanathan.
He heard Regev’s lecture at a symposium last August, where Regev posed a challenge: Could anyone improve his circuit to reduce the number of qubits required? Vaikuntanathan and Ragavan accepted the challenge.
Quantum Ping Pong
To factor a very large number, a quantum circuit needs to run multiple times, performing operations involving powers of calculations, such as 2 to the power of 100. However, calculating such large powers on a quantum computer is costly and
Views: 0