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

Kurzfassung

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.