On decoding high-order interleaved sum-rank-metric codes

DOI10.1007/978-3-031-29689-5_6zbMATH Open1522.94129arXiv2303.17454OpenAlexW4361763391WikidataQ122658559 ScholiaQ122658559MaRDI QIDQ6174646FDOQ6174646

Authors: Thomas Jerkovits, Felicitas Hörmann, Hannes Bartz 

Publication date: 17 August 2023

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

Abstract: We consider decoding of vertically homogeneous interleaved sum-rank-metric codes with high interleaving order $s$, that are constructed by stacking $s$ codewords of a single constituent code. We propose a Metzner--Kapturowski-like decoding algorithm that can correct errors of sum-rank weight $t<=d-2$, where $d$ is the minimum distance of the code, if the interleaving order $s>t$ and the error matrix fulfills a certain rank condition. The proposed decoding algorithm generalizes the Metzner--Kapturowski(-like) decoders in the Hamming metric and the rank metric and has a computational complexity of $ildeO(max(n^3,n^{2}s))$ operations in $mathbb{F}_{q^m}$, where $n$ is the length of the code. The scheme performs linear-algebraic operations only and thus works for any interleaved linear sum-rank-metric code. We show how the decoder can be used to decode high-order interleaved codes in the skew metric. Apart from error control, the proposed decoder allows to determine the security level of code-based cryptosystems based on interleaved sum-rank metric codes.

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

Recommendations

• Encoding and decoding of several optimal rank metric codes
• Row reduction applied to decoding of rank-metric and subspace codes
• New technique for decoding codes in the rank metric and its cryptography applications
• Hamming and simplex codes for the sum-rank metric
• Codes in the sum-rank metric: fundamentals and applications

Mathematics Subject Classification ID

Decoding (94B35)

Cites Work

• Elliptic periods for finite fields
• Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring
• Coding for Combined Block–Symbol Error Correction
• LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
• Generic Decoding in the Sum-Rank Metric
• A general decoding technique applicable to replicated file disagreement location and concatenated code decoding
• Performance of a general decoding technique over the class of randomly chosen parity check codes
• A decoding algorithm with restrictions for array codes
• Interleaved Prange: a new generic decoder for interleaved codes

Cited In (2)

• Fast Gao-like Decoding of Horizontally Interleaved Linearized Reed-Solomon Codes
• Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes

This page was built for publication: On decoding high-order interleaved sum-rank-metric codes

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