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 .