Fear not: RSA encryption won’t fall to quantum computing anytime soon

Abstract futuristic electronic circuit board hi-tech background

Three weeks ago, panic swept through some corners of the security world after researchers discovered a breakthrough that finally put cracking the widely used RSA encryption scheme within reach using quantum computing.

Scientists and cryptographers have known for two decades that a factorization method known as Shor’s algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. That’s because the secret primes that support the security of an RSA key are easy to calculate using Shor’s algorithm. Factoring the same prime numbers using classical computing takes billions of years.

The only thing holding this doomsday scenario back is the massive amount of computing resources required for Shor’s algorithm to crack RSA keys of sufficient size. The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in overlay. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. But while a classical binary bit can represent only a single binary value such as 0 or 1, a qubit is represented by a superposition of multiple possible states.)

The paper, published three weeks ago by a team of researchers in China, reported finding a factorization method that could break a 2,048-bit RSA key using a quantum system with only 372 qubits when run using thousands of operation steps. The finding, if true, would have meant that the fall of RSA encryption to quantum computing could come much sooner than most people believed.

The demise of RSA has been greatly exaggerated

At the Enigma 2023 Conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that RSA’s demise had been greatly exaggerated. Currently, he said, quantum computing has few, if any, practical applications.

“In the near term, quantum computers are good for one thing, and that is publishing papers in prestigious journals,” Garfinkel, co-author with Chris Hoofnagle of the 2021 book. Law and Politics for the Quantum Age, told the audience. “The second thing they’re pretty good at, but we don’t know for how long, is they’re pretty good at getting financing.”

Even when quantum computing becomes advanced enough to provide useful applications, the applications are likely for simulating physics and chemistry, and performing computational optimizations that do not work well with classical computing. Garfinkel said the lack of useful applications in the foreseeable future could usher in a “quantum winter,” similar to the multiple rounds of artificial intelligence winters before AI finally took off.

The problem with the paper published earlier this month was its reliance on Shnorr’s algorithm (not to be confused with Shor’s algorithm), which was developed in 1994. Schnorr’s algorithm is a classical computation based on grids, which are mathematical concepts of lines that form lines. a geometric structure that can encode and decode messages. The authors who came up with Schnorr’s algorithm said it could improve the use of the heuristic quantum optimization method called QAOA.

In a short time, a multitude of researchers pointed out fatal flaws in Shnorr’s algorithm that all but disproved it. Specifically, critics said that there was no evidence supporting the authors’ claims of Schnorr’s algorithm achieving polynomial time, as opposed to the exponential time achieved with classical algorithms.

The research paper from three weeks ago seemed to take Shor’s algorithm at face value. Even when it is supposedly improved using QAOA—something for which there is currently no support—it is questionable whether combining it with Shor’s algorithm gives any performance boost.

“This is one of the most actively misleading articles about quantum computing that I’ve seen in 25 years, and I’ve seen … a lot,” Scott Aaronson, a computer scientist at the University of Texas at Austin and director of its Quantum. Information center, wrote. “Having said that, this is actually not the first time I’ve come across the strange idea that the exponential quantum speedup for integer factorization, which we know about from Shor’s algorithm, should somehow “rub” into a quantum optimization heuristic that incorporates none. of the real insights of Shor’s algorithm, as if by sympathetic magic.”


Also Read :  Looking to buy a premium phone? Here are options from Apple, Samsung and Google

Leave a Reply

Your email address will not be published.

Related Articles

Back to top button