Paper 2022/1715

An Algebraic Attack Against McEliece-like Cryptosystems Based on BCH Codes

Freja Elbro, Technical University of Denmark
Christian Majenz, Technical University of Denmark
Abstract

We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
post-quantum cryptographyMcEliecealgebraic attackBCH-codes
Contact author(s)
freel @ dtu dk
chmaj @ dtu dk
History
2023-01-31: last of 2 revisions
2022-12-11: received
See all versions
Short URL
https://ia.cr/2022/1715
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1715,
      author = {Freja Elbro and Christian Majenz},
      title = {An Algebraic Attack Against McEliece-like Cryptosystems Based on BCH Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1715},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1715}},
      url = {https://eprint.iacr.org/2022/1715}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.