Hörmann, Felicitas and Bartz, Hannes (2023) Fast Gao-like Decoding of Horizontally Interleaved Linearized Reed-Solomon Codes. In: 11th International Workshop on Code-Based Cryptography, CBCrypto 2023, pp. 14-34. Springer. CBCrypto 2023: International Workshop on Code-Based Cryptography, 2023-04-22 - 2023-04-23, Lyon, France. doi: 10.1007/978-3-031-46495-9_2. ISBN 978-303146494-2. ISSN 0302-9743.
PDF
345kB |
Abstract
Both horizontal interleaving as well as the sum-rank metric are currently attractive topics in the field of code-based cryptography, as they could mitigate the problem of large key sizes. In contrast to vertical interleaving, where codewords are stacked vertically, each codeword of a horizontally s-interleaved code is the horizontal concatenation of s codewords of s component codes. In the case of horizontally interleaved linearized Reed-Solomon (HILRS) codes, these component codes are chosen to be linearized Reed-Solomon (LRS) codes. We provide a Gao-like decoder for HILRS codes that is inspired by the respective works for non-interleaved Reed-Solomon and Gabidulin codes. By applying techniques from the theory of minimal approximant bases, we achieve a complexity of O(s^{2.373} n^{1.635} operations in F_{q^m}, where O() neglects logarithmic factors, s is the interleaving order and n denotes the length of the component codes. For reasonably small interleaving order s << n, this is subquadratic in the component-code length n and improves over the only known syndrome-based decoder for HILRS codes with quadratic complexity. Moreover, it closes the performance gap to vertically interleaved LRS codes for which a decoder of complexity O(s^{2.373} n^{1.635} is already known. We can decode beyond the unique-decoding radius and handle errors of sum-rank weight up to (s/s+1)(n-k) for component-code dimension k. We also give an upper bound on the failure probability in the zero-derivation setting and validate its tightness via Monte Carlo simulations.
Item URL in elib: | https://elib.dlr.de/196630/ | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Document Type: | Conference or Workshop Item (Speech) | ||||||||||||
Additional Information: | F. Hörmann and H. Bartz acknowledge the financial support by the Federal Ministry of Education and Research of Germany in the programme of “Souverän. Digital. Vernetzt.” Joint project 6 G-RIC, Project Identification Number 16KISK022. | ||||||||||||
Title: | Fast Gao-like Decoding of Horizontally Interleaved Linearized Reed-Solomon Codes | ||||||||||||
Authors: |
| ||||||||||||
Date: | 2023 | ||||||||||||
Journal or Publication Title: | 11th International Workshop on Code-Based Cryptography, CBCrypto 2023 | ||||||||||||
Refereed publication: | Yes | ||||||||||||
Open Access: | Yes | ||||||||||||
Gold Open Access: | No | ||||||||||||
In SCOPUS: | Yes | ||||||||||||
In ISI Web of Science: | No | ||||||||||||
DOI: | 10.1007/978-3-031-46495-9_2 | ||||||||||||
Page Range: | pp. 14-34 | ||||||||||||
Publisher: | Springer | ||||||||||||
Series Name: | Lecture Notes in Computer Science | ||||||||||||
ISSN: | 0302-9743 | ||||||||||||
ISBN: | 978-303146494-2 | ||||||||||||
Status: | Published | ||||||||||||
Keywords: | Gao-like Decoding, Horizontal Interleaving, Linearized Reed-Solomon Codes, Sum-Rank Metric, Code-Based Cryptography, Minimal Approximant Bases | ||||||||||||
Event Title: | CBCrypto 2023: International Workshop on Code-Based Cryptography | ||||||||||||
Event Location: | Lyon, France | ||||||||||||
Event Type: | international Conference | ||||||||||||
Event Start Date: | 22 April 2023 | ||||||||||||
Event End Date: | 23 April 2023 | ||||||||||||
HGF - Research field: | Aeronautics, Space and Transport | ||||||||||||
HGF - Program: | Space | ||||||||||||
HGF - Program Themes: | Communication, Navigation, Quantum Technology | ||||||||||||
DLR - Research area: | Raumfahrt | ||||||||||||
DLR - Program: | R KNQ - Communication, Navigation, Quantum Technology | ||||||||||||
DLR - Research theme (Project): | R - Project Cybersecurity for Autonomous and Networked Systems [KNQ] | ||||||||||||
Location: | Oberpfaffenhofen | ||||||||||||
Institutes and Institutions: | Institute of Communication and Navigation > Satellite Networks | ||||||||||||
Deposited By: | Hörmann, Felicitas | ||||||||||||
Deposited On: | 21 Aug 2023 15:40 | ||||||||||||
Last Modified: | 24 Apr 2024 20:56 |
Repository Staff Only: item control page