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
-
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},
url = {https://eprint.iacr.org/2020/801}
}
