Key reconstruction for QC-MDPC McEliece from imperfect distance spectrum

Motonari Ohtsuka; Takahiro Ishimaru; Rei Iseki; Shingo Kukita; Kohtaro Watanabe

Paper 2025/485

Key reconstruction for QC-MDPC McEliece from imperfect distance spectrum

Motonari Ohtsuka

, Japan Ground Self-Defense Force

Takahiro Ishimaru

, National Defense Academy of Japan

Rei Iseki

, National Defense Academy of Japan

Shingo Kukita

, National Defense Academy of Japan

Kohtaro Watanabe

, National Defense Academy of Japan

Abstract

McEliece cryptosystems, based on code-based cryptography, is a candidate in Round 4 of NIST's post-quantum cryptography standardization process. The QC-MDPC (quasi-cyclic moderate-density parity-check) variant is particularly noteworthy due to its small key length. The Guo-Johansson-Stankovski (GJS) attack against the QC-MDPC McEliece cryptosystem was recently proposed and has intensively been studied. This attack reconstructs the secret key using information on decoding error rate (DER). However, in practice, obtaining complete DER information is presumed to be time-consuming. This paper proposes two algorithms to reconstruct the secret key under imperfection in the DER information and evaluates the relationship between the imperfection and efficiency of key reconstruction. This will help us to increase the efficacy of the GJS attack.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: McEliece cryptosystem QC-MDPC codes Reaction attacks Distance spectrum Key reconstruction
Contact author(s): kukita @ nda ac jp
wata @ nda ac jp
History: 2025-03-19: revised; 2025-03-14: received; See all versions
Short URL: https://ia.cr/2025/485
License: CC BY

BibTeX

@misc{cryptoeprint:2025/485,
      author = {Motonari Ohtsuka and Takahiro Ishimaru and Rei Iseki and Shingo Kukita and Kohtaro Watanabe},
      title = {Key reconstruction for {QC}-{MDPC} {McEliece} from imperfect distance spectrum},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/485},
      year = {2025},
      url = {https://eprint.iacr.org/2025/485}
}