Paper 2020/801

Not enough LESS: An improved algorithm for solving Code Equivalence Problems over $\mathbb{F}_q$

Ward Beullens

Abstract

Recently, a new code based signature scheme, called LESS, was proposed with three concrete instantiations, each aiming to provide 128 bits of classical security. Two instantiations (LESS-I and LESS-II) are based on the conjectured hardness of the linear code equivalence problem, while a third instantiation, LESS-III, is based on the conjectured hardness of the permutation code equivalence problem for weakly self-dual codes. We give an improved algorithm for solving both these problems over sufficiently large finite fields. Our implementation breaks LESS-I and LESS-III in approximately 25 seconds and 2 seconds respectively on a laptop. Since the field size for LESS-II is relatively small $(\mathbb{F}_7)$ our algorithm does not improve on existing methods. Nonetheless, we estimate that LESS-II can be broken with approximately $2^{44}$ row operations.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
permutation code equivalence problemlinear code equivalence problemcode-based cryptographypost-quantum cryptography
Contact author(s)
ward beullens @ esat kuleuven be
History
2020-07-10: revised
2020-06-27: received
See all versions
Short URL
https://ia.cr/2020/801
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/801,
      author = {Ward Beullens},
      title = {Not enough LESS: An improved algorithm for solving Code Equivalence Problems over $\mathbb{F}_q$},
      howpublished = {Cryptology ePrint Archive, Paper 2020/801},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/801}},
      url = {https://eprint.iacr.org/2020/801}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.