Solving McEliece-1409 in One Day—Cryptanalysis with the Improved BJMM Algorithm
摘要
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) provided the first implementation of the representation-based ISD, such as May–Meurer–Thomae (MMT) or Becker–Joux–May–Meurer (BJMM) algorithm and solved 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. Our results provide both theoretical and practical evidence for the reliability of code-based NIST-PQC round 4 candidates.