Paper 2024/393

Revisiting the May--Meurer--Thomae Algorithm --- Solving McEliece-1409 in One Day

Shintaro Narisada, KDDI Research, Japan
Shusaku Uemura, KDDI Research, Japan
Hiroki Okada, KDDI Research, Japan
Hiroki Furue, The University of Tokyo, Japan
Yusuke Aikawa, The University of Tokyo, Japan
Kazuhide Fukushima, KDDI Research, Japan

As post-quantum cryptography transitions toward practical deployment, the significance of extensive cryptanalysis is on the rise. Three out of the four NIST-PQC round 4 candidates are forms of code-based cryptography. Analyses of asymptotic complexity in information set decoding (ISD) algorithms have been a central focus in the field of code-based cryptography. Recently, Esser, May and Zweydinger (Eurocrypt '22) demonstrate the practicality of the May--Meurer--Thomae (MMT) algorithm by decoding McEliece-1284. Esser and Zweydinger (Eurocrypt '23) propose the time-memory trade-off variant of Becker--Joux--May--Meurer (BJMM) decoding, which solves QC-3138. These works have paved the way for the cryptanalysis of ISD in real-world scenarios. In this work, we further advance the progress of the abovementioned studies by performing a concrete analysis of MMT decoding. We improve the list construction in MMT so that the number of both candidates and representations in the enumeration phase is increased without the need for additional time and memory. Our new algorithm is theoretically 5.1 times faster than the BJMM algorithm for Classic McEliece I instance. We achieve the minimum time complexity across all categories of Classic McEliece among all ISD algorithms. Moreover, compared with the BJMM algorithm, our MMT algorithm reduces the bit security by 1 to 3 bits for all code based NIST-PQC round 4 candidates. Practical security estimates confirm that all the candidates have sufficiently strong bit security, except for Classic McEliece III, with a 1-bit deficiency. In addition, we implement our new MMT algorithm in a GPU environment and provide the new record of the McEliece-1409 instance, along with implementation details and experimental analyses. Our study verifies the practical reliability of the code-based candidates against current ISD algorithms.

Available format(s)
Attacks and cryptanalysis
Publication info
Information Set DecodingRepresentation TechniqueMcEliece
Contact author(s)
sh-narisada @ kddi com
su-uemura @ kddi com
ir-okada @ kddi com
furue-hiroki261 @ g ecc u-tokyo ac jp
aikawa @ mist i u-tokyo ac jp
ka-fukushima @ kddi com
2024-03-04: approved
2024-03-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shintaro Narisada and Shusaku Uemura and Hiroki Okada and Hiroki Furue and Yusuke Aikawa and Kazuhide Fukushima},
      title = {Revisiting the May--Meurer--Thomae Algorithm ---  Solving McEliece-1409 in One Day},
      howpublished = {Cryptology ePrint Archive, Paper 2024/393},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.