Paper 2024/393

Solving McEliece-1409 in One Day --- Cryptanalysis with the Improved BJMM Algorithm

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

Syndrome decoding problem (SDP) is the security assumption of the code-based cryptography. Three out of the four NIST-PQC round 4 candidates are code-based cryptography. Information set decoding (ISD) is known for the fastest existing algorithm to solve SDP instances with relatively high code rate. Security of code-based cryptography is often constructed on the asymptotic complexity of the ISD algorithm. However, the concrete complexity of the ISD algorithm has hardly ever been known. Recently, Esser, May and Zweydinger (Eurocrypt '22) provide the first implementation of the representation-based ISD, such as May--Meurer--Thomae (MMT) or Becker--Joux--May--Meurer (BJMM) algorithm and solve the McEliece-1284 instance in the decoding challenge, revealing the practical efficiency of these ISDs. In this work, we propose a practically fast depth-2 BJMM algorithm and provide the first publicly available GPU implementation. We solve the McEliece-1409 instance for the first time and present concrete analysis for the record. Cryptanalysis for NIST-PQC round 4 code-based candidates against the improved BJMM algorithm is also conducted. In addition, we revise the asymptotic space complexity of the time-memory trade-off MMT algorithm presented by Esser and Zweydinger (Eurocrypt '23) from $2^{0.375n}$ to $2^{0.376n}$.

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-05-17: revised
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 = {Solving {McEliece}-1409 in One Day ---  Cryptanalysis with the Improved {BJMM} Algorithm},
      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.