Distinguishers for Skew and Linearized Reed-Solomon Codes

Computer Science > Cryptography and Security [Submitted on 14 Apr 2026] Distinguishers for Skew and Linearized Reed-Solomon Codes 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. Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT) Cite as: arXiv:2604.12954 [cs.CR]   (or arXiv:2604.12954v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.12954 Focus to learn more Submission history From: Felicitas Hörmann [view email] [v1] Tue, 14 Apr 2026 16:50:44 UTC (62 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.IT math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)