

Feature Articles: Frontline Cybersecurity Technology to Enable a Digital Society Research Trends in Postquantum CryptographyAbstractThe growing recognition that quantum computers are soon to be a reality is driving research into postquantum cryptography. This article introduces the PostQuantum Cryptography Standardization project of the National Institute of Standards and Technology (NIST) in the United States, which is playing a core role in the research and development of postquantum cryptography, and introduces NTT initiatives and independent research related to that project. Keywords: cryptographic technology, postquantum security, quantum computer 1. Postquantum cryptographic technologyToday, a great deal of highly confidential information such as personal data and credit card numbers is being exchanged on the Internet. For this reason, cryptographic systems such as symmetrickey cryptography and publickey cryptography are being used to conceal the contents of such transmissions. In addition, authentication technologies such as digital signatures and message authentication codes (MACs) are being used to authenticate the other party and the content of the received message. Certain algorithms have found widespread use in publickey cryptography and digital signatures, namely cryptographic algorithms based on the difficulty of the factorization problem (RSA (RivestShamirAdleman) encryption, RSA signatures, etc.) and those based on the difficulty of the discrete logarithm problem (Diffie–Hellman key exchange, ellipticcurve Diffie–Hellman key exchange, Digital Signature Algorithm (DSA), etc.). In 1994, Peter Shor, then of Bell Laboratories, proposed efficient algorithms using a quantum computer for solving these two problems. Consequently, if a quantum computer that can perform largescale calculations in a stable manner can be built, cryptographic algorithms that are now in widespread use will no longer be secure. This is why the research, development, and standardization of cryptographic algorithms that a quantum computer cannot break or tamper with have become quite active as efforts continue to successfully develop a quantum computer. Within publickey cryptographic technology, cryptographic algorithms that have been designed based on problems for which quantum computers are considered to be weak in solving are referred to as postquantum (publickey) cryptography. 2. Standardization trends in postquantum cryptographyOn the question of whether it is necessary to start a migration to postquantum cryptographic algorithms, we refer to the formula proposed by Michele Mosca, cofounder and deputy director of the Institute for Quantum Computing, University of Waterloo, Ontario, Canada, as described below. Let us define x, y, and z as follows:
If x + y > z, ciphertext created after y years based on the thinking that “I want to keep this information secret for at least x years” may be cracked by a quantum computer in less than x years. Accordingly, if it is thought that x + y > z is true at the present time, there is a need to study closely the standardization of and migration to postquantum cryptographic technology. Under the assumption that z number of years from today’s state of quantum computer development is likely to be within a realistic range, organizations and standardization bodies in various countries are moving forward with migration studies, as outlined below.
Among these activities, we introduce here the NIST PostQuantum Cryptography Standardization project, which is having a major impact on cryptographic technology standardization around the world.
3. NIST PostQuantum Cryptography Standardization ProjectThe NIST PostQuantum Cryptography Standardization Project began in earnest in 2016 with the aim of selecting and standardizing postquantum cryptographic algorithms in the three categories of digital signature, publickey encryption, and key establishment. The timeline for this project is summarized below (Fig. 1).
A total of 82 proposals were submitted by the deadline in November 2017; of these, 23 concerned digital signatures and 59 concerned encryption and keyencapsulation mechanisms. After an examination of documents and forms was conducted, Round 1 began in December 2017, at which time 69 proposals remained. However, 5 proposals were later withdrawn, resulting in a total of 64 proposals at present—19 for digital signatures and 45 for encryption and keyencapsulation mechanisms. As mentioned above, the results of examining documents and forms left 69 candidate algorithms for Round 1. These candidates are not necessarily secure simply by reaching Round 1. Immediately after the release of Round 1 candidates, lively discussions took place on the security of each method via the NIST pqc mailing list. Among these candidates, many were shown to be breakable as summarized below.
It should be kept in mind that security evaluation techniques are expected to be improved going forward to Round 2. 4. NTT initiativesNTT did not submit an original algorithm to these NIST PostQuantum Cryptography Standardization activities. However, NTT is participating by making proposals for security enhancement techniques and security evaluation from a thirdparty standpoint and is working with other project members to ensure that suitable algorithms can be selected. Furthermore, though the NIST PostQuantum Cryptography Standardization Project is focused only on postquantum publickey cryptographic algorithms, NTT is independently researching postquantum symmetrickey cryptography as well. 4.1 Security enhancement techniqueFor secure communications to be carried out in the real world, publickey encryption algorithms must provide a level of security that is strong enough not only to conceal the message itself but also to prevent messages from being tampered with. Technically speaking, this is called chosenciphertext attack (CCA) security. At present, CCA security is considered to be an essential requirement for the realistic use of publickey encryption algorithms. In this regard, techniques for converting a publickey encryption algorithm without CCA security to a publickey encryption algorithm with CCA security have been researched for some time, but it was not until 2010 that research began in order to determine whether such techniques were secure enough to counter attacks using a quantum computer. It was found that these techniques could indeed be effective against quantum computers but only with a drop in efficiency. However, no security enhancement technique that was effective against quantum computers without sacrificing efficiency was known to exist. With this being the case, NTT developed a new technique that improves security by converting a postquantum publickey encryption algorithm without CCA security to a postquantum publickey encryption algorithm with CCA security [1]. This development makes it possible to configure a postquantum publickey encryption algorithm according to the highest global standards with high efficiency. In addition, the technique has broad utility, enabling it to be applied to a variety of existing postquantum publickey cryptographic schemes. It was found that it could be applied to at least seven of the candidate algorithms in the NIST PostQuantum Cryptography Standardization Project. The use of postquantum publickey encryption algorithms based on this technology will enable cryptographic communications at about the same load as existing methods even in the postquantum era. 4.2 Security evaluation from the outsideA cryptographic algorithm called Giophantus is one of the 69 candidate algorithms evaluated in the NIST standardization project. This algorithm was originally presented in a paper under the name Indeterminate Equation Cryptosystem (IEC). The security of this scheme, while proven to be secure, is dependent on the difficulty of a certain problem. In this regard, large size parameters are required to ensure that the underlying problem is difficult. However, since IEC was designed so that the key size and ciphertext length would be short, the underlying problem with small size parameters was an issue. Against this background, we proposed a new attack technique that could degrade security for small size parameters [2]. The results of an experiment using this attack technique revealed that practical cryptanalysis could be performed in 30–40 seconds on a desktop personal computer. As a result of this study, parameters for the Giophantus version of IEC submitted to NIST were significantly revised. 4.3 Postquantum symmetrickey cryptographic technology(1) Security evaluation techniques A generalpurpose quantum algorithm for attacking symmetrickey cryptography is presently unknown. Consequently, an attack that applies computer scientist L. K. Grover’s algorithm for searching a database is currently known to be the most effective. For this reason, quantum attack techniques surpassing the Grover algorithm are being devised by analyzing in detail the inner workings of symmetrickey cryptography, and security evaluations using these techniques are being performed. At NTT, we have obtained results surpassing those of existing research by combining meetinthemiddle attacks and quantum algorithms [3, 4]. It is also known that security can break down for some symmetrickey ciphers and MACs in cases where the attacker can access a cryptographic algorithm or MAC algorithm in a quantum manner. NTT has also been researching attacks of this kind and has shown that some symmetrickey ciphers can be broken by quantum relatedkey attacks [5]. (2) Securityproving technique As described above, it is extremely important that the security of symmetrickey cryptography be assessed and proven considering the existence of attackers that instigate quantumtype accesses. NTT has developed a technique that proves the postquantum security of hash functions even when attackers carry out quantum queries [6]. 5. Future developmentWe plan to create a portfolio of security enhancement and security evaluation techniques and to continue studying the development and deployment of secure cryptographic communication technologies even after the successful development of quantum computers. References
