Rebuttal to the Chinese team! Fujitsu Quantum computers still hard to crack RSA

A new study recently conducted by Fujitsu, a global computer and chip manufacturer, on its 39-quantum-bit quantum simulator [1] suggests that quantum computers will remain difficult to crack RSA ciphers for years to come.

Successfully cracking RSA would require about 104 days of fault-tolerant quantum computing

Fujitsu researchers report that using the Shor algorithm, a fault-tolerant quantum computer with a size of about 10,000 quantum bits and 2.23 trillion quantum gates would be required to crack RSA: significantly more than the most advanced quantum computers in the world today. The researchers further estimate that about 104 days of fault-tolerant quantum computing would be required to successfully crack RSA.

Fujitsu's supercomputer

"Our research shows that quantum computing does not pose a direct threat to existing encryption methods. However, we cannot be complacent." Fujitsu's senior director of data and security research Tetsuya Izu said, "The world needs to start preparing now because one day quantum computers could fundamentally change the way we think about security."

The latest work on Shor's algorithm was conducted on Fujitsu's Quantum Simulator; the system utilizes technology developed for Japan's "Tomigatake" supercomputer (ranked second on the latest Top500 list) and specialized quantum bit processing technology. Fujitsu reports, "Using a clustered system based on Fujitsu's 512-node supercomputer PRIMEHPC FX700 hardware - with an A64FX CPU - and newly developed technology to automatically and efficiently rearrange the state information of quantum bits, Fujitsu achieved more than 100 times the number of quantum bits in the 64-node system. of the system achieved a speedup of more than 100 times and was able to factorize N=253 in 463 seconds, which previously took 16 hours."

Simulation details: quantitatively proving that the RSA cryptosystem is temporarily secure against the Shor algorithm

Within the scope of the experiment, Fujitsu implemented a generic program using Shor's algorithm on a quantum simulator to generate a quantum circuit that decomposes the input complex numbers into prime factors. As a result, Fujitsu successfully factorized 96 RSA-type integers (the product of two different odd numbers) from N=15 to N=511, and confirmed that the general-purpose program could generate the correct quantum circuit.

By using the above generic procedure, Fujitsu further generated quantum circuits for factorization of several complex numbers from 10 bits to 25 bits, and estimated the resources of quantum circuits required for factorization of 2048-bit complex numbers based on the calculated resources.

As a result, Fujitsu found that about 10,000 quantum bits, 2.23 trillion quantum gates, and a quantum circuit with a depth of 1.80 trillion are required to factorize a 2048-bit composite number. This is equivalent to up to 104 days of computation using a fault-tolerant quantum computer. Since a quantum computer capable of stable operation at such a large scale will not be realized in the near future, Fujitsu's test quantitatively demonstrates that the RSA cryptosystem is temporarily secure against the Shor algorithm.

How soon will quantum computers crack RSA?

Predictably, developing measures to prevent quantum computers from breaking modern encryption methods - most typically RSA ciphers - is an area of intense research and hot debate within the quantum community. Today, the number of quantum bits around the world is climbing rapidly: IBM debuted a 443-quantum-bit QPU in late 2023 and plans to launch a 1,100-quantum-bit system in 2023.

It is now believed that Shor's algorithm will be able to quickly decrypt today's factor-based encryption schemes, including RSA, when sufficiently large fault-tolerant quantum computers become available. in the summer of 2023, the National Institute of Technology and Standards (NIST) released the first set of new algorithms to replace the current RSA approach.

Debate is swirling about how long NISQ computers or non-gate based quantum annealing methods will be able to decrypt RSA data.

On Dec. 22, 2022, researchers in China reported a breakthrough in developing a method capable of decrypting RSA-2048: the method requires only 372 quantum bits.

They write, "(We) report a generalized quantum algorithm for integer decomposition by combining classical lattice reduction with the Quantum Approximation Optimization Algorithm (QAOA). The number of quantum bits required is O(logN/logN), which is sublinear to the bit length of the integer N, making it the most quantum bit-saving factorization algorithm to date. We experimentally demonstrate the algorithm by factorizing integers of up to 48 bits with 10 superconducting quantum bits, which is the largest integer to be factorized on a quantum device. We estimate that challenging RSA-2048 using our algorithm requires a quantum circuit with 372 physical quantum bits and thousands of depths. Our research shows great promise in accelerating the application of currently noisy quantum computers and paves the way for large integer factors with realistic cryptographic implications."

Fujitsu: an active participant in quantum computing

Recently, Fujitsu announced plans to develop and deploy a 64-quantum-bit quantum computer with Riken in 2023. The new quantum computer will be based on superconducting quantum bits: an approach similar to that of IBM, Rigetti and Google. So far, few details about the new computer have been disclosed.

The company launched a quantum simulator in 2022 and plans to increase its capacity to 40 quantum bits in the first quarter of 2023. in 2018, Fujitsu launched its digital annealer service: "Using digital circuit designs inspired by quantum phenomena, digital annealers focus on solving complex combinatorial optimization problems quickly, without the usual quantum computing methods associated with the additional complexity and cost normally associated with quantum computing methods."

In the fall of 2022, Fujitsu entered into an agreement with Toyota to utilize digital annealers in automotive production applications.

In November 2022, Fujitsu announced the development of hybrid quantum/HPC computing technology to optimize workload selection for customers. "The new AI-based software, a pioneer in future computer workload mediation technology, automatically selects from different next-generation computing platforms to provide the best solution to customers' problems based on parameters including computation time, computation accuracy and cost."

Recently, Fujitsu is rapidly becoming a substantial player in quantum technology.

Reference link：

https://www.hpcwire.com/2023/01/23/fujitsu-study-says-quantum-decryption-threat-still-distant/