Corporate Research & Development Center

Toshiba Develops Public Key Cryptosystem Based on New Principles That is Difficult to Crack Even with Quantum Computers

2017/8
Toshiba Corporation

Overview

Toshiba Corporation has developed a post-quantum public key cryptosystem in collaboration with Hokkaido University of Education, Kyushu University, and the National Institute of Advanced Industrial Science and Technology. The security of the cryptosystem is based on the problem of finding a small solution to a multivariate non-linear indeterminate equation, which is expected to be computationally hard, even with quantum computers. It is expected to offer security and calculation efficiency equivalent to or better than those of lattice-based cryptosystem, and to offer a promising candidate for post-quantum cryptosystems. Details were presented at SAC2017, an international conference held in Ottawa, Canada, on August 16–18, 2017.

Development Background

Major IT firms and national governments are making large investments in the development of quantum computers. However, quantum algorithms that can run on quantum computers using quantum mechanisms can quickly solve the integer factorization and discrete logarithm problems which the security of current public key cryptosystems depends on. As quantum computer will break these cryptosystems and end their usefulness, research efforts are now focusing on post-quantum public key cryptosystems that even quantum computers cannot break.

Though post-quantum public key cryptosystems are generally fast, they also face the problem of having a large public key, which prevents practical application. Although many researchers are tackling this problem, most by focusing on lattice-based cryptosystems, there are no public key cryptosystem whose use has won an international consensus.

Features of This Technology

Toshiba has developed a new type of public key cryptosystem whose security depends on the finding the smallest solution problem in nonlinear equations. This is computationally harder to solve than the linear equations that are the basis for the security of conventional post-quantum public key cryptosystems, such as lattice-based cryptosystem. The new system is expected to be more secure than others, since current efficient algorithms to solve linear equations cannot be applied directly. In testing to date, security has been realized with a public key of approximately 2 KB, about that same size as the public key required for lattice-based cryptosystem. If a public key cryptosystem with a public key as short as that of the current system can be achieved through future improvements, it will open the way to practical application and provide long term secure networks resistant to quantum computers.

Future Development, Plans, and Targets

Toshiba continues to refine the cryptosystem, targeting its proposal as an international standard for a public key cryptosystem, and will encourage evaluation by many researchers at venues such as international conferences.