Generic Decoding in the Sum-Rank Metric

DOI10.1109/TIT.2022.3167629MaRDI QIDQ5096972zbMATH OpenFDO

Authors Sven Puchinger, Julian Renner, Johan Rosenkilde

Publication date 19 August 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

codes in sum-rank metricgeneric decoding algorithm

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.

Cited in

(16)

• Duals of linearized Reed-Solomon codes
• On the hardness of the Lee syndrome decoding problem
• S-semantics -- an example
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory
• Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes
• Distinguishing and recovering generalized linearized Reed-Solomon codes
• On decoding high-order interleaved sum-rank-metric codes
• Fast decoding of interleaved linearized Reed-Solomon codes and variants
• Multilayer crisscross error and erasure correction
• The geometry of covering codes in the sum-rank metric
• Bounds on sphere sizes in the sum-rank metric and coordinate-additive metrics
• On the generalizations of the rank metric over finite chain rings
• The blockwise rank syndrome learning problem and its applications to cryptography
• A zero-knowledge proof for the syndrome decoding problem in the Lee metric
• Invariants for sum-rank metric codes
• HQC beyond the standard: ciphertext compression and refined DFR analysis

This page was built for publication: Generic Decoding in the Sum-Rank Metric

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