Interviews

Project Overview

Focus on quantum computers and the importance of post-quantum cryptography

In recent years, there has been a substantial amount of research on quantum computers, and this is having an impact on the field of cryptography. Some of the widely popular cryptosystems, such as the RSA and elliptic curve cryptography (ECC), may be broken by large scale quantum computers. Thus, the development of cryptographic systems called post-quantum cryptography (PQC) that are secure against both quantum and classical computers is underway worldwide. PQC has been one of the research themes of the Security Fundamentals Laboratory for some time. Since the development of quantum computers has become more active, we have organized a team specializing in PQC. Our two main activities are cryptanalysis research and its implementation. In particular, our current medium- to long-term plan is to promote research so that post-quantum cryptography can be used in Japan.

The standardization of post-quantum cryptography is being actively discussed and led by the United States, and such efforts are necessary in Japan as well. It is important to be able to judge the security of PQC with our own technology, and to prepare PQC in Japan before the cryptosystems that are widely used currently and could be broken by quantum computers become unavailable.

Security Evaluation for the post-quantum cryptography

What are the post-quantum cryptography and our activity of its security evaluation

RSA and ECC can be broken if solutions of the integer prime factorization problem and discrete logarithm problem on elliptic curves (ECDLP) can be efficiently obtained, respectively. Since it has been theoretically proven that quantum computers can efficiently solve these mathematical problems, the progress of quantum computers is closely related to the security of RSA and ECC. To deal with the threat of quantum computers, PQC is constructed from computational problems that are expected to need a very long time even if one can use both quantum and classical computers. (A classical computer means a standard computer that uses digital circuits. The terminology “classical” is from the correspondence between quantum and classical mechanics in physics.) Lattice-based cryptography, code-based cryptography, multivariate cryptography, isogeny-based cryptography, and hash-based signature are representative PQCs.

Our activities for the security evaluation of PQC have two major directions. The first one is the estimation of the security strength for RSA and ECC by using quantum computers. This is used to create a transition timeline from the current cryptosystems to PQCs.

For example, the security strength of RSA is measured by the digits of the composite number used for the encryption and decryption in RSA. Note that RSA can be broken if the composite number is factorized, and the larger the composite number, the larger the computational cost to factorize it.

As of 2021, the latest quantum and classical computers can factorize such numbers in a few digits and 250 digits whereas the daily-used RSA employs about 600-digit numbers. This means quantum computers are not danger against the current cryptography as of now.

In the case of ECC, the security of ECC depends on the hardness to solve ECDLP. There have been no experimental reports for solving the ECDLP on quantum computers. Even for discrete logarithm problems over a small finite field, that is the simpler variants of the ECDLP, only small experiments with only one digit parameter have been reported. Therefore, we believe that the current quantum computers cannot be a threat to the daily-used cryptographies such as RSA or ECC.

Another direction of our research activities is to evaluate the security of PQCs against both classical and quantum computers and make forecasting among the computer performance and security parameters.

Toward Security Evaluation by the World’s Most Advanced Technological Capabilities

The more advanced technological abilities we have, the more valuable our security evaluations of cryptographic algorithms become. This is because the secure operation of a cryptographic algorithm can be ensured by confirming that it is difficult to break even when using the world’s most advanced technology. In our research on cryptographic security evaluation, we find new theories for analyzing cryptographic techniques and present them at international conferences and in papers. Furthermore, we write our codes based on the theory we have found and use them to solve challenge problems in benchmark tests to achieve world records. The theory and programs used in this process will be made publicly available so that other researchers can use them to improve their research. In this way, the security of cryptography can be verified on a global level.

Future Prospects

The future vision for 2030: Security evaluation against many post-Moore computers

During the security evaluation, the researchers find security risks before they are discovered for abuse. Also, they apply a patch to fix the problem to keep the security of cryptographic technology. Various candidates of PQCs have been proposed. Several of them are entered into a process to select cryptographic schemes expected to be a part of the global standards. For candidates that pass the semi-final rounds, serious vulnerabilities have been discovered in the final round. We think this turns out the necessity of the continuous evaluation of the strong candidates and finalists.

The quantum computers have been attracted due to the nonnegligible possibility to break the RSA in the near future. From a broader perspective, the quantum computers can be classified as a subset of the post-Moore computers. This arises a new issue: even if a cryptographic scheme is secure against both classical and quantum computers, how is it against other types of post-Moore computers? This can be an important area that we need to research for the next decades.