Bounded-Degree Low-Rank Parity-Check Codes
Ermes Franch, Chunlei Li · IEEE Transactions on Information Theory · 2025
Low-rank parity-check (LRPC) codes are the rank-metric analogue of low-density parity-check codes and they found important applications in code-based cryptography. In this paper we investigate a sub-family of LRPC codes, which have a parity-check matrix defined over a subspace${\mathcal {V}}_{\alpha,d}=\langle 1,\alpha, \ldots, \alpha ^{d-1} \rangle _{\mathbb {F}_{q}}\subsetneq \mathbb {F}_{q^{m}} $, where$\mathbb {F}_{q^{m}}$is the finite field of$q^{m}$elements,$\alpha \in \mathbb {F}_{q^{m}}$is an element not in any proper subfield of$\mathbb {F}_{q^{m}}$, and d is a positive integer significantly smaller than m. These codes are termed bounded-degree LRPC (BD-LRPC) codes. BD-LRPC codes are the same as the standard LRPC codes of density 2 when the degree$d=2$, while for degree$d\gt 2$they constitute a proper subset of LRPC codes of density d. Exploiting the structure of${\mathcal {V}}_{\alpha,d}$, the BD-LRPC codes of degree d can uniquely correct errors of rank weight r when$n-k \geq r + u$for certain$u \geq 1$, in contrast to the condition$n-k\geq dr$required for the standard LRPC codes. This underscores the superior decoding capability of the BD-LRPC codes. Moreover, as the code length$n\rightarrow \infty $, when$n/m\rightarrow 0$, the BD-LRPC codes with a code rate of$R=k/n$can be uniquely decodable with radius$\rho =r/n$approaching the Singleton bound$1-R$by letting$\epsilon =u/n\rightarrow 0$; and when$n/m$is a constant, the BD-LRPC codes can have unique decoding radius$\rho = 1-R-\epsilon $for a small$\epsilon $, allowing for$\rho \gt (1-R)/2$with properly chosen parameters. This superior decoding capability is theoretically proved for the case$d=2$and confirmed by experimental results for$d\gt 2$.