 |
|||||||||||||||||
|
|
|||||||||||||||||
        |
Feature Articles: Front-line Cybersecurity Technology to Enable a Digital Society Vol. 17, No. 3, pp. 22–26, Mar. 2019. https://doi.org/10.53829/ntr201903fa4 Research Trends in Post-quantum CryptographyAbstractThe growing recognition that quantum computers are soon to be a reality is driving research into post-quantum cryptography. This article introduces the Post-Quantum 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 post-quantum cryptography, and introduces NTT initiatives and independent research related to that project. Keywords: cryptographic technology, post-quantum security, quantum computer
1. Post-quantum 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 symmetric-key cryptography and public-key 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 public-key cryptography and digital signatures, namely cryptographic algorithms based on the difficulty of the factorization problem (RSA (Rivest-Shamir-Adleman) encryption, RSA signatures, etc.) and those based on the difficulty of the discrete logarithm problem (Diffie–Hellman key exchange, elliptic-curve 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 large-scale 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 public-key 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 post-quantum (public-key) cryptography. 2. Standardization trends in post-quantum cryptographyOn the question of whether it is necessary to start a migration to post-quantum cryptographic algorithms, we refer to the formula proposed by Michele Mosca, co-founder 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 post-quantum 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 Post-Quantum Cryptography Standardization project, which is having a major impact on cryptographic technology standardization around the world.
3. NIST Post-Quantum Cryptography Standardization ProjectThe NIST Post-Quantum Cryptography Standardization Project began in earnest in 2016 with the aim of selecting and standardizing post-quantum cryptographic algorithms in the three categories of digital signature, public-key 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 key-encapsulation 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 key-encapsulation 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 Post-Quantum Cryptography Standardization activities. However, NTT is participating by making proposals for security enhancement techniques and security evaluation from a third-party standpoint and is working with other project members to ensure that suitable algorithms can be selected. Furthermore, though the NIST Post-Quantum Cryptography Standardization Project is focused only on post-quantum public-key cryptographic algorithms, NTT is independently researching post-quantum symmetric-key cryptography as well. 4.1 Security enhancement techniqueFor secure communications to be carried out in the real world, public-key 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 chosen-ciphertext attack (CCA) security. At present, CCA security is considered to be an essential requirement for the realistic use of public-key encryption algorithms. In this regard, techniques for converting a public-key encryption algorithm without CCA security to a public-key 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 post-quantum public-key encryption algorithm without CCA security to a post-quantum public-key encryption algorithm with CCA security [1]. This development makes it possible to configure a post-quantum public-key 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 post-quantum public-key cryptographic schemes. It was found that it could be applied to at least seven of the candidate algorithms in the NIST Post-Quantum Cryptography Standardization Project. The use of post-quantum public-key encryption algorithms based on this technology will enable cryptographic communications at about the same load as existing methods even in the post-quantum 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 Post-quantum symmetric-key cryptographic technology(1) Security evaluation techniques A general-purpose quantum algorithm for attacking symmetric-key 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 symmetric-key cryptography, and security evaluations using these techniques are being performed. At NTT, we have obtained results surpassing those of existing research by combining meet-in-the-middle attacks and quantum algorithms [3, 4]. It is also known that security can break down for some symmetric-key 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 symmetric-key ciphers can be broken by quantum related-key attacks [5]. (2) Security-proving technique As described above, it is extremely important that the security of symmetric-key cryptography be assessed and proven considering the existence of attackers that instigate quantum-type accesses. NTT has developed a technique that proves the post-quantum 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
|
||||||||||||||||
