Anna-Lena Horlemann

Hassan Ou-azzou, Anna-Lena Horlemann

We study the equivalence of families of polycyclic codes associated with polynomials of the form $x^n - a_{n-1}x^{n-1} - \ldots - a_1x - a_0$ over a finite field. We begin with the specific case of polycyclic codes associated with a trinomial $x^n - a_{\ell} x^{\ell} - a_0$ (for some $0< \ell <n$), which we refer to as \textit{$\ell$-trinomial codes}, after which we generalize our results to general polycyclic codes. We introduce an equivalence relation called \textit{$n$-equivalence}, which extends the known notion of $n$-equivalence for constacyclic codes \cite{Chen2014}. We compute the number of $n$-equivalence classes %, $ N_{(n,\ell)}$, for this relation and provide conditions under which two families of polycyclic (or $\ell$-trinomial) codes are equivalent. In particular, we prove that when $\gcd(n, n-\ell) = 1$, any $\ell$-trinomial code family is equivalent to a trinomial code family associated with the polynomial $x^n - x^{\ell} - 1$. Finally, we focus on $p^{\ell}$-trinomial codes of length $p^{\ell+r}$, where $p$ is the characteristic of $\mathbb{F}_q$ and $r$ an integer, and provide some examples as an application of the theory developed in this paper.

Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder et al.

Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field.

Felicitas Hörmann, Anna-Lena Horlemann

Generalized Reed-Solomon (GRS) and Gabidulin codes have been proposed for various code-based cryptosystems, though most such schemes without elaborate disguising techniques have been successfully attacked. Both code classes are prominent examples of the isometric families of (generalized) skew and linearized Reed-Solomon ((G)SRS and (G)LRS) codes which are obtained as evaluation codes from skew polynomials. Both GSRS and GLRS codes share the advantage of achieving the maximum possible error-decoding radius and thus promise smaller key sizes than e.g. Classic McEliece. We investigate whether these generalizations can avoid the known structural attacks on GRS and Gabidulin codes. In particular, we prove that both GSRS and GLRS codes decompose into GRS subcodes and are thus efficiently distinguishable from random codes with a square code method. This applies to all parameters for which the code length $n$ and its dimension $k$ over the field $\mathbb{F}_{q^m}$ satisfy $m + 1 < k < n - \tfrac{1}{2} (m^2 + 3m)$. The distinguishability extends to GSRS and GLRS codes with Hamming-isometric disguising. We further relate these findings to existing distinguishers for GRS, Gabidulin, and LRS codes, and extend known results on duals of SRS and LRS codes to the generalized setting allowing nonzero column multipliers. Finally, we provide explicit transformations between GSRS and GLRS codes, clarifying the algebraic relationship between the skew and linearized frameworks.

Violetta Weger, Karan Khathuria, Anna-Lena Horlemann et al.

In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the $3$-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.