The following is translated from the original:
The email you sent recently may have been encrypted using a validated method that relies on the idea that even the fastest computers cannot effectively factor huge numbers into factors.
On the other hand, quantum computers are expected to quickly crack complex cryptographic systems that classic computers may never be able to crack. This commitment is based on the quantum factorization algorithm proposed in 1994 by Peter Shor (now a professor at the Massachusetts Institute of Technology).
Although researchers have made great progress over the past 30 years, scientists have yet to build a quantum computer powerful enough to run Shor’s algorithm.
While some researchers are working on building larger quantum computers, others have been trying to improve Shor’s algorithm so that it can run on smaller quantum circuits. About a year ago, New York University computer scientist Oded Regev proposed a major theoretical improvement. His algorithm can run faster, but the circuit requires more memory.
Based on these results, MIT researchers have proposed a best of both worlds, combining the speed of Regev’s algorithm with the memory efficiency of Shor’s algorithm. This new algorithm is as fast as Regev’s algorithm, requires fewer quantum building blocks (called qubits), and has a higher tolerance for quantum noise, which may make it more feasible in practice.
In the long run, this new algorithm could inform the development of new encryption methods that can withstand the password cracking capabilities of quantum computers.
“If large-scale quantum computers are built, factorization is done and we have to find something else to use for cryptography.” But how real is this threat? Can we make quantum factorization practical?
“Our work may get us closer to actual realization,” said Vinod Vaikuntanathan, professor of engineering at the Ford Foundation, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) and senior author of the paper describing the algorithm.。
The lead author of the paper is Seyoon Ragavan, a graduate student in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. The research was published at the 2024 International Conference on Cryptography (Crypto 2024).
cryptanalysis
To securely transmit messages over the network, service providers such as email clients and messaging applications often rely on RSA, an encryption scheme invented in the 1970s by MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman (hence the name “RSA”). The system is based on the idea that factorizing a 2,048-bit integer (a number with 617 bits) is too difficult for a computer to complete in a reasonable time.
In 1994, Shor, then working at Bell Labs, introduced an algorithm that proved that a quantum computer could decompose RSA ciphers quickly enough, and the idea was completely overturned.
“That was a turning point. But in 1994, no one knew how to build a quantum computer big enough. And we’re still far away from there. Some people wonder if they will be built,”Vaikuntanathan said.
It is estimated that a quantum computer requires approximately 20 million qubits to run Shor’s algorithm. Currently, the largest quantum computers have about 1,100 qubits.
Quantum computers use quantum circuits to perform calculations, just as classic computers use classic circuits. Each quantum circuit consists of a series of operations called quantum gates. These quantum gates use qubits (the smallest building block of a quantum computer) to perform calculations.
But quantum gates introduce noise, so reducing quantum gates improves machine performance. Researchers have been working to enhance Shor’s algorithm so that it can run on smaller circuits with fewer quantum gates.
This is exactly what Regev did with the circuit he proposed a year ago.
“This is big news because this is the first real improvement to the Shor circuit since 1994,” Vaikuntanathan said.
The size of the quantum circuit proposed by Shore is proportional to the square of the number being decomposed. This means that if you want to decompose a 2,048-bit integer, the circuit will require millions of gates.
Regev’s circuit requires significantly fewer quantum gates, but it requires more qubits to provide enough memory. This raises a new question.
“In a sense, certain types of qubits are like apples or oranges. If you keep them, they will decay over time. You want to minimize the number of qubits that need to be retained,”Vaikuntanathan explained.
Last August, he heard Regev talk about his research results at a seminar. At the end of his speech, Regev asked a question: Can anyone improve his circuit so that it requires fewer qubits? Vaikuntanathan and Ragavan answered the question.
If you want to learn more, you can click on the link below the video.
Thank you for watching this video. If you like it, please subscribe and like it. thank
Original text:https://techxplore.com/news/2024-08-smaller-noise-tolerant-quantum-factoring.html
More information: Space-Efficient and Noise-Robust Quantum Factoring: eprint.iacr.org/2023/1501.pdf
More information: Space-saving and noise-resistant quantum decomposition: eprint.iacr.org/2023/1501.pdf
Oil tubing: