Three weeks ago, parts of the security world panicked after researchers discovered a breakthrough that puts cracks in the widely-used RSA encryption method within reach using quantum computing. I fell.
Scientists and cryptographers have known for 20 years that a factorization method known as Scholl’s algorithm theoretically allows a quantum computer with sufficient resources to break RSA. This is because the secret prime numbers that underpin the security of RSA keys can be easily computed using Shor’s algorithm. It would take billions of years to compute the same prime number using classical computing.
The only thing holding back this doomsday scenario is the massive amount of computing resources Shor’s algorithm requires to crack RSA keys of sufficient size. Current estimates are that a quantum computer with enormous resources would be required to crack a 1,024-bit or 2,048-bit RSA key. Specifically, these resources are about 20 million qubits, of which about 8 hours run in superposition. (A qubit is the basic unit of quantum computing and is similar to a binary bit in classical computing. However, the reason that a conventional binary bit can only represent a single binary value such as 0 or 1 is that A qubit, on the other hand, is represented by a superposition of multiple possible values.)
The paper, published three weeks ago by a team of Chinese researchers, uses a quantum system of just 372 qubits to break a 2,048-bit RSA key when operating using thousands of manipulation steps. He reported that he discovered a factorization method that can If this discovery were true, it would have meant that the collapse of his RSA cryptography into quantum computing could come much sooner than most people believe.
RSA’s demise is greatly exaggerated
At the Enigma 2023 conference in Santa Clara, Calif., on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that the demise of RSA was greatly exaggerated. For the time being, there are few, if any, practical applications of quantum computing, he said.
“In the short term, quantum computers will help us do one thing, and that is publication in prestigious journals,” says Garfinkel, co-author of the 2021 book with Chris Hoofnagle. Law and Policy in the Quantum Agesaid to the audience. “The second thing they’re pretty good at, I don’t know how long it will last, but they’re pretty good at fundraising.”
Even if quantum computing becomes advanced enough to offer useful applications, it could simulate physics and chemistry and perform computer optimizations that don’t work well with classical computing. I have. Garfinkel believes that just as there were many artificial intelligence winters before AI finally took off, the lack of useful applications in the foreseeable future could result in a ‘quantum winter’. said.
The problem with the paper, published earlier this month, is that it relied on Schnorr’s algorithm (not to be confused with Shor’s algorithm), which was developed in 1994. Constructive encryption and cryptanalysis. The authors who devised Schnorr’s algorithm say it can be enhanced using a heuristic quantum optimization technique called QAOA.
In a short period of time, many researchers pointed out the fatal flaw in Schnorr’s algorithm and nearly proved it right. Specifically, critics said there was no evidence to support the authors’ claim that Schnorr’s algorithm achieves polynomial time, as opposed to the exponential time achieved by classical algorithms.
A research paper three weeks ago seemed to take Shor’s algorithm at face value. Even if it seems to be enhanced using QAOA (which is not currently supported), I doubt if it will improve performance.
Scott Aaronson, computer scientist and director of quantum computing at the University of Texas at Austin, said: Information center, wrote. “That said, it’s strange that the exponential quantum speedup of integer factorization known from Shore’s algorithm should somehow be ‘rubbed’ into a quantum optimization heuristic that embodies nothing.” This isn’t the first time I’ve encountered such thoughts. Of the practical insight of Scholl’s algorithm, as if by sympathetic magic. ”
