KDDI Research, Inc. has become the first group in the world to successfully solve 1,161-dimensional code-based cryptography as part of the Challenges for Code-Based Problems decryption contest. The decryption challenge, which has never been solved before, has a number of potential solutions reaching 10 to the power of 48 in total, which would require the fastest supercomputer on Earth today more than 100 million years to solve. KDDI Research found the solution in just 375 hours.
The decryption contest is hosted by the National Institute for Research in Digital Science and Technology in France. Of the five challenges presented in the contest, KDDI Research was the first in the world to solve the problem of Syndrome Decoding in the Goppa-McEliece Setting. The KDDI team successfully accelerated the decryption process by approximately 250 times by improving the decryption algorithm and optimizing it for a parallel multithreaded environment.
The 1,161-dimensional code-based cryptography McEliece-Goppa Syndrome Decoding Problem involves a number of potential solutions counted at 10 to the power of 48, which would require 8 virtual machines to run 17 million parallel threads each to process. Accordingly, this problem was solved at the extremely high speed of approximately 375 hours, whereas the use of brute force to solve the problem (by applying the best available supercomputer in the world as of 2021 to testing every possibility without using a decryption algorithm) would require over 100 million years.
The result was announced at the 38th Symposium on Cryptography and Information Security (SCIS2021), held online from January 19 through 22.
RSA encryption is currently the most widely used form of public key encryption technology, and the security thereof depends on the difficulty of factoring large prime numbers. However, as prime factorization is now possible at high speed due to the recent emergence of quantum computing for practical applications, there is a growing need for a form of public key encryption in the future that can be protected even against quantum computers.
The National Institute of Standards and Technology in the US is currently working on selecting the next generation public key encryption technology as part of a project called Post-Quantum Cryptography (NIST-PQC) to standardize encryption capable of withstanding quantum computing.
The McEliece-Goppa Syndrome Decoding Problem solved by KDDI Research is multi-dimensional simultaneous linear equation in which the coefficient, constants, and answer are comprised only of 0s and 1s. Furthermore, the number of 1’s in the solution must be less than or equal to a given constant.
It is believed that even quantum computers would be unable to solve this problem efficiently, and this difficulty is the basis of the security of Classic McEliece encryption, chosen as a final candidate in the NIST-PQC project.
In order to achieve a secure encryption method, it is necessary to increase the dimension (the number of unknown variables) of the McEliece-Goppa Syndrome Decoding Problem to make solving it more difficult, but if the length is too long, it can massively increase the time required to process it. For that reason, research is being carried out on rapid problem solving to find the optimal length for ensuring security.
The results of the work by KDDI Research represents information of extreme importance to determining the safe length of encryption for the next generation public key encryption.
The organization intends to continue working on the acceleration of decryption algorithms, and research and development to achieve the a faster and more secure public key encryption technology for the future in order to contribute to the development of safe and secure information and communications systems.