KDDI Institute and Kyushu University are holding a 60-dimensional Learning with Errors (LWE) that no one has ever been able to crack in a cryptanalysis contest (sponsored by Darmstad Institute of Technology, Germany) where crypto researchers from all over the world are expected to participate. ) Announced that the problem was deciphered for the first time in the world.
In the financial field, cryptography is used on the network for the security of transactions.In a method called public key cryptography, information is exchanged using two types of keys (public key and private key) that are mathematically associated with each other.However, public key cryptography called "lattice-based cryptography", which has a high degree of difficulty, is being considered because of concerns that it will be decrypted by the realization of quantum computers.
The LWE problem is a problem that solves multiple simultaneous linear equations with intentionally added errors.This is equivalent to breaking the lattice code.In order to realize secure cryptography, it is necessary to increase the dimension (number of unknown variables) of the LWE problem or increase the error to make it difficult to decipher.However, if the dimension is too high, the calculation time increases, and if the error is too large, the probability that correct cryptographic processing cannot be performed increases.For this reason, many research institutes are conducting research on high-speed solutions in order to obtain the optimum dimension and the magnitude of error that ensure safety.
This time, the research group succeeded in speeding up and parallelizing the decoding algorithm, and by using 20 virtual PCs in the commercial cloud, the 60-dimensional calculation that takes more than 16 years by the brute force method using a supercomputer. The LWE problem was deciphered in about 55 days.He also said that he had deciphered problems of XNUMX dimensions and below.
This achievement will be important information for determining the secure dimension and the magnitude of error when using lattice-based cryptography as the next-generation public key cryptography.In the future, we would like to further study the speeding up of the decryption algorithm and realize high-speed and secure next-generation public key cryptography.
