### McEliece needs a Break -- Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD

Andre Esser, Alexander May, and Floyd Zweydinger

##### Abstract

With the recent shift to post-quantum algorithms it becomes increasingly important to provide precise bit-security estimates for code-based cryptography such as McEliece and quasi-cyclic schemes like BIKE and HQC. While there has been significant progress on information set decoding (ISD) algorithms within the last decade, it is still unclear to which extent this affects current cryptographic security estimates. We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938). Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST's standardization process. For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC. For the proposed McEliece round-3 parameter sets of 192 and 256 bit, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
MMTBJMM DecodingRepresentation TechniqueMcEliece
Contact author(s)
andre esser @ tii ae
floyd zweydinger @ rub de
History
2022-05-18: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1634

CC BY

BibTeX

@misc{cryptoeprint:2021/1634,
author = {Andre Esser and Alexander May and Floyd Zweydinger},
title = {McEliece needs a Break -- Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD},
howpublished = {Cryptology ePrint Archive, Paper 2021/1634},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1634}},
url = {https://eprint.iacr.org/2021/1634}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.