Fujitsu conducted the trials in January 2023 using its 39-qubit quantum simulator to assess how difficult it would be for quantum computers to crack existing RSA cryptography, using a Shor's algorithm (2) to determine the resources necessary to perform such a task. Fujitsu researchers discovered that a fault-tolerant quantum computer (3) with a scale of approximately 10,000 qubits and 2.23 trillion quantum gates would be required to crack RSA -- well beyond the capabilities of even the most advanced quantum computers in the world today. Researchers further estimated that it would be necessary to conduct fault-tolerant quantum computation for about 104 days to successfully crack RSA .
While the research reveals that the limitations of present quantum computing technology preclude the possibility of this threat in the short term, Fujitsu will continue to proactively evaluate the potential impact of increasingly powerful quantum computers on cryptography security, as well as the eventual need for quantum-resistant cryptography. Dr. Tetsuya Izu, Senior Director of Data & Security Research at Fujitsu Limited and Global Fujitsu Distinguished Engineer, commented: "Our research demonstrates that quantum computing doesn't pose an immediate threat to existing cryptographic methods. We cannot be complacent either, however. The world needs to begin preparing now for the possibility that one day quantum computers could fundamentally transform the way we think about security."
With plans to boost performance of its quantum simulator to 40 qubits by the first quarter of fiscal 2023, and recently revealed plans to build a 64 qubit superconducting quantum computer within fiscal 2023 with the cooperation of RIKEN, Fujitsu remains at the vanguard of research and development in this critical field.
Fujitsu will present parts of the results at the 2023 Symposium on Cryptography and Information Security (SCIS 2023) to be held from Tuesday, January 24 to Friday, January 27, 2023, in Kitakyushu City, Fukuoka Prefecture, Japan and online.
Background
RSA, a widely used standard cryptographic algorithm, represents a secure method to guarantee the confidentiality and integrity of data for digital interactions including the transmission and reception of credit card information in online shopping and the exchange of messages in SNS.
The RSA cryptosystem is based on the fact that factoring a large integer is difficult. As current computers can factor composite numbers up to 829 bits (4), experts believe that an RSA cryptosystem with 2,048-bit key length (5) will remain secure with regard to future improvements in computing capabilities.
Despite this, concerns remain that once available, fault-tolerant quantum computers will be able to factor even huge composite numbers, and thus pose a potential threat to RSA cryptography. This means that one day, it will become necessary to shift from the RSA cryptosystem to alternative technologies such as post-quantum cryptography. Due to a lack of respective trials, estimating the computational resources necessary for quantum computers to actually perform integer factorization of 2,048 bits composite numbers remains a difficult task, and the timing of transition to alternative technologies remains unclear.
About the evaluation of the safety of RSA encryption using a quantum simulator
To address these issues, Fujitsu conducted factorization trials to confirm the safety of the RSA cryptosystem using Fujitsu's 39 qubit quantum simulator developed in September 2022.
Within the trials, Fujitsu implemented a general-purpose program using Shor's algorithm on a quantum simulator to generate a quantum circuit that factors the input composite number into prime factors. As a result, Fujitsu succeeded in factoring 96 RSA-type integers (a product of two different odd primes) from N = 15 to N = 511, and confirmed that the general-purpose program can generate correct quantum circuits.
By using the above general purpose program, Fujitsu further generated quantum circuits that factor several composite numbers from 10 bits to 25 bits, and estimated the required resources of the quantum circuits necessary for factoring 2,048 bits composite numbers from the calculated resources. As a result, Fujitsu found that approximately 10,000 qubits, 2.23 trillion quantum gates, and a quantum circuit with a depth (6) of 1.80 trillion were required to factor a composite number of 2,048 bits. This equates to a 104-day long calculation using a fault-tolerant quantum computer. As a quantum computer that can operate stably and at such a large scale will not be realized in the short term, Fujitsu's tests quantitatively proved that the RSA cryptosystem is safe against the Shor's algorithm for the time being.
Within the trials, Fujitsu utilized its quantum simulator leveraging the high speed computing power of the CPU "A64FX" of the supercomputer "Fugaku" (7) and Fujitsu's massively parallel computing technology. Using a cluster system based on Fujitsu's 512 node supercomputer "FUJITSU Supercomputer PRIMEHPC FX700" hardware, which features the A64FX CPU, and a newly developed technology that automatically and efficiently rearranges the state information of quantum bits, Fujitsu achieved a speed increase of more than 100 times that of a system without rearrangement in 64 nodes, and was able to perform factoring of N = 253 in 463 seconds, which previously took 16 hours.
(1) RSA cryptosystem :
Cryptographic system named for its developers Rivest, Shamir, and Adleman, that uses a private key for decryption and a public key for encryption. Even if the encryption key is made public, only those with the private key can correctly receive the information due to the difficulty of factoring.
(2) Shor's algorithm:
A quantum algorithm developed in 1994 by Peter Shore, a theoretical computer scientist and mathematician in the United States, that can perform integer factorization at high speed.
(3) fault-tolerant quantum computer :
A quantum computer that is not limited by quantum bit noise or the upper limit of the number of quantum gates. It is used in conducting theoretical analysis.
(4) Current computers can factor composite numbers up to 829 bit :
Source: [Cado-nfs-discuss] Factorization of RSA-250 (archive.org)
(5) Key length :
Length of a key in the cryptosystem. In RSA cryptosystem, the key length is the bit length of the composite number used as the decryption key and the encryption key. When using RSA cryptosystem, it is recommended to set the key length to 2,048 bits or more.
(6) Depth:
The number of steps required to perform quantum computation in a quantum circuit.
(7) Supercomputer "Fugaku":
A computer jointly developed by RIKEN and Fujitsu as a successor to the K computer. Full operation started on March, 2021. From June 2020 to November 2021, it ranked first in 4 categories in the supercomputer rankings for 4 consecutive terms.
While the research reveals that the limitations of present quantum computing technology preclude the possibility of this threat in the short term, Fujitsu will continue to proactively evaluate the potential impact of increasingly powerful quantum computers on cryptography security, as well as the eventual need for quantum-resistant cryptography. Dr. Tetsuya Izu, Senior Director of Data & Security Research at Fujitsu Limited and Global Fujitsu Distinguished Engineer, commented: "Our research demonstrates that quantum computing doesn't pose an immediate threat to existing cryptographic methods. We cannot be complacent either, however. The world needs to begin preparing now for the possibility that one day quantum computers could fundamentally transform the way we think about security."
With plans to boost performance of its quantum simulator to 40 qubits by the first quarter of fiscal 2023, and recently revealed plans to build a 64 qubit superconducting quantum computer within fiscal 2023 with the cooperation of RIKEN, Fujitsu remains at the vanguard of research and development in this critical field.
Fujitsu will present parts of the results at the 2023 Symposium on Cryptography and Information Security (SCIS 2023) to be held from Tuesday, January 24 to Friday, January 27, 2023, in Kitakyushu City, Fukuoka Prefecture, Japan and online.
Background
RSA, a widely used standard cryptographic algorithm, represents a secure method to guarantee the confidentiality and integrity of data for digital interactions including the transmission and reception of credit card information in online shopping and the exchange of messages in SNS.
The RSA cryptosystem is based on the fact that factoring a large integer is difficult. As current computers can factor composite numbers up to 829 bits (4), experts believe that an RSA cryptosystem with 2,048-bit key length (5) will remain secure with regard to future improvements in computing capabilities.
Despite this, concerns remain that once available, fault-tolerant quantum computers will be able to factor even huge composite numbers, and thus pose a potential threat to RSA cryptography. This means that one day, it will become necessary to shift from the RSA cryptosystem to alternative technologies such as post-quantum cryptography. Due to a lack of respective trials, estimating the computational resources necessary for quantum computers to actually perform integer factorization of 2,048 bits composite numbers remains a difficult task, and the timing of transition to alternative technologies remains unclear.
About the evaluation of the safety of RSA encryption using a quantum simulator
To address these issues, Fujitsu conducted factorization trials to confirm the safety of the RSA cryptosystem using Fujitsu's 39 qubit quantum simulator developed in September 2022.
Within the trials, Fujitsu implemented a general-purpose program using Shor's algorithm on a quantum simulator to generate a quantum circuit that factors the input composite number into prime factors. As a result, Fujitsu succeeded in factoring 96 RSA-type integers (a product of two different odd primes) from N = 15 to N = 511, and confirmed that the general-purpose program can generate correct quantum circuits.
By using the above general purpose program, Fujitsu further generated quantum circuits that factor several composite numbers from 10 bits to 25 bits, and estimated the required resources of the quantum circuits necessary for factoring 2,048 bits composite numbers from the calculated resources. As a result, Fujitsu found that approximately 10,000 qubits, 2.23 trillion quantum gates, and a quantum circuit with a depth (6) of 1.80 trillion were required to factor a composite number of 2,048 bits. This equates to a 104-day long calculation using a fault-tolerant quantum computer. As a quantum computer that can operate stably and at such a large scale will not be realized in the short term, Fujitsu's tests quantitatively proved that the RSA cryptosystem is safe against the Shor's algorithm for the time being.
Within the trials, Fujitsu utilized its quantum simulator leveraging the high speed computing power of the CPU "A64FX" of the supercomputer "Fugaku" (7) and Fujitsu's massively parallel computing technology. Using a cluster system based on Fujitsu's 512 node supercomputer "FUJITSU Supercomputer PRIMEHPC FX700" hardware, which features the A64FX CPU, and a newly developed technology that automatically and efficiently rearranges the state information of quantum bits, Fujitsu achieved a speed increase of more than 100 times that of a system without rearrangement in 64 nodes, and was able to perform factoring of N = 253 in 463 seconds, which previously took 16 hours.
(1) RSA cryptosystem :
Cryptographic system named for its developers Rivest, Shamir, and Adleman, that uses a private key for decryption and a public key for encryption. Even if the encryption key is made public, only those with the private key can correctly receive the information due to the difficulty of factoring.
(2) Shor's algorithm:
A quantum algorithm developed in 1994 by Peter Shore, a theoretical computer scientist and mathematician in the United States, that can perform integer factorization at high speed.
(3) fault-tolerant quantum computer :
A quantum computer that is not limited by quantum bit noise or the upper limit of the number of quantum gates. It is used in conducting theoretical analysis.
(4) Current computers can factor composite numbers up to 829 bit :
Source: [Cado-nfs-discuss] Factorization of RSA-250 (archive.org)
(5) Key length :
Length of a key in the cryptosystem. In RSA cryptosystem, the key length is the bit length of the composite number used as the decryption key and the encryption key. When using RSA cryptosystem, it is recommended to set the key length to 2,048 bits or more.
(6) Depth:
The number of steps required to perform quantum computation in a quantum circuit.
(7) Supercomputer "Fugaku":
A computer jointly developed by RIKEN and Fujitsu as a successor to the K computer. Full operation started on March, 2021. From June 2020 to November 2021, it ranked first in 4 categories in the supercomputer rankings for 4 consecutive terms.
IonQ Achieves Industry Leading Performance on Next Generation Barium Qubits