Cryptography Research in Anticipation of the Advent of the Quantum-computer Era

1. NTT’s results and trends in cryptography research

NTT Social Informatics Laboratories has been engaged in the research and development (R&D) of cryptographic technology for more than 40 years and has been producing world-class results. Our major achievements include the digital signature scheme ESIGN (Efficient Digital Signature) (1990), key encapsulation mechanism PSEC-KEM (Provably Secure Elliptic Curve encryption with Key Encapsulation Mechanism) (1999), symmetric block cipher Camellia (2000) jointly developed by NTT and Mitsubishi Electric, and message recovery digital signature scheme ECAOS (Elliptic Curve Abe–Okamoto–Suzuki signature) (2008). In addition to these encryption and digital-signature methods, we have also produced many results from research on security analysis and attack methods. Every year for the last ten years or so, our research results have been included in CRYPTO/Eurocrypt/Asiacrypt, prestigious conferences organized by the International Association for Cryptologic Research (IACR), and some have attracted much attention as the world’s first epoch-making results.

We have also worked extensively on social implementation of these research results. For example, the R&D of attribute-based encryption, which is an advanced cryptography, has progressed and made into a library. Attribute-based encryption is a cryptographic technique that can control data access on the basis of user attributes. Similarly, we have developed a multi-party computation technology using homomorphic encryption, which is an advanced cryptography, and has been commercialized through NTT Group companies. A multi-party computation is a technology that can compute encrypted data and has been adopted as an ISO (International Organization for Standardization) international standard [1].

In cryptography, there are basic technologies such as symmetric-key encryption, key exchange, public-key encryption, hash functions, digital signatures, attribute-based encryption, and a multi-party computation. Researchers worldwide, including those at NTT laboratories, have been working for many years to advance these basic technologies and establish new ones.

Because these basic technologies had been established, new technologies, such as ESIGN, which we mentioned at the beginning, and the social infrastructure that is widely used today, appeared. For example, public-key infrastructure (PKI) has been implemented by using public-key encryption and digital signatures in response to the advent of the Internet, which has made communication with a large number of unspecified people mainstream. The appearance of Internet of Things (IoT) devices and embedded devices along with the spread of high-speed wireless communications and cloud computing has given birth to a new technology called lightweight cryptography that reduces the amount of computation, power consumption, and memory usage. Some of the new technologies are positioned as basic technologies and are under further research (see Fig. 1).

Fig. 1. Basic cryptographic technologies as a foundation for new technologies and social infrastructure in response to environmental changes.

To achieve a safe and secure society by providing new technologies and social infrastructure at the appropriate time in response to various changes in the environment, we believe that continuous R&D on basic cryptographic technologies is very important. We are thus conducting R&D on a daily basis.

Although the R&D results described thus far are based on the premise of using modern cryptography^*1 on a classical computer^*2, we are currently conducting extensive R&D in anticipation of a major environmental change, namely, the advent of the quantum-computer era.

R&D on quantum computers^*3 has progressed rapidly, and practical quantum computers will appear in the 2030s. Since an attacker will be assumed able to acquire a quantum computer, which is a specific example of environmental change, researchers worldwide, including us, are conducting R&D on post-quantum cryptography (PQC)^*4 (Fig. 1).

As the practical application of quantum computers is imminent, the movement to replace modern cryptography with PQC has become active.

People will be able to use quantum computers on a daily basis. Looking ahead to such a future, we are also conducting research to create new cryptographic functions that were previously impossible by combining cryptographic theory and quantum information processing (Fig. 1).

2. R&D of PQC

In 1994, the American mathematician Peter Shore devised a quantum algorithm that can solve the prime factorization problem and discrete logarithm problem that form the basis of modern cryptography. This showed the possibility that public-key encryption can be decrypted in realistic time using a quantum computer. In response to this, research on PQC, which is difficult to crack even with the computing power of a quantum computer, began in earnest in the 2010s.

National Institute of Standards and Technology (NIST) then started the standardization (competition) of PQC in 2016 on the basis of the designation as a priority implementation item of the National Cyber Strategy. Due to the large number of applications, the standardization process has been carried out in a round system in which candidates are narrowed down in stages. Thus far, standardization has been decided on two methods for encryption and key exchange (ML-KEM (Module-Lattice Key Encapsulation Mechanism) and HQC (Hamming Quasi-Cyclic)) and three methods for a digital signature (ML-DSA (Module-Lattice-Based Digital Signature Algorithm), SLH-DSA (Stateless Hash-Based Digital Signature Algorithm), and FN-DSA (Fast Fourier Transform over NTRU-Lattice-Based Digital Signature Algorithm)) (Fig. 2). We also applied for NTRU (N-th degree Truncated polynomial Ring Units), an encryption and key-exchange method based on the lattice problem. NTRU made it to the third round, but did not achieve standardization. However, NTRU has an advantage in processing time over standardized methods (ML-KEM, formerly CRYSTALS-Kyber), and we are still working on standardization in the Internet Engineering Task Force.

