Welcome to the resource topic for
**2020/801**

**Title:**

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

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

**ePrint:**
https://eprint.iacr.org/2020/801

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .