Cryptology ePrint Archive: Report 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.

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:

[ Cryptology ePrint archive ]