Fig. 2. NIST’s standardization process for PQC and signatures.

In September 2022, NIST launched an additional call for proposals for post-quantum digital signatures, which attracted 40 proposals worldwide. We proposed QR-UOV (Quotient Ring Unbalanced Oil and Vinegar), which is based on multivariable polynomial problems, in collaboration with the University of Tokyo, Kyushu University, and Nagasaki Prefectural University. In October 2024, 14 methods were announced to advance to the second round, and QR-UOV was among them [2] (Fig. 3). We are currently working on improving specifications, proving safety, and improving processing performance at the time of implementation in both software and hardware.

Fig. 3. Candidates for NIST’s additional post-quantum signature.

NTT has been investigating PQC on the basis of the isogeny problem, using the knowledge from elliptic-curve cryptography developed over many years. Isogeny-based cryptography is attracting attention because the data size of public key and ciphertext is smaller than other methods. Since the previous isogeny-based cryptography SIKE (Supersingular Isogeny Key Encapsulation) broke in 2022, several alternatives have been devised, but we developed the most computationally efficient one, QFESTA (Quaternion Fast Encapsulation from Supersingular Torsion Attacks) [3]. Compared with ML-KEM, QFESTA achieves less than 1/5 the private-key data size, less than 1/3 the public-key data size, and less than the ciphertext data size. In collaboration with researchers at the University of Tokyo and KU Leuven in Belgium, we also developed a digital-signature scheme SQIsign2D-East [4]. This scheme greatly reduces the verification cost of SQIsign (Short Quaternion and Isogeny Signature), which is a method participating in NIST’s additional solicitation of post-quantum digital signatures. As a result of this achievement, our colleagues have joined the SQIsign team since the second round of standardization and have been conducting R&D.

As described above, we are proud of our R&D efforts on multiple types of PQC, producing excellent results. We will continue to conduct R&D on PQC to contribute to safe and secure information communications and society.

3. R&D on migration to PQC

The idea of a quantum computer dates back to 1981, and the competition to develop quantum computers among Google, IBM, and venture companies has intensified. A fault-tolerant quantum computer (FTQC) and cryptographically relevant quantum computer (CRQC) will appear in the 2030s. By the combination of Shore’s algorithm described above and FTQC/CRQC, the threat of decryption of public-key encryption widely used in PKI has become real. The HNDL (Harvest Now Decrypt Later) attack, in which the target ciphertexts are collected now and decrypted after the practical use of quantum computers, is also a real threat. Under these circumstances, the necessity of moving from modern cryptography to PQC (hereinafter referred to as PQC migration) is increasing daily. The public-key encryption RSA (Rivest–Shamir–Adleman)-2048 will expire at the end of 2030 (the 2030 problem of cryptography), which is also a factor encouraging PQC migration.

On the basis of the above situation, we are also conducting R&D on crypto-agility technologies that will contribute to PQC migration. Crypto agility refers to the ability to switch between encryption methods quickly and flexibly, so that if an encryption method is broken or a new encryption method is introduced, the system can smoothly switch to the new encryption method without major changes. We have experienced shifting to new cryptographic mechanisms due to concerns about old ones being potentially compromised, but in most cases we only needed to increase the key length or alter just one mechanism at a time. However, PQC migration is a transition from modern cryptography to a completely new method of PQC, and there are difficulties even in the main ones as follows.

Since almost all information and communication technology systems are involved in PQC migration, and not only companies and individuals but also countries need to respond, each country has published its response policies and timelines.

In the United States, in May 2022, then U.S. President Joe Biden signed an executive order to shift to PQC by 2035 due to concerns that conventional cryptographic mechanisms would be compromised by the development of quantum computers. Therefore, the tasks that each administrative agency should carry out by 2023 on the transition to PQC were indicated. (However, due to changes in President Trump’s policy, these documents were kept private at the time of writing, and the latest status of the activities is no longer generally available.)

The UK government has also published a timeline for PQC migration. The outline of the plan is that the assessment will be completed and a migration plan will be made by 2028, migration of the top-priority systems will be completed by 2031, and migration of all other systems will be completed by 2035 [5].

The EU also published a roadmap in February 2025 [6]. The plan is to move ahead a bit earlier than the UK timeline, with a roadmap to be drawn up by the end of 2026 and pilot projects for high and medium risk to be launched, migration for high risk to be completed by the end of 2030, and migration for medium and small risk to be completed by the end of 2035.

