Low-rank parity-check codes over Galois rings
- PDF / 630,926 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 204 Views
Low-rank parity-check codes over Galois rings Julian Renner1 · Alessandro Neri1
· Sven Puchinger2
Received: 20 June 2020 / Revised: 12 November 2020 / Accepted: 17 November 2020 © The Author(s) 2020
Abstract Low-rank parity-check (LRPC) codes are rank-metric codes over finite fields, which have been proposed by Gaborit et al. (Proceedings of the workshop on coding and cryptography WCC, vol 2013, 2013) for cryptographic applications. Inspired by a recent adaption of Gabidulin codes to certain finite rings by Kamche et al. (IEEE Trans Inf Theory 65(12):7718– 7735, 2019), we define and study LRPC codes over Galois rings—a wide class of finite commutative rings. We give a decoding algorithm similar to Gaborit et al.’s decoder, based on simple linear-algebraic operations. We derive an upper bound on the failure probability of the decoder, which is significantly more involved than in the case of finite fields. The bound depends only on the rank of an error, i.e., is independent of its free rank. Further, we analyze the complexity of the decoder. We obtain that there is a class of LRPC codes over a Galois ring that can decode roughly the same number of errors as a Gabidulin code with the same code parameters, but faster than the currently best decoder for Gabidulin codes. However, the price that one needs to pay is a small failure probability, which we can bound from above. Keywords Galois rings · Low-rank parity-check codes · Rank-metric codes · Algebraic coding theory Mathematics Subject Classification 11T71
Communicated by I. Landjev.
B
Alessandro Neri [email protected] Julian Renner [email protected] Sven Puchinger [email protected]
1
Institute for Communications Engineering, Technical University of Munich (TUM), Münich, Germany
2
Department of Applied Mathematics and Computer Science, Technical University of Denmark (DTU), Lyngby, Denmark
123
J. Renner et al.
1 Introduction Rank-metric codes are sets of matrices whose distance is measured by the rank of their difference. Over finite fields, the codes have found various applications in network coding, cryptography, space-time coding, distributed data storage, and digital watermarking. The first rank-metric codes were introduced in [6,9,22] and are today called Gabidulin codes. Motivated by cryptographic applications, Gaborit et al. introduced low-rank parity-check (LRPC) in [1,10]. They can be seen as the rank-metric analogs of low-density parity-check codes in the Hamming metric. LRPC codes have since had a stellar career, as they are already the core component of a second-round submission to the currently running NIST standardization process for post-quantum secure public-key cryptosystems [17]. They are suitable in this scenario due to their weak algebraic structure, which prevents efficient structural attacks. Despite this weak structure, the codes have an efficient decoding algorithm, which in some cases can decode up to the same decoding radius as a Gabidulin code with the same parameters, or even beyond [1]. A drawback is that for random errors
Data Loading...
