Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The paper analyzes the security of Generalized Skew Reed-Solomon (GSRS) and Generalized Linearized Reed-Solomon (GLRS) codes, which are promising candidates for code-based cryptography due to their maximum error-decoding radius. The authors demonstrate that GSRS and GLRS codes can be efficiently distinguished from random codes using a square code method, effectively breaking their security for a wide range of parameters. They also provide transformations between GSRS and GLRS codes, clarifying their algebraic relationship.
Turns out, Generalized Skew and Linearized Reed-Solomon codes, despite their promise for code-based crypto, are vulnerable to a square code distinguisher, shattering hopes for smaller key sizes.
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.