Scholarlink

Code-based cryptography is a family of post-quantum cryptographic schemes, primarily based on a problem called syndrome decoding ( \(\textsf{SD}\) ). Among such schemes, HQC, BIKE, and Classic McEliece were selected as finalists in the fourth round of the NIST PQC project, with HQC being selected as a standard in 2025. In this work, we analyze the concrete hardness of the \(\textsf{SD}\) instances used for HQC, BIKE, and Classic McEliece. In most cases, the resulting bit security estimates closely match NIST’s security requirements. We also implement the improved variant of the BJMM algorithm proposed by Narisada et al. (ISC ’24) to solve the quasi-cyclic \(\textsf{SD}\) problem underlying HQC and BIKE. Using this implementation, we provide a runtime-based analysis and new record computations for QC-3366, QC-3602, and QC-3846 instances in decodingchallenge.org, along with all artifacts and optimized implementations.

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

Refined Analysis of the Concrete Hardness of the Quasi-Cyclic Syndrome Decoding

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Shintaro Narisada,
  • Hiroki Okada,
  • Yusuke Aikawa,
  • Kazuhide Fukushima

摘要

Code-based cryptography is a family of post-quantum cryptographic schemes, primarily based on a problem called syndrome decoding ( \(\textsf{SD}\) ). Among such schemes, HQC, BIKE, and Classic McEliece were selected as finalists in the fourth round of the NIST PQC project, with HQC being selected as a standard in 2025. In this work, we analyze the concrete hardness of the \(\textsf{SD}\) instances used for HQC, BIKE, and Classic McEliece. In most cases, the resulting bit security estimates closely match NIST’s security requirements. We also implement the improved variant of the BJMM algorithm proposed by Narisada et al. (ISC ’24) to solve the quasi-cyclic \(\textsf{SD}\) problem underlying HQC and BIKE. Using this implementation, we provide a runtime-based analysis and new record computations for QC-3366, QC-3602, and QC-3846 instances in decodingchallenge.org, along with all artifacts and optimized implementations.