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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Shintaro Narisada,
  • Shusaku Uemura,
  • Hiroki Okada,
  • Hiroki Furue,
  • Yusuke Aikawa,
  • Kazuhide Fukushima

摘要

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.