elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Fast Gao-like Decoding of Horizontally Interleaved Linearized Reed-Solomon Codes

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.

[img] 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:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Hörmann, FelicitasUNSPECIFIEDhttps://orcid.org/0000-0003-2217-9753UNSPECIFIED
Bartz, HannesUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
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

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.