In Japan, the financial industry is leading the way in considering PQC migration. The Financial Services Agency established the Study Group on Deposit-taking Institutions’ Response to Post-Quantum Cryptography, which held a wide-ranging discussion on recommendations, challenges, and points to note when considering PQC migration, and published a report in November 2024 [7]. The Financial Services Agency is urging not only megabanks but also regional banks to begin considering PQC migration as soon as possible. On June 30, 2025, the Inter-Ministerial Liaison Conference on the Use of Post-Quantum Cryptography (PQC) in Government Agencies, etc. was held to consider and promote measures regarding the use of PQC in government agencies, etc. [8]. The outline of the PQC migration roadmap is scheduled to be finalized around November 2025.

It is expected that PQC migration will begin in earnest in each country and industry. PQC migration is an unavoidable issue for NTT Group companies and customer companies, and we will continue to work on the creation and dissemination of crypto-agility technologies that contribute to smooth PQC migration.

4. R&D on new cryptographic functions using quantum information processing

Quantum information processing is a technology that uses the principle of quantum mechanics to execute information processing impossible with conventional computers. Specifically, quantum mechanical phenomena, such as quantum bit superposition and entanglement, are used. Quantum computers are representative examples of quantum information processing.

When practical quantum computers appear in the 2030s, it is thought that they will be used by enterprise users first, then a world where ordinary users can use quantum computers on a daily basis in the form of cloud services will come. Looking ahead to such a future, we are conducting research to create new cryptographic functions by combining quantum information processing and cryptographic theory.

Today, we send and receive important data encrypted. The recipient of the encrypted data can copy it as much as they want, and there is no way for the sender to be sure that the data have been completely deleted from the recipient’s hands when they are done using it. In reality, however, one needs a way to ensure that data are deleted when no longer available.

To solve these problems, we are researching a cryptographic method that can prove that data (ciphertext) have been deleted by making good use of the “no-cloning theorem” of quantum mechanics, which states that it is impossible to create an exact copy of a given quantum state [9]. When this method is established, for example, safe and appropriate software lending and returning can be possible. Specifically, the software can be run during the rental period but cannot be run once it is returned (Fig. 4).

Fig. 4. Solving social problems through research of new cryptographic functionality using quantum computers.

These are still in the basic research stage, but by advancing such research, we believe that we can implement a mechanism to appropriately protect the rights of data owners and achieve a society in which safe and secure data distribution and utilization based on more reliable technology can spread.

5. Conclusion

The R&D of cryptography technology of NTT Social Informatics Laboratories which looked at the coming of the quantum-computer era was introduced. Cryptography will continue to be important as a basic technology that contributes to a safe and secure society. We will continue our R&D efforts toward the further development and sophistication of cryptographic technology.

References

[1]	Press release issued by NTT, “NTT’s Secure Computing Technology adopted as ISO International Standard—Secure computing technology to speed up data utilization and protect privacy,” Mar. 21, 2024. https://group.ntt/en/newsrelease/2024/03/21/240321b.html
[2]	Press release issued by the University of Tokyo, NTT, Kyushu University, and Nagasaki Prefectural University on Jan. 20, 2025 (in Japanese). https://group.ntt/jp/newsrelease/2025/01/20/250120a.html
[3]	Press release issued by NTT, “Developed QFESTA, an Efficient Isogeny-Based Cryptography with Small Public Key and Ciphertext Size—Using a technique that breaks SIKE, the NIST standardization candidate,” Sept. 5, 2024. https://group.ntt/en/newsrelease/2024/09/05/240905a.html
[4]	Press release issued by NTT on Dec. 9, 2024 (in Japanese). https://group.ntt/jp/topics/2024/12/09/asiacrypt2024.html
[5]	National Cyber Security Center, “Timelines for migration to post-quantum cryptography,” Mar. 2025. https://www.ncsc.gov.uk/pdfs/guidance/pqc-migration-timelines.pdf
[6]	Press release issued by EU, “EU reinforces its cybersecurity with post-quantum cryptography,” June 23, 2025. https://digital-strategy.ec.europa.eu/en/news/eu-reinforces-its-cybersecurity-post-quantum-cryptography
[7]	Financial Services Agency, “Publication of the ‘Report of the Study Group on Deposit-taking Institutions’ Response to Post-Quantum Cryptography,’” Nov. 26, 2024. https://www.fsa.go.jp/en/newsletter/weekly2024/614.html#e06
[8]	Cabinet Secretariat, “First Meeting of Inter-Ministerial Liaison Conference on the Use of Post-Quantum Cryptography (PQC) in Government Agencies, etc.,” June 2025 (in Japanese). https://www.cas.go.jp/jp/seisaku/pqc/dai1/gijisidai.html
[9]	T. Yamakawa, “Research of Cryptographic Protocols for Secure Communications in the Quantum Computer Era,” NTT Technical Review, Vol. 21, No. 2, pp. 11–15, 2023. https://doi.org/10.53829/ntr202302ri1