Distinguishing and recovering generalized linearized Reed-Solomon codes

DOI10.1007/978-3-031-29689-5_1zbMATH Open1522.94111arXiv2304.00627MaRDI QIDQ6132742FDOQ6132742

Authors: Felicitas Hörmann, Hannes Bartz, Anna-Lena Horlemann 

Publication date: 17 August 2023

Published in: Code-Based Cryptography (Search for Journal in Brave)

Abstract: We study the distinguishability of linearized Reed-Solomon (LRS) codes by defining and analyzing analogs of the square-code and the Overbeck distinguisher for classical Reed-Solomon and Gabidulin codes, respectively. Our main results show that the square-code distinguisher works for generalized linearized Reed-Solomon (GLRS) codes defined with the trivial automorphism, whereas the Overbeck-type distinguisher can handle LRS codes in the general setting. We further show how to recover defining code parameters from any generator matrix of such codes in the zero-derivation case. For other choices of automorphisms and derivations simulations indicate that these distinguishers and recovery algorithms do not work. The corresponding LRS and GLRS codes might hence be of interest for code-based cryptography.

Full work available at URL: https://arxiv.org/abs/2304.00627

Recommendations

• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• The non-gap sequence of a subcode of a generalized Reed-Solomon code
• Identifiers for MRD-codes
• On the dimension and structure of the square of the dual of a Goppa code
• Duals of linearized Reed-Solomon codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cites Work

• MacWilliams extension theorems and the local-global property for codes over Frobenius rings
• Structural attacks for public key cryptosystems based on Gabidulin codes
• How to mask the structure of codes for a cryptographic use
• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Title not available (Why is that?)
• On the edge-independence number and edge-covering number for regular graphs
• Vandermonde and Wronskian matrices over division rings
• Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes
• Public Key Cryptography - PKC 2006
• Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis
• Progress in Cryptology – Mycrypt 2005
• Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring
• A Unified Construction of Space–Time Codes With Optimal Rate–Diversity Tradeoff
• Hamming and simplex codes for the sum-rank metric
• Extension of Overbeck's attack for Gabidulin-based cryptosystems
• Attacks and counter-attacks on the GPT public key cryptosystem
• Duals of linearized Reed-Solomon codes
• Sum-rank product codes and bounds on the minimum distance
• Twisted linearized Reed-Solomon codes: a skew polynomial framework
• Generic Decoding in the Sum-Rank Metric

This page was built for publication: Distinguishing and recovering generalized linearized Reed-Solomon codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132742)