The University of Tokyo proposes a new high-speed algorithm — World record achieved in next-generation code deciphering contest

Project researcher Kosuke Sakata and Professor Tsuyoshi Takagi of the Graduate School of Information Science and Technology at the University of Tokyo announced that they have set a world record for deciphering a code that had previously remained unsolved in the MQ Challenge, a next-generation code deciphering contest. The MQ Challenge is a deciphering contest that evaluates the security of post-quantum ciphers, which cannot be deciphered even by quantum computers. It includes questions about cryptanalysis using multivariate polynomials.

In this contest, by clarifying the mathematical characteristics of the problem that needed to be decoded, the group proposed a new high-speed algorithm and achieved a world record. The results were presented at the Computer Security Symposium (CSS2023) held at ACROS Fukuoka (Tenjin, Chuo Ward, Fukuoka City) and in other venues from October 30 to November 2 organized by the Information Processing Society of Japan.

Once quantum computers are developed to a practical level, the ciphers that are currently in use will be easily deciphered. The National Institute of Standards and Technology (NIST) is in the process of selecting a secure quantum-resistant computer cipher that is challenging to break even for quantum computers. One quantum-resistant computer cryptography is a cryptographic method called multivariate polynomial cryptography and solving simultaneous quadratic multivariate polynomials (MQ problem) are required to decipher it.

The standard method to solve MQ problems is known as F4, an algorithm for computing the Gröbner Bases used in solving simultaneous multivariable equations, which require computation of a huge matrix to decipher. The research group clarified the mathematical characteristics of the MQ problem through a Hilbert series (a one-variable series that can be defined for a set of multivariable polynomials and has information on the algebraic structure of the set) and constructed an algorithm to minimize the number of polynomials to be calculated. As a result, they succeeded in speeding up the calculation of the matrix generated by F4 by extracting only those regions of the matrices that are essential to the calculation and computing those smaller matrices.

Takagi commented, "In the era of quantum computers, cryptographic technology that can be used safely is attracting significant attention, with standardization efforts being promoted by the U.S. government. This study achieved a world record in deciphering, which will enable us to establish a rigorous security evaluation method and contribute to the development of secure and highly reliable next-generation cryptography systems."