**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.

**Category / Keywords: **public-key cryptography / permutation code equivalence problem, linear code equivalence problem, code-based cryptography, post-quantum cryptography

**Date: **received 27 Jun 2020, last revised 10 Jul 2020

**Contact author: **ward beullens at esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20200710:150211 (All versions of this report)

**Short URL: **ia.cr/2020/801

[ Cryptology ePrint archive ]