"Post-quantum cryptography" decoding contest — KDDI Research Inc. and the University of Tokyo achieve world records

KDDI Research Inc., together with Graduate Student Takeshi Wakao, Assistant Professor Yusuke Aikawa, and Professor Tsuyoshi Takagi from the Graduate School of Information Science and Technology at the University of Tokyo, announced on January 9 that they had achieved world records by becoming the first to successfully decrypt code-based cryptography of 210, 220, 230, and 240 dimensions based on a set of three elements in the decryption contest "Challenges for code-based problems" for post-quantum cryptography (PQC), which is being standardized in the United States as next-generation cryptography. Furthermore, on December 15 last year, this achievement confirmed that ternary-based code-based cryptography achieves security equivalent to the U.S. standard PQC code-based cryptography with less than one-tenth the dimensionality (data size).

Both parties presented these results at the "2026 Symposium on Cryptography and Information Security (SCIS 2026)" held in Hakodate City from January 26 to 30.

A ternary field is a mathematical structure consisting of a set of three elements ("0," "1," and "2"), in which addition and multiplication are defined. A set consisting of "0" and "1" is a binary field. On this occasion, the researchers decrypted cryptography that no one had been able to solve before by developing and implementing an efficient algorithm using division and parallel processing for ternary-based code-based cryptography. Through this achievement, they demonstrated the effectiveness of a theoretical framework for evaluating in detail the security of cryptography based on binary fields, ternary fields, and other structures, and opened a path toward realizing new cryptographic schemes using mathematical structures.

When code-based cryptography based on ternary fields is used for digital signatures, it has the characteristic of enabling shorter signature lengths than binary fields, and its utilization is expected in devices with data size constraints such as smart cards and IoT sensors.

The problem the researchers tackled is called the "syndrome decoding problem," which forms the basis of the security of code-based cryptography based on ternary fields. It involves searching for a secret vector that satisfies conditions for a given matrix and vector based on ternary fields and is equivalent to deriving the secret key from the public key of code-based cryptography.

A decryption algorithm called Information Set Decoding is known as a standard method for solving this problem. However, since this algorithm is typically used to decrypt binary-field code-based cryptography, it was necessary to develop a more efficient decryption algorithm and its implementation for ternary-field code-based cryptography.

Therefore, to accomplish this, both parties extended the algorithm for binary fields, which they had been researching and developing through previous decryption contests, for use with ternary fields. They also applied a divide-and-conquer method that combines the decryption algorithm for binary fields with the decryption algorithm for ternary fields during the secret key search, improving its efficiency.

They then implemented the extended decryption algorithm in a parallel computing environment and constructed a computing environment consisting of up to seven desktop computers. Through these efforts, they were able to speed up the decryption process by approximately 1,000 times, and as a result, they succeeded in decrypting code-based cryptography from 210 to 240 dimensions in several tens of minutes to several days.

Based on this achievement, they demonstrated that code-based cryptography based on ternary fields has high security at the 128-bit level for parameters of 600 dimensions or more. Additionally, they constructed a theory for evaluating the security of code-based cryptography, including the binary-based code cryptography they had previously decrypted and the cryptography from this work, and evaluated and demonstrated the precise security of diverse code-based cryptography.