07 March 2025 | Tung Chou1 · Edoardo Persichetti2 · Paolo Santini3
This paper addresses the problem of finding an isometry mapping one linear code into another, known as code equivalence. The authors propose a new notion of equivalence, which significantly reduces the size of the witness required to prove equivalence. This new approach, based on *canonical representatives*, allows for the identification of broader classes of equivalent codes with compact witnesses. The paper introduces the Canonical Form Linear Equivalence Problem (CFLEP), which is shown to be as hard as the original code equivalence problem. This reduction leads to a faster solver for the code equivalence problem, especially when the finite field size is large. The authors also demonstrate a substantial reduction in signature size compared to the LESS submission, achieving signatures around 2 KB or less, which are among the smallest in the code-based setting. The paper contributes to the field of post-quantum cryptography, particularly in the area of digital signatures based on linear codes.This paper addresses the problem of finding an isometry mapping one linear code into another, known as code equivalence. The authors propose a new notion of equivalence, which significantly reduces the size of the witness required to prove equivalence. This new approach, based on *canonical representatives*, allows for the identification of broader classes of equivalent codes with compact witnesses. The paper introduces the Canonical Form Linear Equivalence Problem (CFLEP), which is shown to be as hard as the original code equivalence problem. This reduction leads to a faster solver for the code equivalence problem, especially when the finite field size is large. The authors also demonstrate a substantial reduction in signature size compared to the LESS submission, achieving signatures around 2 KB or less, which are among the smallest in the code-based setting. The paper contributes to the field of post-quantum cryptography, particularly in the area of digital signatures based on linear codes.