Paper 2025/668

(Interleaved) Extended Gabidulin Codes, More Analysis on Blockwise Rank Decoding Problem, and Their Applications to Cryptosystems

Abstract

In this paper, we investigate the Extended Gabidulin (EG) codes and the Interleaved EG (IEG) codes, conduct more analysis on the Blockwise Rank Decoding (BRD) problem, and obtain efficient rank-based cryptosystems. First, we develop a general decoding algorithm for the (I)EG codes by solving the Linear Reconstruction (LR) problem. We find that the (I)EG codes can be probabilistically decoded by Welch-Berlekamp like algorithm, can achieve an arbitrarily small decoding failure rate, and can decode up to the rank Gilbert-Varshamov bound (even close to the minimal distance). Our conclusion intrinsically shows that it is not necessary to require that the generator be linearly independent as Gabidulin codes for designing decodable codes from $q$-polynomials. An interesting and important byproduct is that we demonstrate that decoding interleaved Gabidulin codes can be achieved deterministically by solving the LR problem. It has long been believed that there are only probabilistic decoding algorithms for interleaved Gabidulin codes (IEEE TIT 2011, DCC 2014, DCC 2024). Second, we propose the Blockwise Puncturing (BP) approach for solving the BRD problem (Asiacrypt 2023, IEEE TIT 2025). For this purpose, we derive a tight upper bound of independent equations in the MM modeling for general blocks, which further addresses an open question in (Asiacrypt 2023, IEEE TIT 2025, PQC 2024). We find that the BP approach can speed up the MM modeling. When the proposed approach is applied to the BRD problem used in existing rank-based cryptosystems, such as RQC and ROLLO (IEEE TIT 2025, PQC 2024), some parameters sets are lower than the practical security strength, and the security loss is up to 25 bits; nevertheless, the schemes still preserve the claimed security level. This work further supports the hardness of the BRD problem and enhances the security and performance of cryptosystems based on the BRD problem. Third, we apply the EG codes to the structured rank decoding encryption, namely RQC based on the BRD problem (Asiacrypt 2023, IEEE TIT 2025), and obtain the Bolckwise RQC with the EG codes (BRE). We find that the gain of using the EG codes in decoding capacity outweighs the complexity loss in solving the BRD problem with the BP approach, which still makes it possible to design more efficient schemes. As a result, BRE features a more attractive size with a bandwidth of about 1.6 KB for 128-bit security. Overall, BRE outperforms Hamming metric ones of NIST PQC Round 4 submissions, such as HQC, BIKE, and Classic McEliece, in terms of bandwidth, especially about 76% more compact than HQC selected by the NIST PQC. Fourth, we apply the EG codes to the unstructured rank decoding encryption, namely NH-Multi-UR-AG (IEEE TIT 2024), with the homogeneous errors, and obtain the Homogeneous Unstructured Rank decoding encryption with the EG codes (HURE). The bandwidth of HURE is about 6.7 KB for 128-bit security, which is slightly shorter than NH-Multi-UR-AG. This bandwidth also outperforms lattice-based unstructured PKEs, namely FrodoKEM and Scloud$^{+}$, respectively about 64% and 45% more compact. We intrinsically show that it is sufficient to construct an efficient unstructured PKE scheme by only homogeneous errors, without non-homogeneous errors. This application benefits from that we derive the concise DFR for the EG codes, which allows to choose flexible parameters.

Note: In the previous version, the complexity of the MM modeling with the BP approach is impractical for the BRD and NHRD problems because we used the maximal equations as independent equations. The complexity is underestimated.  In this updated version, we (1) Only consider the complexity of the BRD problem with the BP approach. We conduct an estimation of independent equations for general blocks. Some parameter sets of the schemes based on the BRD problem are lower than the practical security strength, but the schemes still preserve the claimed security level. (2) Delete the analysis of the NHRD problem and leave it as future and independent work. (3) Show additionally that the homogeneous errors can also lead to an efficient unstructured PKE with the EG codes (HURE).