Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes

Abstract

In this paper, we initiate the study of the Rank Decoding (RD) problem and LRPC codes with blockwise structures in rank-based cryptosystems. First, we introduce the blockwise errors ($\ell$-errors) where each error consists of $\ell$ blocks of coordinates with disjoint supports, and define the blockwise RD ($\ell$-RD) problem as a natural generalization of the RD problem whose solutions are $\ell$-errors (note that the standard RD problem is actually a special $\ell$-RD problem with $\ell =1$). We adapt the typical attacks on the RD problem to the $\ell$-RD problem, and find that the blockwise structures do not ease the problem too much: the $\ell$-RD problem is still exponentially hard for appropriate choices of $\ell >1$. Second, we introduce blockwise LRPC ($\ell$-LRPC) codes as generalizations of the standard LPRC codes whose parity-check matrices can be divided into $\ell$ sub-matrices with disjoint supports, i.e., the intersection of two subspaces generated by the entries of any two sub-matrices is a null space, and investigate the decoding algorithms for $\ell$-errors. We find that the gain of using $\ell$-errors in decoding capacity outweighs the complexity loss in solving the $\ell$-RD problem, which makes it possible to design more efficient rank-based cryptosystems with flexible choices of parameters.

As an application, we show that the two rank-based cryptosystems submitted to the NIST PQC competition, namely, RQC and ROLLO, can be greatly improved by using the ideal variants of the $\ell$-RD problem and $\ell$-LRPC codes. Concretely, for 128-bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece.

1 Introduction

Since traditional cryptographic schemes based on number theoretic assumptions are at risk from the possible attacks using quantum computers, the design of post-quantum cryptosystems, such as code-based cryptosystems, has become the consensus of industry and academia. Last year, three code-based cryptosystems using the Hamming metric codes, namely, BIKE, Classic McEliece, and HQC, had been selected to the fourth round of NIST post-quantum standardization process for future standardization [35]. As a nice alternative to Hamming metric code-based cryptography, code-based cryptography using the rank metric, namely, rank-based cryptography, is more efficient in computational efficiency and bandwidth, and deserves further research as encouraged by NIST [34].

$\mathbb {F}_{q^m}$-Linear Codes with Rank Metric and Rank Decoding Problem. Codes used in rank-based cryptography are $\mathbb F_{q^m}$-linear codes with rank metric over a degree m extension field $\mathbb {F}_{q^m}$ of $\mathbb {F}_{q}$. Let $\boldsymbol{\alpha }= (\alpha _1,\alpha _2,\dots ,\alpha _m) \in \mathbb {F}_{q^m}^m$ be a basis of $\mathbb {F}_{q^m}$ viewed as an m-dimensional vector space over $\mathbb {F}_{q}$. Then, any $\boldsymbol{e}=(e_1,e_1,\dots ,e_n)\in \mathbb {F}_{q^m}^n$ has an associated matrix $\textrm{Mat}(\boldsymbol{e})\in \mathbb {F}_q^{m\times n}$ such that $\boldsymbol{e}= \boldsymbol{\alpha }\textrm{Mat}(\boldsymbol{e})$. The rank weight $\Vert \boldsymbol{e}\Vert _\textrm{R}$ of $\boldsymbol{e}$ is defined as the rank of $\textrm{Mat}(\boldsymbol{e})$. The support Supp($\boldsymbol{e}$) of $\boldsymbol{e}$ is the $\mathbb {F}_q$-linear subspace of $\mathbb {F}_{q^m}$ spanned by the coordinates of $\boldsymbol{e}$. It follows from definition that $\Vert \boldsymbol{e}\Vert _\textrm{R}$ equals to the dimension of $\textrm{Supp}(\boldsymbol{e})$. The set of errors of length n and weight r is denoted by $\mathcal {S}_{r}^{n}$. An $\mathbb F_{q^m}$-linear code ($[n,k]_{q^m}$) with rank metric of length n and dimension k is a dimension k subspace of $\mathbb F_{q^m}^n$, which can be represented by a generator matrix of size $k\times n$ or a parity-check matrix of size $(n-k)\times n$ over $\mathbb {F}_{q^m}$.

Let $\boldsymbol{G}$ be the generator matrix of a random $[n,k]_{q^m}$-linear code, $\boldsymbol{y}\in \mathbb {F}_{q^m}^{n}$, and $r \in \mathbb {N}$. The Rank Decoding (RD) problem is to find $\boldsymbol{x} \in \mathbb {F}_{q^m}^k$ and $\boldsymbol{e}\in \mathcal {S}_{r}^n$ such that $\boldsymbol{y}=\boldsymbol{x}\boldsymbol{G}+\boldsymbol{e}$. Although the RD problem is not shown to be NP-hard, it is very close to the Hamming metric decoding problem which is NP-hard [23], and can be seen as a structured version of the MinRank problem which is also NP-hard [17]. Moreover, after more than three decades of study, the best known algorithms for solving the RD problem are all exponential. This makes the RD problem a promising hard problem to construct secure cryptosystems.

Rank-Based Cryptography. The first rank-based cryptosystem, known as the GPT cryptosystem [19], was based on Gabidulin codes [18] which have analogous structures to Reed-Solomon codes. The GPT cryptosystem and its early variants were broken by Overbeck attack [38], in the much same way as McEliece schemes based on Reed-Solomon codes were attacked in [16, 39]. The recent variant [28] was analyzed with some insecure parameters region being found in [15, 24]. As these attacks [15, 16, 24, 38, 39] mainly expose the security flaws of the GPT cryptosystem by exploiting the strong algebraic structure of Gabidulin codes, it is still possible to construct secure and efficient rank-based cryptosystems.

A very significant step was using the Low Rank Parity Check (LRPC) codes [4, 20] and the Gabidulin codes to build cryptosystems [2, 20, 22, 29, 30], which can be viewed as rank metric analogues of the MDPC cryptosystem [33], NTRU [25], or Alekhnovich [1]. Four cryptosystems of this kind, namely, RQC [30], Lake, Locker [29], and Ouroboros-R [2], were submitted to the NIST PQC standardization process in 2017, with the latter three being merged into ROLLO in the second round. The combinatorial attacks [5, 21, 37] were once considered to be the most efficient attacks against the parameters region of RQC and ROLLO. However, it turned out later that the improved dedicated algebraic attacks [7, 9] could greatly reduce the concrete security of RQC and ROLLO. This is the main reason that RQC and ROLLO were not selected to the third round of the NIST PQC standardization process. New parameter sets [2, 29, 30] for RQC and ROLLO were proposed to provide adequate security against algebraic attacks. As the new key and ciphertext sizes of RQC and ROLLO remain competitive, NIST encourages further research on rank-based cryptography [34].

1.1 Our Contribution

We initiate the study of the RD problem and LRPC codes with blockwise structures to design secure and efficient rank-based cryptosystems. First, we introduce the blockwise errors ($\ell$-errors) where each error consists of $\ell$ blocks of coordinates with disjoint supports, and define the blockwise RD ($\ell$-RD) problem as a natural generalization of the RD problem whose solutions are $\ell$-errors. Notably, the standard RD problem can be seen as a special $\ell$-RD problem with $\ell =1$, or equivalently the $\ell$-RD problem can be treated as a structured RD problem. Since the attacks may benefit from the blockwise structure, the $\ell$-RD problem is inherently not harder than the standard one. Fortunately, this structure does not ease the problem too much: we only observe a reduction about $\ell$ times in the exponent to solve the $\ell$-RD problem by carefully examining the typical attacks for the standard RD problem, implying that the $\ell$-RD problem is still exponentially hard for appropriate choices of constant $\ell >1$.

Second, we introduce the blockwise LRPC ($\ell$-LRPC) codes as generalizations of the standard LPRC codes whose parity-check matrices can be divided into $\ell$ sub-matrices with disjoint supports, i.e., the intersection of two subspaces generated by the entries of any two sub-matrices is a null space, and investigate the decoding algorithms for $\ell$-errors. We find that the decoding algorithm can also benefit from the blockwise structure: the decoding capacity can be significantly improved by a factor of $\ell$. In particular, a suitably defined $[n,k]_{q^m}$ $\ell$-LRPC code can actually decode an $\ell$-error with weight up to $(n-k)/2$, which achieves the decoding capacity of rank codes of optimal distance. This makes it possible to design more efficient rank-based cryptosystems with flexible choices of parameters, by making a tradeoff between the hardness of the $\ell$-RD problem and the decoding capacity of the $\ell$-LPRC codes.

Finally, we show that the two rank-based cryptosystems submitted to the NIST PQC competition, namely, RQC and ROLLO, can be greatly improved by using the ideal variants of the $\ell$-RD problem and $\ell$-LRPC codes. Concretely, for 128-bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece. A detailed comparison with related works is given in Subsect. 1.2.

1.2 Technical Overview

Recall that the set of errors of length n and weight r is denoted by $\mathcal {S}_{r}^{n}$. By definition, all n coordinates of an error $\boldsymbol{e} \in \mathcal {S}_{r}^{n}$ belong to the same support of dimension r. In particular, let $\boldsymbol{\varepsilon }= (\varepsilon _{1},\ldots ,\varepsilon _{r})\in \mathbb {F}_{q^m}^{r}$ be a basis of the support $\textrm{Supp}(\boldsymbol{e})$, then there is an $r\times n$ coefficient matrix $\boldsymbol{C}$ such that $\boldsymbol{e} = \boldsymbol{\varepsilon }\boldsymbol{C}$.

The Blockwise Errors ($\ell$-errors). Let $\boldsymbol{n} = (n_1,\dots ,n_\ell )$ and $\boldsymbol{r} =(r_1,\dots ,r_\ell )$ be vectors of positive integers. We say that an error $\boldsymbol{e} \in \mathcal {S}_{r}^{n}$ with $n =\sum _{i=1}^\ell n_i$ and $r =\sum _{i=1}^\ell r_i$ is an $\ell$-error with parameters $\boldsymbol{n}$ and $\boldsymbol{r}$ if it can be divided into $\ell$ sub-vectors $\boldsymbol{e}= (\boldsymbol{e}_1,\boldsymbol{e}_2,\dots ,\boldsymbol{e}_\ell )$ such that 1) the sub-vector $\boldsymbol{e}_i \in \mathbb {F}_{q^m}^{n_i}$ has weight $r_i$ for all $i\in \{1..\ell \}$; and 2) the supports of these sub-vectors are mutually disjoint, namely, $\textrm{Supp}(\boldsymbol{e}_i)\,\cap \, \textrm{Supp}(\boldsymbol{e}_j) = \{0\}$ for all $i\ne j$. Denote $\mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ as the set of blockwise errors with parameters $\boldsymbol{n}$ and $\boldsymbol{r}$. By definition, the set $\mathcal {S}_{r}^{n}$ is exactly the set $\mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ of $\ell$-errors with $\ell =1$. For $\ell > 1$, $\mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ is a proper subset of $\mathcal {S}_{r}^{n}$. In particular, for any $\boldsymbol{e} = (\boldsymbol{e}_1, \boldsymbol{e}_2, \ldots , \boldsymbol{e}_\ell )\in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$, if we let $\boldsymbol{\varepsilon }_i = (\varepsilon _{i1}, \varepsilon _{i2}, \ldots ,\varepsilon _{ir_i})\in \mathbb {F}_{q^m}^{r_i}$ be a basis of $\textrm{Supp}(\boldsymbol{e}_i)$, then the coefficient matrix $\boldsymbol{C}$ of $\boldsymbol{e}$ w.r.t. the basis $\boldsymbol{\varepsilon }= (\boldsymbol{\varepsilon }_1, \boldsymbol{\varepsilon }_2, \ldots , \boldsymbol{\varepsilon }_\ell )$, i.e., $\boldsymbol{e}= \boldsymbol{\varepsilon }\boldsymbol{C}$, has a special block-diagonal form:

$$\begin{aligned} \boldsymbol{C} = \begin{pmatrix} \boldsymbol{C}_1 &{} \boldsymbol{0} &{} \boldsymbol{0}&{} \boldsymbol{0}\\ \boldsymbol{0} &{} \boldsymbol{C}_2 &{} \boldsymbol{0}&{}\boldsymbol{0}\\ \vdots &{} \vdots &{} \ddots &{}\vdots \\ \boldsymbol{0} &{} \boldsymbol{0} &{}\boldsymbol{0} &{}\boldsymbol{C}_\ell \end{pmatrix}\in \mathbb {F}_{q}^{r\times n} \end{aligned}$$

(1)

where $\boldsymbol{e}_i = \varepsilon _i \boldsymbol{C}_i$. As we will show later, the attacks can benefit from the block-diagonal structure.

The Blockwise RD ($\ell$-RD) Problem. We define the $\ell$-RD problem as a natural generalization of the RD problem whose solutions are $\ell$-errors. Recall that the RD problem asks an algorithm given as inputs a generator matrix $\boldsymbol{G}$ of random $[n,k]_{q^m}$-linear code $\mathcal {C}$, a vector $\boldsymbol{y}\in \mathbb {F}_{q^m}^{n}$, and an integer $r \in \mathbb {N}$, outputs $\boldsymbol{x} \in \mathbb {F}_{q^m}^k$ and $\boldsymbol{e}\in \mathcal {S}_{r}^n$ such that $\boldsymbol{y}=\boldsymbol{x}\boldsymbol{G}+\boldsymbol{e}$. The RD problem can be solved by finding a codeword $\boldsymbol{e} \in \mathcal {S}_{r}^n$ in the $[n,k+1]_{q^m}$ extended code $\mathcal {C}_{\boldsymbol{y}}=\mathcal {C} + \langle \boldsymbol{y}\rangle$ of $\mathcal {C}$. Let $\boldsymbol{H}_{\boldsymbol{y}} \in \mathbb {F}_{q^m}^{(n-k-1)\times n}$ be the parity-check matrix of $\mathcal {C}_{\boldsymbol{y}}$. The problem can be further reduced to find an $\boldsymbol{e}\in \mathcal {S}_{r}^n$ such that $\boldsymbol{e}\boldsymbol{H}_{\boldsymbol{y}}^{\top }= \boldsymbol{\varepsilon }\boldsymbol{C}\boldsymbol{H}_{\boldsymbol{y}}^{\top } = \boldsymbol{0}$.

There are two main kinds of attacks for the RD problem, i.e., combinatorial attacks [5, 14, 21, 37] and algebraic attacks [7,8,9, 21]. The basic idea of the combinatorial attacks [5, 14, 21, 37] is to guess some unknown variables about the equations $\boldsymbol{y}=\boldsymbol{x}\boldsymbol{G}+\boldsymbol{e}$ or $\boldsymbol{e}\boldsymbol{H}_{\boldsymbol{y}}^{\top }= \boldsymbol{\varepsilon }\boldsymbol{C}\boldsymbol{H}_{\boldsymbol{y}}^{\top } = \boldsymbol{0}$ so that they can be directly solved by using Gaussian eliminations (note that number of equations are much less than that of the variables). The guess complexity is the main cost for the combinatorial attacks. In contrast, the algebraic attacks [7,8,9, 21] resort to establish sufficiently more equations using different algebraic properties such as the annulator polynomial, so that the error $\boldsymbol{e}$ can be directly found by solving those equations. The complexity of the algebraic attacks is mainly determined by the number of the unknown variables of those equations. By carefully investigating the typical attacks, we find that both combinatorial and algebraic attacks can benefit from the blockwise structures, the basic reason is that the coefficient matrix $\boldsymbol{C}$ for an $\ell$-error has a special block-diagonal form, which allows to greatly reduce the number of the unknown variables. The take-away message is that the best cost for solving the $\ell$-RD problem is roughly equal to the $\ell$-th square root of the cost for solving the standard RD problem (with the same parameters). This means that for appropriate choices of constant $\ell >1$ such as $\ell =2$ or 3 in our applications, the $\ell$-RD problem is still exponentially hard.

The Blockwise LRPC ($\ell$-LRPC) Codes. Let $\boldsymbol{H} \in \mathbb {F}_{q^m}^{(n-k)\times n}$ be the parity-check matrix of an $[n,k]_{{q^m}}$ LRPC code. The entries of $\boldsymbol{H}$ generate an $\mathbb {F}_q$-linear subspace F of dimension d (for simplicity, we call $\boldsymbol{H}$ a matrix of weight d and support F). Let $\boldsymbol{e} \in \mathcal {S}_{r}^{n}$ be an error of support E and let $\boldsymbol{s} = \boldsymbol{H}\boldsymbol{e}^{\top }$. Let EF be the product space of E and F, whose dimension is equal to rd with overwhelming probability when rd is sufficiently smaller than m. The decoding algorithm works by first recovering the product space EF using the support $\textrm{Supp}(\boldsymbol{s})$ of $\boldsymbol{s}$ (which requires the weight $\Vert \boldsymbol{s}\Vert _\textrm{R}$ is equal to the dimension of EF), then recovering the error support E from EF, and finally solving the linear equations $\boldsymbol{s} = \boldsymbol{H}\boldsymbol{e}^{\top }$ using E. The Decode Failure Rate (DFR) is about $q^{\Vert \boldsymbol{s}\Vert _\textrm{R}-(n-k)}=q^{rd-(n-k)}$, implying that an LPRC code of weight d can decode errors of weight up to $\frac{n-k}{d}$.

We define the blockwise LRPC ($\ell$-LRPC) codes as generalizations of the standard LPRC codes whose parity-check matrices can be divided by columns into $\ell$ sub-matrices with disjoint supports. Let $\boldsymbol{n} = (n_1,\dots ,n_\ell )$ and $\boldsymbol{d} = (d_1,\dots ,d_\ell )$ be vectors of positive integers and $k\in \mathbb {N}$. We say that an $[n,k]_{q^m}$ LRPC code is an $\ell$-LRPC code with parameters $n =\sum _{i=1}^\ell n_i$ and $d = \sum _{i=1}^\ell d_i$ if its parity-check matrix $\boldsymbol{H} \in \mathbb {F}_{q^m}^{(n-k)\times n}$ can be divided into $\ell$ sub-matrices $\boldsymbol{H}= (\boldsymbol{H}_1,\boldsymbol{H}_2,\cdots ,\boldsymbol{H}_\ell )$ such that 1) the sub-matrix $\boldsymbol{H}_i \in \mathbb {F}_{q^m}^{(n-k)\times n_i}$ has small weight $d_i$ for all $i\in \{1..\ell \}$; and 2) the supports $\{F_i = \textrm{Supp}(\boldsymbol{H}_i)\}$ of these sub-matrices are mutually disjoint, namely, $F_i\cap F_j = \{0\}$ for all $i\ne j$.

The decoding algorithm for $\ell$-LRPC codes works the same way as the one for standard LRPC codes. For traditional errors, an $\ell$-LRPC code has the same decoding capacity as a standard LRPC code. However, it is more powerful when decoding $\ell$-errors. This is because for an $\ell$-error $\boldsymbol{e}\in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$ with supports $(E_1,E_2,\ldots ,E_\ell )$ and $\boldsymbol{r} = (r_1,\dots ,r_\ell )$, the product space in consideration becomes $\sum _{i=1}^{\ell }E_iF_i$, whose dimension is upper bounded by $\sum _{i=1}^{\ell } r_id_i <rd$, where $r = \sum _{i=1}^{\ell } r_i$. This means that the $\ell$-LRPC code can decode an $\ell$-error with a much larger weight r. Formally, we have the following Theorem 1.1 (see the proofs in Sect. 4).

Theorem 1.1

When $d_1=d_2=\cdots =d_\ell$, the $\ell$-LRPC code allows to decode $\ell$-errors of weight up to $r=\sum _{j=1}^{\ell }r_j=\frac{n-k}{d_1}$. By setting $d_1=d_2=\cdots =d_\ell$= 2, it can decode $\ell$-errors of weight up to $\frac{n-k}{2}$.

Theorem 1.1 implies that when dealing with $\ell$-errors, the decoding capacity for the $\ell$-LRPC codes is $\ell$ times larger than that of the standard LRPC codes. For example, fixing $d=4$, $r=8$, and the DFR of $q^{32-n-k}$, an $[n,k]_{q^m}$ LRPC code can decode errors of weight 8, but an $[n,k]_{q^m}$ 2-LRPC codes with parameter $\boldsymbol{d}= (d_1,d_2)=(2,2)$ can decode $\ell$-errors with parameter $\boldsymbol{r}= (r_1,r_2)=(8,8)$ of weight up to $r = r_1 + r_2 = 16$.

Applications. By making a tradeoff between the hardness of the $\ell$-RD problem and the decoding capacity of the $\ell$-LRPC codes, it is possible to design more efficient and secure rank-based cryptosystems with flexible choices of parameters. In particular, the blockwise structures would lead to larger parameters to reserve the security, but the gain in decoding capacity still allows us to design more efficient cryptosystems. As an application, we show that both RQC and ROLLO cryptosystems can be greatly improved by using the ideal variants of the $\ell$-RD problem and $\ell$-LRPC codes. A brief comparison with related coded-based cryptosystems at the same 128-bit security is summarized in Table 1, which shows that our RQC is about 50% more compact than the original RQC, and has smaller sizes than the three code-based cryptosystems using the Hamming metric, namely, HQC, BIKE, and Classic McEliece.

Table 1. Comparisons of size and DFR for 128-bit security.

1.3 Other Related Works

The idea of using blockwise errors can be seen as an adaption of the LPN/LWE problem in rank metric [11]. Our blockwise codes are also related to the sum-rank metric codes [13], where the error is also divided into $\ell$ blocks and the sum-rank weight is defined as the sum of rank weight of each block. One main difference is that we explicitly require the $\ell$ blocks to have disjoint supports, which is very crucial for our results in this paper.

1.4 Organization

After some notations given in Sect. 2, we define the $\ell$-errors and analyze the complexity of solving the $\ell$-RD problem in Sect. 3. Section 4 defines the $\ell$-LRPC codes and analyzes decoding failure probability and error-correcting capability. In Sect. 5, we apply the ideal $\ell$-RD problem and the ideal $\ell$-LRPC codes to improve RQC and ROLLO. We conclude this paper in Sect. 6.

2 Notations

• We denote by $\mathbb {N}$ the set of positive integer numbers, q prime or prime power, and $\mathbb {F}_{q^m}$ an extension of degree m of the finite field $\mathbb {F}_{q}$.

• Let $\alpha \in \mathbb {F}_{q^m}$ be a primitive element and $\boldsymbol{\alpha }= (1,\alpha ,\ldots ,\alpha ^{m-1})$ be a basis of $\mathbb {F}_{q^m}$ viewed as an $\mathbb {F}_{q}$ vector space.

• Vectors (resp. matrices) are represented by lower-case (resp. upper-case) bold letters. We say that an algorithm is a PPT algorithm if it is a probabilistic polynomial-time algorithm.

• If $\mathcal {X}$ is a finite set, $x{\mathop {\leftarrow }\limits ^{\$}}\mathcal {X}$ (resp. $x{\mathop {\longleftarrow }\limits ^{\textsf{seed}}}\mathcal {X}$) denotes that x is chosen uniformly and randomly from the set $\mathcal {X}$ (resp. by a seed $\textsf{seed}$).

• For integers $a\le b$, let $\{a..b\}$ denote all integers from a to b.

• The number of $\mathbb {F}_{q}$-subspaces of dimension r of $\mathbb {F}_{q^m}$ is given by the Gaussian coefficient $\left[ \begin{array}{c} m \\ r \end{array}\right] _q=\prod _{i=0}^{r-1} \frac{q^m-q^i}{q^r-q^i} \approx q^{r(m-r)}.$

• The submatrix of a matrix $\boldsymbol{M}$ formed from the rows in I and columns in J is denoted by $\boldsymbol{M}_{I,J}$. When I (resp. J) consists of all the rows (resp. columns), we use the notation $\boldsymbol{M}_{*,J}$ (resp. $\boldsymbol{M}_{I,*}$).

• $|\boldsymbol{M}|$, $|\boldsymbol{M}|_{I,J}$, and $|\boldsymbol{M}|_{*,J}$ are the determinant of the matrix $\boldsymbol{M}$, the submatrix $\boldsymbol{M}_{I,J}$, and the submatrix $\boldsymbol{M}_{*,J}$, respectively.

• $\textrm{GL}_\eta (\mathbb {F}_{q})$ is a general linear group and represents the set of all invertible matrices of size $\eta$ over $\mathbb {F}_{q}$. The matrix $\boldsymbol{I}_r$ is the identity matrix of size r.

• The maximal minor $c_{T}$ of a matrix $\boldsymbol{C}$ of size $r\times n$ is the determinant of its submatrix $\boldsymbol{C}_{*,T}$ whose column indexes $T \subset \{1..n\}$ and $\#T = r$.

• Cauchy-Binet formula that computes the determinant of the product of $\boldsymbol{A} \in \mathbb {F}_{q^m}^{r\times n}$ and $\boldsymbol{B} \in \mathbb {F}_{q^m}^{n \times r}$ is expressed as $|\boldsymbol{A}\boldsymbol{B}| = \sum _{T\subset \{1..n\}, \#T = r}|\boldsymbol{A}|_{*,T}|\boldsymbol{B}|_{T,*}$.

• The Gaussian elimination of a $\mu \times \nu$ matrix of rank $\rho$ over an $\mathbb {F}_{q}$ has a complexity of $\mathcal {O}(\rho ^{\omega -2}\mu \nu )$ operations in $\mathbb {F}_{q}$, where $\omega$ is the exponent of matrix multiplication with $2\le \omega \le 3$ and a practical value is 2.81 when more than a few hundreds rows and columns.

• The complexities are estimated by operations in $\mathbb {F}_{q}$ if there is no ambiguity. All logarithms are of base 2.

3 The $\ell$-RD Problem and Its Complexity

In this section, we first introduce the blockwise errors ($\ell$-errors) and the blockwise RD ($\ell$-RD) problem in Subsect. 3.1. Then, to analyze the complexity of the $\ell$-RD problem, we refine a universal reduction from existing attacks on the RD problem and analyze the support and coefficient matrices of the $\ell$-error in Subsect. 3.2. Finally, we adapt the typical combinatorial and algebraic attacks to the $\ell$-RD problem in Subsects. 3.3, 3.4 and 3.5, and find that the $\ell$-errors do not ease the problem too much: the $\ell$-RD problem is still exponentially hard for appropriate choices of $\ell >1$.

3.1 The $\ell$-Errors and $\ell$-RD Problem

Let $\ell , k \in \mathbb {N}$. Let $\boldsymbol{n} = (n_1,\dots ,n_\ell )$ and $\boldsymbol{r} =(r_1,\dots ,r_\ell )$ be vectors of positive integers. Let $n=\sum _{i=1}^{\ell }n_i$ and $r=\sum _{i=1}^{\ell }r_i$. We first define the disjointness of multiple subspaces. We say that $\ell$ $\mathbb {F}_{q}$-subspaces $\{V_i\}_{i\in \{1..\ell \}}$ of $\mathbb {F}_{q^m}$ are mutually disjoint if $\forall \ i,j \in \{1..\ell \}, i\ne j, V_i \cap V_j=\{0\}$.

Definition 3.1

(Blockwise Errors ($\ell$-errors)). Let $\boldsymbol{e}_i\in \mathbb {F}_{q^m}^{n_i}$ be a vector of weight $r_i$ for $i\in \{1..\ell \}$. An error $\boldsymbol{e}= (\boldsymbol{e}_1,\boldsymbol{e}_2,\ldots , \boldsymbol{e}_{\ell })\in \mathbb {F}_{q^m}^{n}$ is called an $\ell$-error if the supports of $\ell$ vectors $\boldsymbol{e}_i$’s are mutually disjoint.

Recall that $\boldsymbol{n} = (n_1,\dots ,n_\ell )$ and $\boldsymbol{r} =(r_1,\dots ,r_\ell )$ are two vectors of positive integers. We denote the set of such $\ell$-errors by $\mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$. Let $E_i$ be the support of dimension $r_i$ of $\boldsymbol{e}_i$. Because all supports are mutually disjoint, the $\ell$-error $\boldsymbol{e}$ can be viewed as the error of weight r and support $E = \sum _{i=1}^{\ell }E_i$.

We now define the $\ell$-RD problem. This problem is the Rank Decoding (RD) problem finding the $\ell$-errors.

Definition 3.2

(Blockwise RD ($\ell$-RD) Problem). Let $\boldsymbol{G}$ be the generator matrix of a random $[n,k]_{q^m}$-linear code $\mathcal {C}$ and $\boldsymbol{y}\in \mathbb {F}_{q^m}^{n}$. The problem is to find $\boldsymbol{x} \in \mathbb {F}_{q^m}^k$ and $\boldsymbol{e} \in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$ such that $\boldsymbol{y}=\boldsymbol{x}\boldsymbol{G}+\boldsymbol{e}$.

Like the dual version of the RD problem using the generator matrix is the Rank Syndrome Decoding (RSD) problem [23] using the parity-check matrix, the dual version of the $\ell$-RD problem is defined as the $\ell$-RSD problem.

Definition 3.3

(Blockwise RSD ($\ell$-RSD) Problem). Let $\boldsymbol{H}$ be the parity-check matrix of a random $[n,k]_{q^m}$-linear code $\mathcal {C}$ and $\boldsymbol{s}\in \mathbb {F}_{q^m}^{n-k}$. The problem is to find $\boldsymbol{e} \in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$ such that $\boldsymbol{s}=\boldsymbol{H}\boldsymbol{e}^{\top }$.

Two variants are exactly the standard RD and RSD problems when $\ell =1$. By the duality, the hardness of two variants is equivalent. Intuitively, two variants are also hard because they still find a small-weight error.

3.2 Reduction, Support and Coefficient Matrices

In this subsection, we first recall existing attacks on the RD problem, then adapt the reduction refined from typical attacks to the $\ell$-RD problem, finally analyze support and coefficient matrices of the $\ell$-error.

Attacks on the RD Problem. There currently exist the combinatorial and algebraic attacks [5, 7,8,9, 14, 21, 37] on the RD problem. Please see Appendix B of full version [40] for detailed overviews of these attacks. The first combinatorial attack [14] starts with the RSD problem and is significantly improved in [37] and further refined in [5, 21]. The combinatorial attacks [5, 14, 21] consist of subtly guessing the support of error and solving a linear system. The attack [37] transforms a quadratic multivariate system obtained from the RD problem into a linear system by guessing the entries of support matrix and coefficient matrix. Another way is the algebraic attack [21], where one solves a multivariate system induced from the RD problem based on the annulator polynomial by linearization and Gröbner basis. A breakthrough paper [7] shows that the $\mathbb {F}_{q^m}$-linearity allows to devise a dedicated algebraic attack, i.e., the MaxMinors (MM) modeling. Then the MM modeling is refined and improved in [9] where the authors also introduced another algebraic modeling, the Support-Minors (SM) modeling. The SM modeling later is combined with the MM modeling (i.e., the SM-$\mathbb {F}_{q^m}^+$ modeling [8]). Both SM and MM modelings reduce the RD problem to solving a linear system. The analysis in [8] shows that the cost of the SM-$\mathbb {F}_{q^m}^+$ modeling is close to those of the combinatorial attack [5] and the MM modeling [9].

To measure the potential complexity loss and ensure the security of schemes, we adapt typical combinatorial attacks [5, 37] and algebraic attacks [9, 21] to the $\ell$-RD problem in Subsects. 3.3, 3.4 and 3.5. The reduction technique in attacks [5, 9, 21, 37] is still available to the $\ell$-RD problem. We refine the reduction in Theorem 3.4.

Theorem 3.4

Solving the $\ell$-$RD(q,m,n,k,r,\ell )$ problem defined by $[n,k]_{q^m}$ linear code $\mathcal {C}$ (see Definition 3.2) can be reduced to finding a blockwise codeword (i.e., an $\ell$-error) of weight r in the $[n,k+1]_{q^m}$ extended code of $\mathcal {C}$.

Proof

Once obtaining word $\boldsymbol{y}$, one adds $\boldsymbol{y}$ to code $\mathcal {C}$ and obtains an $[n,k+1]_{q^m}$ extended code $\mathcal {C}_{\boldsymbol{y}}=\mathcal {C} + \langle \boldsymbol{y}\rangle$ with a generator matrix $\left( \begin{array}{c} \boldsymbol{y}\\ \boldsymbol{G} \end{array}\right)$ of size $(k+1) \times n$. In this way, $\boldsymbol{e} = \left( \begin{array}{cc} 1& -\boldsymbol{m} \end{array}\right) \left( \begin{array}{c} \boldsymbol{y}\\ \boldsymbol{G} \end{array}\right)$ is exactly a codeword of weight r of $\mathcal {C}_{\boldsymbol{y}}$. Let $\boldsymbol{G}_{\boldsymbol{y}}=\left( \boldsymbol{I}_{k+1} \ \boldsymbol{R}\right) \in \mathbb {F}_{q^m}^{(k+1)\times n}$ be a systematic generator matrix of $\mathcal {C}_{\boldsymbol{y}}$ and $\boldsymbol{H}_{\boldsymbol{y}}=\left( -\boldsymbol{R}^{\top } \ \boldsymbol{I}_{n-k-1}\right) \in \mathbb {F}_{q^m}^{(n-k-1)\times n}$ be a systematic parity-check matrix of $\mathcal {C}_{\boldsymbol{y}}$, where $\boldsymbol{R} \in \mathbb {F}_{q^m}^{(k+1)\times (n-k-1)}$. Then solving the $\ell$-RD problem consists in finding an $\boldsymbol{u} \in \mathbb {F}_{q^m}^{k+1}$ of weight $\le r$ such that

$$\begin{aligned} \boldsymbol{u} \boldsymbol{G}_{\boldsymbol{y}} = \boldsymbol{e}, \end{aligned}$$

(2)

or finding an $\ell$-error $\boldsymbol{e}$ of weight r such that

$$\begin{aligned} \boldsymbol{e}\boldsymbol{H}_{\boldsymbol{y}}^{\top } = \boldsymbol{0}. \end{aligned}$$

(3)

   $\square$

The support and coefficient matrices of the $\ell$-error are crucial tools to construct the specific attack modelings by exploiting the reduction in Theorem 3.4. The entries of two matrices determine the number of variables of algebraic equations in the attack modelings. We next analyze the forms of two matrices.

Support and Coefficient Matrices of the $\ell$-error. Let $\boldsymbol{n} = (n_1,\dots ,n_\ell )$ and $\boldsymbol{r} =(r_1,\dots ,r_\ell )$ be vectors of positive integers. Let $\boldsymbol{e} = (\boldsymbol{e}_1,\boldsymbol{e}_2,\ldots , \boldsymbol{e}_\ell )\in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$ be an $\ell$-error. If let $\boldsymbol{\varepsilon }_i = (\varepsilon _{i1},\varepsilon _{i2},\ldots ,\varepsilon _{ir_i})\in \mathbb {F}_{q^m}^{r_i}$ be a basis of support of dimension $r_i$, then there exists a matrix $\boldsymbol{C}_i \in \mathbb {F}_{q}^{r_i\times n_i}$ of rank $r_i$ such that $\boldsymbol{e}_i = \boldsymbol{\varepsilon }_i \boldsymbol{C}_i$, If one expresses the basis $\boldsymbol{\varepsilon }_i$ as a matrix $\boldsymbol{S}_i\in \mathbb {F}_{q}^{m\times r_i}$ of rank $r_i$ under the basis $\boldsymbol{\alpha }$, then $\boldsymbol{e}_i = \boldsymbol{\alpha }\boldsymbol{S}_i \boldsymbol{C}_i$. We have $\boldsymbol{e}= \boldsymbol{\varepsilon }\boldsymbol{C} = \boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{C}$, where $\boldsymbol{\varepsilon }= (\boldsymbol{\varepsilon }_1,\boldsymbol{\varepsilon }_2,\ldots , \boldsymbol{\varepsilon }_\ell )\in \mathbb {F}_{q^m}^{r}$,

$$\begin{aligned} \boldsymbol{S}= \begin{pmatrix} \boldsymbol{S}_1 & \boldsymbol{S}_2 & \cdots & \boldsymbol{S}_\ell \end{pmatrix}\in \mathbb {F}_{q}^{m\times r}, \qquad \boldsymbol{C} = \begin{pmatrix} \boldsymbol{C}_1 &{} \boldsymbol{0} &{} \boldsymbol{0}&{} \boldsymbol{0}\\ \boldsymbol{0} &{} \boldsymbol{C}_2 &{} \boldsymbol{0}&{}\boldsymbol{0}\\ \vdots &{} \vdots &{} \ddots &{}\vdots \\ \boldsymbol{0} &{} \boldsymbol{0} &{}\boldsymbol{0} &{}\boldsymbol{C}_\ell \end{pmatrix}\in \mathbb {F}_{q}^{r\times n}. \end{aligned}$$

(4)

We call $\boldsymbol{S}$ and $\boldsymbol{C}$ respectively support matrix and coefficient matrix of $\boldsymbol{e}$.

Remark 1

The main difference with the standard rank metric error is that the form of the coefficient matrix $\boldsymbol{C}$ of the $\ell$-error is of block-diagonal form. For a standard rank metric error $\boldsymbol{e}\in \mathcal {S}^{n}_{r}$, let $\boldsymbol{\varepsilon }= (\varepsilon _1,\varepsilon _2,\ldots ,\varepsilon _r)\in \mathbb {F}_{q^m}^{r}$ be a basis of $\textrm{Supp}(\boldsymbol{e})$, the there is a coefficient matrix $\boldsymbol{C} \in \mathbb {F}_{q}^{r\times n}$ of rank r such that $\boldsymbol{e} = \boldsymbol{\varepsilon }\boldsymbol{C}$. Under the basis $\boldsymbol{\alpha }$, there is a support matrix $\boldsymbol{S} \in \mathbb {F}_{q}^{m\times r}$ of rank r such that $\boldsymbol{\varepsilon }= \boldsymbol{\alpha }\boldsymbol{S}$. Then $\boldsymbol{e} = \boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{C}$.

Support and Coefficient Matrices with Less Entries. Because all multiples $\lambda \boldsymbol{e}$ for $\lambda \in \mathbb {F}_{q^m}^{*}$ are solutions of Eq. (3) due to $\Vert \lambda \boldsymbol{e}\Vert _\textrm{R}=r$, one can specify $\lambda$ to be the inverse of the first coordinate of $\boldsymbol{e}$. Without loss of generality, let the first coordinate of $\boldsymbol{e}$ be 1, then one can set the first column of $\boldsymbol{C}$ to $(1 \ 0 \ \cdots \ 0)^{\top }$ and the first column of $\boldsymbol{S}$ to $(1 \ 0 \ \cdots \ 0)^{\top }$. Then $\boldsymbol{S}$ and $\boldsymbol{C}$ can be further reduced to two forms with less entries.

• $\boldsymbol{S}_{\{1..r\},*}= \boldsymbol{I}_r$. By Gaussian elimination on column of $\boldsymbol{S}$, there is a matrix $\boldsymbol{P} \in \textrm{GL}_r(q)$ such that and where $\boldsymbol{S}' \in \mathbb {F}_{q}^{(m-r)\times (r-1)}$ and $\boldsymbol{C}' \in \mathbb {F}_{q}^{r\times (n-1)}$. Then

  

  (5)

  Let $\boldsymbol{s} :=\boldsymbol{S}\boldsymbol{P}$ and $\boldsymbol{C} := \boldsymbol{P}^{-1}\boldsymbol{C}$.

• $\boldsymbol{C}_{i}$ is of systematic form. By Gaussian elimination on row of $\boldsymbol{C}$, there is a matrix $\boldsymbol{Q}_i\in \textrm{GL}_{r_i}(q)$ such that $\boldsymbol{Q}_i\boldsymbol{C}_i= (\boldsymbol{I}_{r_i} \ \boldsymbol{C}'_i)$ and where $\boldsymbol{C}'_i \in \mathbb {F}_{q}^{r_i\times (n_i-r_i)}$, $\boldsymbol{S}' \in \mathbb {F}_{q}^{m\times (r-1)}$, and $\boldsymbol{Q} =\begin{pmatrix} \boldsymbol{Q}_1 &{} \boldsymbol{0} &{} \boldsymbol{0}&{} \boldsymbol{0}\\ \boldsymbol{0} &{} \boldsymbol{Q}_2 &{} \boldsymbol{0}&{}\boldsymbol{0}\\ \vdots &{} \vdots &{} \ddots &{}\vdots \\ \boldsymbol{0} &{} \boldsymbol{0} &{}\boldsymbol{0} &{}\boldsymbol{Q}_{\ell } \end{pmatrix}\in \textrm{GL}_r(q)$. Then

  

  (6)

  Let $\boldsymbol{S} := \boldsymbol{S}\boldsymbol{Q}^{-1}$ and $\boldsymbol{C} := \boldsymbol{Q}\boldsymbol{C}$.

For solving the $\ell$-RD problem, most attacks aim to recover $\boldsymbol{S}$ and $\boldsymbol{C}$ by solving the algebraic equations obtained from Eqs. (2)–(6). Equation (3) is used to build the AGHT attacks (Subsect. 3.3). Equations (2), (5) and (6) are used to build the OJ attack (Subsect. 3.3). Equations (3) and (6) are used to build the algebraic attack, the MM modeling (Subsect. 3.5). The details of constructing the algebraic equations can refer to the specific attacks in Subsects. 3.3, 3.4 and 3.5.

3.3 Combinatorial Attacks on the $\ell$-RD Problem

In this subsection, we use the AGHT attack [5] and the OJ attack [37] to analyze the complexity of solving the $\ell$-RD problem.

AGHT Attack [5]. The idea is that the solver tries to guess a subspace that contains the support of the $\ell$-error, then checks if the choice is correct. The cost depends on how to successfully guess such a subspace.

• Guess randomly a t-dimensional subspace F that contains the support $\textrm{Supp}(\boldsymbol{e})$ of dimension $r = \sum _{i=1}^{\ell }r_i$ of the $\ell$-error $\boldsymbol{e}$.

• Let $(f_1,f_2,\ldots ,f_t) \in \mathbb {F}_{q^m}^{t}$ be a basis of F. One expresses $\boldsymbol{e}$ under this basis

  $$\begin{aligned}\begin{gathered} \boldsymbol{e} = (e_1,e_2,\ldots ,e_n)= (f_1,f_2,\ldots ,f_t) \begin{pmatrix} e_{11}&{} e_{12}&{} \cdots &{} e_{1n} \\ e_{21}&{} e_{22}&{} \cdots &{} e_{2n}\\ \vdots &{} \vdots &{} \cdots &{} \vdots \\ e_{t1}&{} e_{t2}&{}\cdots &{} e_{tn} \end{pmatrix} = (f_1,f_2,\ldots ,f_t) \begin{pmatrix} \overline{\boldsymbol{e}}_1 \\ \overline{\boldsymbol{e}}_2\\ \vdots \\ \overline{\boldsymbol{e}}_t \end{pmatrix}, \end{gathered}\end{aligned}$$

  where $\overline{\boldsymbol{e}}_i = (e_{i1}, e_{i2}, \ldots , e_{in})\in \mathbb {F}_{q}^n$ for $i \in \{1 .. t\}$. By Eq. (3): $\boldsymbol{H}_{\boldsymbol{y}} \boldsymbol{e}^{\top }=\boldsymbol{0}$, let $\boldsymbol{h}_j$ is the j-th row of $\boldsymbol{H}_{\boldsymbol{y}}$, we have

  $$\begin{aligned} \boldsymbol{H}_{\boldsymbol{y}} \boldsymbol{e}^{\top } &= \begin{pmatrix} \boldsymbol{h}_1 \\ \boldsymbol{h}_2\\ \vdots \\ \boldsymbol{h}_{n-k-1} \end{pmatrix}\left( \overline{\boldsymbol{e}}^{\top }_1,\overline{\boldsymbol{e}}^{\top }_2,\ldots ,\overline{\boldsymbol{e}}^{\top }_t\right) \begin{pmatrix} f_1 \\ f_2\\ \vdots \\ f_t \end{pmatrix}\nonumber \\ &= \begin{pmatrix} \boldsymbol{h}_{1}f_1 &{} \boldsymbol{h}_{1}f_2&{} \cdots &{} \boldsymbol{h}_{1}f_t \\ \boldsymbol{h}_{2}f_1 &{} \boldsymbol{h}_{2}f_2&{} \cdots &{} \boldsymbol{h}_{2}f_t \\ \vdots &{} \vdots &{} \cdots &{} \vdots \\ \boldsymbol{h}_{n-k-1}f_1 &{} \boldsymbol{h}_{n-k-1}f_2&{} \cdots &{} \boldsymbol{h}_{n-k-1}f_t \\ \end{pmatrix} \begin{pmatrix} \overline{\boldsymbol{e}}^{\top }_1 \\ \overline{\boldsymbol{e}}^{\top }_2\\ \vdots \\ \overline{\boldsymbol{e}}^{\top }_t \end{pmatrix} = \boldsymbol{0}_{n-k-1}. \end{aligned}$$

  (7)

• Express Eq. (7) as a linear system over $\mathbb {F}_{q}$ and solve $\overline{\boldsymbol{e}}_{i}$. By expressing $\boldsymbol{h}_jf_i$ as a matrix $\textrm{Mat}(\boldsymbol{h}_jf_i)\in \mathbb {F}^{m\times n}_{q}$ under the basis $\boldsymbol{\alpha }$ for $j \in \{1 .. n-k-1\}$ and $i \in \{1 .. t\}$, a linear system over $\mathbb {F}_{q}$ with nt unknowns and $m(n-k-1)$ equations is obtained. The linear system has only one solution with overwhelming probability if $nt\le m(n-k-1)$.

• The probability of $F \supset E$ is estimated as . In this way, the complexity is $\mathcal {O}\left( ((n-k-1)m)^\omega q^{r\left\lceil \frac{(k+1)m}{n}\right\rceil }\right)$.

• Use $\mathbb {F}_{q^{m}}$-linearity to decrease the cost. Since, for any $\lambda \in \mathbb {F}_{q^m}^{*}$, $\Vert \lambda \boldsymbol{e}\Vert _\textrm{R}=r$ and all multiples $\lambda \boldsymbol{e}$ are solutions of Eq. (3): $\boldsymbol{H}_{\boldsymbol{y}} \boldsymbol{e}^{\top }=\boldsymbol{0}$, the complexity is divided by about $q^m$.

As a result, this attack has a complexity of $\mathcal {O}\left( ((n-k-1)m)^\omega q^{r\left\lceil \frac{(k+1)m}{n}\right\rceil -m}\right)$.

In [12], the authors adapted the AGHT attack to the RD problem finding so-called non-homogeneous errors. Here, inspired by [12], the strategy guessing the subspace F is that the solver randomly guesses a subspace $F_i$ of dimension $t_i$ that contains the support $E_i=\textrm{Supp}(\boldsymbol{e}_i)$ of dimension $r_i$ of $\boldsymbol{e}_i$ such that all $F_i$’s are mutually disjoint, and sets $F = \sum _{i=1}^{\ell }F_i$. In this way, the dimension of F is of $\sum _{i=1}^{\ell }t_i$, and F must contain the support of the $\ell$-error $\boldsymbol{e}$.

If one knows $F_i$, then each entry of $\boldsymbol{e}_i$ can be expressed as an $\mathbb {F}_q$-linear combination of $t_i$ elements in a basis of $F_i$. This means that one can write $\boldsymbol{e}_i$ using $n_it_i$ unknowns in $\mathbb {F}_q$. Doing the same for all $\boldsymbol{e}_i$’s, one obtains $\sum _{i=1}^{\ell }n_it_i$ unknowns. Then one solves the linear system with $\sum _{i=1}^{\ell }n_it_i$ unknowns and $m(n-k-1)$ equations for single solution $\boldsymbol{e}$ as long as $\sum _{i=1}^{\ell }n_it_i\le m(n-k-1)$. The most costly part of the attack consists in finding the $F_i$’s containing $E_i$ for $i \in \{1..\ell \}$. We estimate this probability in Lemma 3.5.

Lemma 3.5

Let $E_1, E_2,\ldots ,E_\ell$ be fixed $\mathbb {F}_q$-subspaces of dimension respectively $r_1, r_2,...,r_\ell$ of $\mathbb {F}_{q^m}$. The probability that one successfully guesses $\mathbb {F}_q$-subspaces $F_1, F_2,...,F_{\ell }$ dimension respectively $t_1, t_2,\ldots ,t_\ell$ of $\mathbb {F}_{q^m}$ such that all $F_i$’s are mutually disjoint and $E_i\subset F_i$ is estimated as $\mathcal {O}\left( q^{-mr+\sum _{i=1}^{\ell -1}r_i^2+\sum _{j=2}^{\ell }r_j\sum _{i=1}^{j-1}r_i+t_{\ell }r_{\ell }}\right)$.

We give the detailed proof for Lemma 3.5 in Appendix C.1 of full version [40]. Finally, one takes advantage of the $\mathbb {F}_{q^{m}}$-linearity to raise this probability: for any $\lambda \in \mathbb {F}_{q^m}^{*}$, $\Vert \lambda \boldsymbol{e}\Vert _\textrm{R}=r$ and all multiples $\lambda \boldsymbol{e}$ are solutions of Eq. (3): $\boldsymbol{H}_{\boldsymbol{y}} \boldsymbol{e}^{\top }=\boldsymbol{0}$, hence the complexity is divided by about $q^m$. The complexity of solving the $\ell$-RD problem by the variant of AGHT attack is estimated as

$$\mathcal {O}\left( (m(n-k-1))^{\omega }q^{mr-\sum _{i=1}^{\ell -1}r_i^2-\sum _{j=2}^{\ell }r_j\sum _{i=1}^{j-1}r_i-t_\ell r_\ell -m}\right) $$

where $t_i$ is chosen to maximize $t_\ell r_\ell$ under the constraints

$$\begin{aligned} {\left\{ \begin{array}{ll} r_i\le t_i, \ \ for \ i \in \{1..\ell \};\\ \sum \nolimits _{i=1}^{\ell }t_i \le m-1;\\ \sum \nolimits _{i=1}^{\ell }n_it_i\le m(n-k-1). \end{array}\right. } \end{aligned}$$

OJ Attack. We now analyze the complexity of solving the $\ell$-RD problem by the OJ attack [37]. Let $\overline{\boldsymbol{e}}_1$ and $\overline{\boldsymbol{e}}_2$ be the first $k+1$ and the last $n-k-1$ coordinates of $\boldsymbol{e}$. Let $\boldsymbol{A}_1$ and $\boldsymbol{A}_2$ be the first $k+1$ columns and the last $n-k-1$ columns of $\boldsymbol{C}$. Then $\boldsymbol{e} = (\overline{\boldsymbol{e}}_1,\overline{\boldsymbol{e}}_2) = \boldsymbol{\varepsilon }(\boldsymbol{A}_1, \boldsymbol{A}_2)=(\boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{A}_1,\boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{A}_2)$. Equation (2) means

$$\begin{aligned} \boldsymbol{u}\boldsymbol{G}_{\boldsymbol{y}} =\boldsymbol{e} \Longleftrightarrow (\boldsymbol{u} \ \boldsymbol{u}\boldsymbol{R}) = (\overline{\boldsymbol{e}}_1,\overline{\boldsymbol{e}}_2) \Longleftrightarrow \overline{\boldsymbol{e}}_1\boldsymbol{R} = \overline{\boldsymbol{e}}_2 \Longleftrightarrow \boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{A}_1\boldsymbol{R} = \boldsymbol{\alpha }\boldsymbol{S} \boldsymbol{A}_2. \end{aligned}$$

(8)

We first analyze the case of the 2-RD problem, then extend conclusions into general cases. By Equation (8), for $j\in \{1..n-k-1\}$, let $\boldsymbol{r}_j$ and $\boldsymbol{a}_{j}$ be the j-th column of $\boldsymbol{R}$ and $\boldsymbol{A}_2$, respectively, then

(9)

Let where $\boldsymbol{T}_j \in \mathbb {F}_{q}^{(k+2)\times m}$ is the matrix expression of under the basis $\boldsymbol{\alpha }$. Equation (9) can be written $\boldsymbol{\alpha }\boldsymbol{S} \begin{pmatrix}\boldsymbol{A}_1 \ \boldsymbol{a}_j\end{pmatrix} \boldsymbol{T}_j \boldsymbol{\alpha }^{\top } = 0$. This means

$$\begin{aligned} \boldsymbol{S}(\boldsymbol{A}_1 \ \boldsymbol{a}_j)\boldsymbol{T}_j = \boldsymbol{0}_{m\times m}. \end{aligned}$$

(10)

The entries of $\boldsymbol{S}(\boldsymbol{A}_1 \ \boldsymbol{a}_j)\boldsymbol{T}_j$ are quadratic polynomials. Then Eq. (10) gives a quadratic multivariate system over $\mathbb {F}_{q}$ with $m^2$ quadratic polynomials in the entries of $\boldsymbol{S}$ and $\boldsymbol{C}$.

The OJ attack uses the basis enumeration and the coordinates enumeration to transform the quadratic multivariate system into a linear system. The former guesses all entries of $\boldsymbol{S}$ and solves the linear system about the entries of $(\boldsymbol{A}_1 \ \boldsymbol{a}_j)$ to determine $\boldsymbol{C}$. The latter guesses the entries of $\boldsymbol{C}$ and solves the linear system about the entries of $\boldsymbol{S}$ to determine $\boldsymbol{S}$.

When $\boldsymbol{S}$ and $\boldsymbol{C}$ are in the form of Eq. (5) and Eq. (6), the complexities are presented in Theorem 3.6 and Theorem 3.7. We give their detailed proofs in Appendix C.2 and Appendix C.3 of full version [40]. The ideas of proofs can be easily extended to the $\ell$-RD problem.

Theorem 3.6

If $\boldsymbol{S}$ and $\boldsymbol{C}$ are in the form of Eq. (5), the 2-RD problem can be solved with complexity $\mathcal {O}\left( (kr+r)^{\omega }q^{(m-r)(r-1)}\right)$ by the basis enumeration.

Theorem 3.7

If $k=n_1$, $\boldsymbol{S}$ and $\boldsymbol{C}$ are in the form of Eq. (6), the 2-RD problem can be solved with complexity $\mathcal {O}\left( (m(r-1)+(n_1-r_1))^{\omega }q^{(r_1-1)(n_1-r_1)+r_2}\right)$ by the coordinates enumeration.

Theorem 3.8

If $k=n_1$, the complexity of solving the $\ell$-RD problem by the OJ attack is estimated as

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathcal {O}\big ((kr+r)^{\omega }q^{(m-r)(r-1)}\big ), \ {} &{} {Basis\,Enumeration};\\ \mathcal {O}\left( (m(r-1)+(n_1-r_1))^{\omega }q^{(r_1-1)(n_1-r_1)+\gamma }\right) ,\ {} &{} {Coordinates\,Enumeration}, \end{array}\right. } \end{aligned}$$

where $\gamma = \max \big \{r_i: i\in \{2..\ell \}\big \}$ and $r = \sum _{i=1}^{\ell }r_i$.

3.4 Algebraic Attack by Annulator Polynomial

This algebraic attack [21] differs from attacks aiming to recover $\boldsymbol{S}$ and $\boldsymbol{C}$ with reductions described in Subsect. 3.2. It directly solves $\boldsymbol{x}$ from a multivariate system obtained from the $\ell$-RD instance and the theory of q-polynomials [36], more specifically annulator polynomials (see Appendix A of full version [40]). The attack details are outlined in Appendix B.2 of full version [40].

For the $\ell$-RD problem finding the $\ell$-error $\boldsymbol{e} = (\boldsymbol{e}_1,\boldsymbol{e}_2,\ldots ,\boldsymbol{e}_\ell )\in \mathcal {S}^{\boldsymbol{n}}_{\boldsymbol{r}}$, the solver splits $\boldsymbol{y}$ as $(\boldsymbol{y}_1,\boldsymbol{y}_2,\ldots ,\boldsymbol{y}_\ell )$ and splits $\boldsymbol{G}$ as $(\boldsymbol{G}_1, \boldsymbol{G}_2, \ldots , \boldsymbol{G}_\ell )$ by columns $\boldsymbol{n}$. Then

$$(\boldsymbol{y}_1,\boldsymbol{y}_2,\ldots ,\boldsymbol{y}_\ell ) = \boldsymbol{x}(\boldsymbol{G}_1, \boldsymbol{G}_2, \ldots , \boldsymbol{G}_\ell )+ (\boldsymbol{e}_1,\boldsymbol{e}_2,\ldots ,\boldsymbol{e}_\ell ).$$

In this way, the $\ell$-RD problem is divided into $\ell$ subproblems, for $\nu \in \{1..\ell \}$, $\boldsymbol{y}_{\nu } = \boldsymbol{x} \boldsymbol{G}_{\nu } + \boldsymbol{e}_{\nu }$, then one solves $\boldsymbol{x}$ from one of $\ell$ subproblems.

Let $\boldsymbol{x} = (x_1, x_2,\ldots ,x_k)$. For $\nu \in \{1..\ell \}$, let $\boldsymbol{y}_\nu = (y_1,y_2,\ldots ,y_{n_\nu })$, $\boldsymbol{G}_\nu = (g_{ij})_{\begin{array}{c} i\in \{1..k\} \\ j \in \{1..n_\nu \} \end{array}}$, and $\boldsymbol{e}_\nu = (e_1,e_2,\ldots ,e_{n_\nu })$. Since the entries of $\boldsymbol{e}_\nu$ lie in the support $\textrm{Supp}(\boldsymbol{e}_\nu )$ of dimension $r_\nu$, there exists a unique monic q-polynomials $P^{(\nu )}(u) = \sum _{\delta =0}^{r_\nu }p^{(\nu )}_\delta u^{q^\delta }$ of q-degree $r_\nu$ such that for $j \in \{1..n_\nu \}$

$$\begin{aligned} P^{(\nu )}\left( y_j-\sum _{i=1}^{k}x_ig_{ij}\right) = \sum _{\delta =0}^{r_\nu }\left( p^{(\nu )}_\delta y_j^{q^\delta }- \sum _{i=1}^{k}p^{(\nu )}_\delta x_i^{q^\delta }g_{ij}^{q^\delta }\right) = P^{(\nu )}\left( e_j\right) = 0. \end{aligned}$$

(11)

Equation (11) gives a multivariate system with $n_\nu$ polynomials and $(r_\nu +k)$ variables $p^{(\nu )}_\delta$ and $x_i$. For solving the $\ell$-RD problem, one solves $x_i$ from this multivariate system.

The linearization and Gröbner basis techniques are applied to solve $x_i$. The complexities are given in Theorem 3.9 and the detailed proof is presented in Appendix C.4 of full version [40].

Theorem 3.9

The complexity of solving the $\ell$-RD problem by annulator polynomials is estimated as

where $d^{(\nu )}_{reg}$ is the degree of regularity of the semi-regular system.

3.5 Algebraic Attacks by the MaxMinors Modeling

The MaxMinors (MM) modeling [9] is a powerful algebraic attack for cryptographic parameters and reduces the RD problem to solving a linear system. Equation $\boldsymbol{\varepsilon }\boldsymbol{C}\boldsymbol{H}_{\boldsymbol{y}}^{\top } = \boldsymbol{0}_{n-k-1}$ (obtained from Eq. (3) and $\boldsymbol{e}= \boldsymbol{\varepsilon }\boldsymbol{C}$) implies that $\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}\in \mathbb {F}_{q^m}^{r \times (n-k-1)}$ is not of row full rank because a non-zero vector $\boldsymbol{s}$ belongs to its left kernel. Then all maximal minors $|\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}|_{*,J}$ of $\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}$ are equal to 0 for $J\subset \{1..n-k-1\}$ and $\#J=r$. By the Cauchy-Binet formula, each $|\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}|_{*,J}$ can be viewed a non-zero linear combination about all maximal minors $c_T= |\boldsymbol{C}|_{*,T}$ for $T \subset \{1..n\}$ and $\#T=r$. One views non-zero $c_T$ as unknowns and solves $c_T$ from a linear system with $\left( {\begin{array}{c}n\\ r\end{array}}\right)$ unknowns and $\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right)$ equations. Finally, one determines the entries of $\boldsymbol{C}$ from the $c_T$ by using the fact that it is in systematic form. The $\text {MM}$ modeling over $\mathbb {F}_{q^m}$ is built

$$\begin{aligned} \left\{ P_{J} = |\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}|_{*,J}: J\subset \{1..n-k-1\}, \#J=r \right\} , \quad (\text {MM-}\mathbb {F}_{q^m}) \end{aligned}$$

(12)

Unknowns: $\left( {\begin{array}{c}n\\ r\end{array}}\right)$ variables $c_T \in \mathbb {F}_{q}$ for $T \subset \{1..n\}$ and $\#T=r$,

Equations: $\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right)$ linear equations $P_{J}=0$ over $\mathbb {F}_{q^m}$ in $c_T$.

However, this system has many solutions due to $\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) <\left( {\begin{array}{c}n\\ r\end{array}}\right)$ whereas one wants more equations than unknowns for a unique solution. To obtain more equations than unknowns, one unfolds the coefficients of $P_{J}$ over $\mathbb {F}_{q}$ and obtains the MM-$\mathbb {F}_{q}$ modeling

$$\begin{aligned} \left\{ P_{i,J} = |\boldsymbol{C}\boldsymbol{H}^{\top }_{\boldsymbol{y}}|_{*,J}: J\subset \{1..n-k-1\}, \#J=r, i\in \{1..m\} \right\} , \quad (\text {MM-}\mathbb {F}_{q}) \end{aligned}$$

(13)

Unknowns: $\left( {\begin{array}{c}n\\ r\end{array}}\right)$ variables $c_T \in \mathbb {F}_{q}$ for $T \subset \{1..n\}$ and $\#T=r$,

Equations: $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right)$ linear equations $P_{i,J}=0$ over $\mathbb {F}_{q}$ in $c_T$.

We first analyze the case of the 2-RD problem, then extend conclusions to general cases. By Eq. (6), the matrix $\boldsymbol{C}$ is of form

$$\begin{aligned} \boldsymbol{C} = \left( \begin{array}{c|c} \boldsymbol{I}_{r_1} \ \boldsymbol{C}'_1&{}\boldsymbol{0}_{r_1\times n_2}\\ \hline \boldsymbol{0}_{r_2\times n_1}&{} \boldsymbol{I}_{r_2} \ \boldsymbol{C}'_2\end{array}\right) \in \mathbb {F}_{q}^{r\times n}, \end{aligned}$$

(14)

where $\boldsymbol{C} = (c_{ij})_{\begin{array}{c} i\in \{1..r\} \\ j \in \{1..n\} \end{array}} \in \mathbb {F}_{q}^{r\times n}$, $\boldsymbol{C}'_1 \in \mathbb {F}_{q}^{r_1\times (n_1-r_1)}$, and $\boldsymbol{C}'_2 \in \mathbb {F}_{q}^{r_2\times (n_2-r_2)}$. One can easily check

• $|\boldsymbol{C}|_{*,(\{1..r_1\}\setminus \{i\}\cup \{j\})\cup \{n_1+1..n_1+r_2\}}= (-1)^{r_1-i}c_{ij}$ for $i \in \{1..r_1\}$ and $j \in \{r_1+1..n_1\}$,

• $|\boldsymbol{C}|_{*,\{1..r_1\}\cup (\{n_1+1..n_1+r_2\}\setminus \{i\}\cup \{j\})}= (-1)^{n_1+r_2-i}c_{ij}$ for $i \in \{n_1+1..n_1+r_2\}$ and $j \in \{n_1+r_2+1..n\}$,

• $|\boldsymbol{C}|_{*,\{1..r_1\}\cup \{n_1+1..n_1+r_2\}}= 1$.

Therefore, once all $c_T$’s are solved, one can determine the entries of the matrix $\boldsymbol{C}$. Lemma 3.10 bounds the number of equations and unknowns $c_T$.

Lemma 3.10

Under block form of $\boldsymbol{C}$ in Eq. (14), the $\text {MM-}\mathbb {F}_{q}$ modeling obtained from the 2-RD problem contains $\left( {\begin{array}{c}n_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2\\ r_2\end{array}}\right)$ unknowns $c_T$ and at most $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right)$ equations.

We give the detailed proof for Lemma 3.10 in Appendix C.5 of full version [40].

Remark 2

Our analysis follows the idea of updated RQC [30], where authors bounded the maximal number of equations. On the one hand, considering less equations could lead to a higher complexity because in this case one is more likely to solve an underdetermined system with more unknowns and would guess more entries of $\boldsymbol{C}$ to transform the system into an overdetermined case (see hybrid method in the proof of Theorem 3.11). This means that using the maximal number of equations would give a lower bound of complexity. Cryptographic parameters often lead to an underdetermined case. On the other hand, the number of zero and dependent equations is negligible to the maximal number $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right)$ and their impact on complexity is very limited. A thorough analysis in [8, 12] supported this point and we also experimentally verified this when $\ell =2,3$.

Remark 3

The number of non-zero variables $c_T$ is easy to compute. When n and r are divisible by $\ell$, by Stirling approximation, the loss of variables $c_T$ is large due to $\left( {\begin{array}{c}n/\ell \\ r/\ell \end{array}}\right) ^\ell \approx \ell ^\frac{\ell }{2}\left( \frac{n}{2\pi r(n-r)}\right) ^{\frac{\ell -1}{2}}\left( {\begin{array}{c}n\\ r\end{array}}\right)$ while comparing with the $\text {MM-}\mathbb {F}_{q}$ modeling obtained from the standard RD problem. See Lemma C.1 in Appendix C.6 of full version [40] for this proof.

Theorem 3.11

The complexity of solving the 2-RD problem by the MM-$\mathbb {F}_{q}$ modeling is estimated as

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathcal {O}\left( m\left( {\begin{array}{c}n-p-k-1\\ r\end{array}}\right) \left( \left( {\begin{array}{c}n_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2-p\\ r_2\end{array}}\right) \right) ^{\omega -1}\right) , \ {} &{} m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \left( {\begin{array}{c}n_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2\\ r_2\end{array}}\right) -1;\\ \mathcal {O}\left( q^{a_1r_1+a_2r_2}m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \left( \left( {\begin{array}{c}n_1-a_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2-a_2\\ r_2\end{array}}\right) \right) ^{\omega -1}\right) , &{} m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) < \left( {\begin{array}{c}n_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2\\ r_2\end{array}}\right) -1. \end{array}\right. } \end{aligned}$$

where $p=\max \left\{ i \ | \ m\left( {\begin{array}{c}n-i-k-1\\ r\end{array}}\right) \ge \left( {\begin{array}{c}n_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2-i\\ r_2\end{array}}\right) -1\right\}$ and $(a_1,a_2)$ is an integer pair such that $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \left( {\begin{array}{c}n_1-a_1\\ r_1\end{array}}\right) \left( {\begin{array}{c}n_2-a_2\\ r_2\end{array}}\right) -1$ exactly holds.

We give a proof with full details for Theorem 3.11 in Appendix C.7 of full version [40]. Theorem 3.11 can be extended to the case of the $\ell$-RD problem.

Theorem 3.12

The complexity of solving the $\ell$-RD problem by the $\text {MM-}\mathbb {F}_{q}$ modeling is estimated as

$$\begin{aligned} {\left\{ \begin{array}{ll} \mathcal {O}\left( m\left( {\begin{array}{c}n-p-k-1\\ r\end{array}}\right) \left( \left( {\begin{array}{c}n_\ell -p\\ r_\ell \end{array}}\right) \prod \limits _{i=1}^{\ell -1}\left( {\begin{array}{c}n_i\\ r_i\end{array}}\right) \right) ^{\omega -1}\right) , \ {} &{} m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n_i\\ r_i\end{array}}\right) -1;\\ \mathcal {O}\left( q^{\sum _{i=1}^{\ell }a_ir_i}m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \left( \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n_i-a_i\\ r_i\end{array}}\right) \right) ^{\omega -1}\right) , &{} m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) < \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n_i\\ r_i\end{array}}\right) -1. \end{array}\right. } \end{aligned}$$

where $p=\max \left\{ i \ \Big | \ m\left( {\begin{array}{c}n-i-k-1\\ r\end{array}}\right) \ge \left( {\begin{array}{c}n_\ell -i\\ r_\ell \end{array}}\right) \prod \limits _{i=1}^{\ell -1}\left( {\begin{array}{c}n_i\\ r_i\end{array}}\right) -1\right\}$ and $(a_1,a_2,\ldots ,a_\ell )$ is an integers sequence such that $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n_i-a_i\\ r_i\end{array}}\right) -1$ exactly holds.

3.6 Summary of Complexities for Solving the $\ell$-RD Problem

At the end of this section, we summarize the complexity gain of solving the $\ell$-RD problem compared with the standard RD problem in Table 2. For the first three attacks, we only compare the exponential terms.

Table 2. Complexity comparisons of solving the $\ell$-RD and RD problems.

Remark 4

The complexity analysis shows that the gain of most attacks on the $\ell$-RD problem benefits from the blockwise structure of $\ell$-errors. (1) the OJ and MM attacks benefits from the block-diagonal form of coefficient matrix $\boldsymbol{C}$ because the sparse $\boldsymbol{C}$ enables one to solve less variables (multivariable or linear) system; (2) the AGHT attack is limited because its cost depends on how to successfully guess a subspace that contains the support of the error; (3) the annulator polynomials attack benefits from the fact that the $\ell$-errors allow to divide the $\ell$-RD problem into $\ell$ subproblems with the smaller parameters.

For the powerful MM-$\mathbb {F}_{q}$ modeling, in the “underdetermined” case, an interesting result is that the complexity of solving the $\ell$-RD problem allows to divide by a factor $\ell$ that of solving the standard RD problem.

Let $\ell |n$, $\ell |r$, $n'=n/\ell$, and $r'=r/\ell$. For both RD and $\ell$-RD instances, when the parameters (m, n, k, r) satisfy respectively the “underdetermined” conditions: $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) < \left( {\begin{array}{c}n\\ r\end{array}}\right) -1$ and $m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) < \left( {\begin{array}{c}n'\\ r'\end{array}}\right) ^{\ell }-1$. The attacker chooses appropriate a and $(a_1,a_2,\ldots ,a_\ell )$ such that

$$\begin{aligned} m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \left( {\begin{array}{c}n-a\\ r\end{array}}\right) -1 \ \ \text {and} \ \ m\left( {\begin{array}{c}n-k-1\\ r\end{array}}\right) \ge \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n'-a_i\\ r'\end{array}}\right) -1 \end{aligned}$$

exactly hold. This means $\left( {\begin{array}{c}n-a\\ r\end{array}}\right) \approx \prod \limits _{i=1}^{\ell }\left( {\begin{array}{c}n'-a_i\\ r'\end{array}}\right)$. From Lemma C.1 in Appendix C.6 of full version [40], an appropriate choice is $a_1=a_2=\cdots =a_\ell$ and $a_i=a/\ell$. At this point,

$$\begin{aligned} \frac{\log _q(T_\textrm{RD})}{\log _q(T_{\ell \text {-RD}})}\approx \frac{ar}{\sum _{i}^{\ell }a_ir_i} = \ell \ \ \Longrightarrow \ \ T_{\ell \text {-RD}}\approx \root \ell \of {T_\textrm{RD}}, \end{aligned}$$

where $T_\textrm{RD}$ and $T_{\ell \text {-RD}}$ are the complexity of solving the RD and $\ell$-RD problems, respectively. This further shows that the speedup really benefits from the block-diagonal form of $\boldsymbol{C}$ because having $\boldsymbol{C}$ sparse enables one to guess $\sum _{i=1}^{{\ell }}a_ir_i$ entries of $\boldsymbol{C}$ to convert the “underdetermined” system into an “overdetermined” system, instead of ar entries in the standard RD problem.

We simulate the complexity of MM-$\mathbb {F}_{q}$ for RD, 2-RD, and 3-RD in Fig. 1.

• (a) The RD instances are estimated with $(q, m, n, k) = (2,200, 200, 100)$ and various even values $r = 2r'$ ($r'\in \{3..30\}$). The 2-RD instances are estimated with $(q, m, n, k, n_1, n_2) = (2,200, 200, 100, 100, 100)$ and various values $r_1=r_2\in \{3..30\}$.

• (b) The RD instances are estimated with $(q, m, n, k) = (2,100, 200, 100)$ and various even values $r\in \{6..40\}$. The 2-RD instances are estimated with $(q, m, n, k, n_1, n_2) = (2,100, 200, 100, 100, 100)$ and various values $r_1=r_2\in \{3..20\}$.

• (c) The RD instances are estimated with $(q, m, n, k) = (2,100, 300, 100)$ and various values $r = 3r'$ ($r'\in \{2..20\}$). The 3-RD instances are estimated with $(q, m, n, k, n_1, n_2, n_3) = (2,100, 300, 100, 100, 100, 100)$ and various values $r_1=r_2=r_3\in \{2..20\}$.

Our simulations become interesting as r increases. (a) and (b) in Fig. 1 show that, when r is divided equally into $(r_1, r_2)$, the exponential complexity allows to divide by a factor 2 for $r\ge 10$, i.e., $T_{2\text {-RD}}\approx \sqrt{T_\textrm{RD}}$. (c) in Fig. 1 shows that, when r is divided equally into $(r_1, r_2, r_3)$, the exponential complexity allows to divide by a factor 3 for $r\ge 12$, i.e., $T_{3\text {-RD}}\approx \root 3 \of {T_\textrm{RD}}$. The parameters sizes in (b) and (c) are exactly the case of cryptography parameters in Sect. 5.

Fig. 1.

Complexity trend of RD, 2-RD, and 3-RD by MM-$\mathbb {F}_{q}$.

4 The $\ell$-LRPC Codes and Decoding Algorithm

In this section, we define the blockwise LRPC ($\ell$-LRPC) codes, give its decoding algorithm, and analyze the decoding failure probability and the error-correcting capability. We find that the decoding algorithm can benefit from the blockwise structure: the decoding capacity can be significantly improved by a factor of $\ell$. For cryptography applications in Sect. 5, we finally give the $\ell$-Rank Support Recover ($\ell$-RSR) algorithm which is used to recover the support of the $\ell$-error.

4.1 The $\ell$-LRPC Codes

An $[n,k]_{{q^m}}$ LRPC code [4, 20] is defined by a parity-check matrix $\boldsymbol{H} \in \mathbb {F}_{q^m}^{(n-k)\times n}$ with small weight. Our $[n,k]_{{q^m}}$ $\ell$-LRPC code is defined by a parity-check matrix consisting of $\ell$ small-weight matrices of size $(n-k)\times n_i$.

Definition 4.1

(Blockwise LRPC ($\ell$-LRPC) Codes). Let $\ell , k\in \mathbb {N}$, $n_i, d_i\in \mathbb {N}$ for $i\in \{1..\ell \}$, and $n=\sum _{i=1}^{\ell }n_i$. Let $\boldsymbol{H}_i\in \mathbb {F}_{q^m}^{(n-k)\times n_i}$ be a matrix of weight $d_i$. Let the supports of $\ell$ matrices $\boldsymbol{H}_i$’s are mutually disjoint. An $[n,k]_{q^m}$ $\ell$-LRPC code of length n and dimension k is defined by a parity-check matrix $\boldsymbol{H} = (\boldsymbol{H}_1 \ \boldsymbol{H}_2 \ \cdots \ \boldsymbol{H}_\ell )\in \mathbb {F}_{q^m}^{(n-k)\times n}$.

Let $\boldsymbol{n} = (n_1,n_2,\dots ,n_\ell )$ and $\boldsymbol{d} =(d_1,d_2,\dots ,d_\ell )$ be vectors of positive integers. We denote the set of such parity-check matrices by $\mathcal {M}_{\boldsymbol{d}}^{\boldsymbol{n}}(k)$. Let $F_i$ be the support of dimension $d_i$ of $\boldsymbol{H}_i$. Because all supports are mutually disjoint, the matrix $\boldsymbol{H}$ can be viewed as the matrix of weight $d = \sum _{i=1}^{\ell }d_i$ and support $F = \sum _{i=1}^{\ell }F_i$.

We next consider decoding algorithms for two error distributions: the $\ell$-errors and the standard rank metric errors. In this subsection, we analyze the case of decoding the $\ell$-errors. The decoding algorithm is also applied to ROLLO in Sect. 5. The latter is presented in Appendix D of full version [40], where we show that for the standard errors, the $\ell$-LRPC code has the same decoding capacity as the standard LRPC code.

4.2 Decoding $\ell$-Errors

Let $\boldsymbol{r} =(r_1,\dots ,r_\ell )$ be a vector of positive integers. Consider an $[n,k]_{q^m}$ $\ell$-LRPC code $\mathcal {C}$ with generator matrix $\boldsymbol{G} \in \mathbb {F}_{q^m}^{k\times n}$ and parity-check matrix $\boldsymbol{H} = (\boldsymbol{H}_1 \ \boldsymbol{H}_2 \ \cdots \ \boldsymbol{H}_\ell )\in \mathcal {M}_{\boldsymbol{d}}^{\boldsymbol{n}}(k)$ of support $(F_1,F_2,\ldots , F_\ell )$. Let $\boldsymbol{y} = \boldsymbol{m} \boldsymbol{G} + \boldsymbol{e}$ be a received word, where $\boldsymbol{m} \in \mathbb {F}_{q^m}^{k}$ and $\boldsymbol{e} = (\boldsymbol{e}_1, \boldsymbol{e}_2,\ldots ,\boldsymbol{e}_\ell ) \in \mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ with the support $(E_1,E_2,\ldots ,E_\ell )$. The syndrome $\boldsymbol{s} = \boldsymbol{H}\boldsymbol{y}^{\top } = \boldsymbol{H}\boldsymbol{e}^{\top } =\sum _{j=1}^{\ell }\boldsymbol{H}_j\boldsymbol{e}_j^{\top }$.

The general idea of decoding $\ell$-error $\boldsymbol{e}$ uses the fact that the subspace $S = \langle s_1, s_2, \ldots , s_{n-k}\rangle _{\mathbb {F}_q}$ generated by $\boldsymbol{s}$ enables one to recover the space $\sum _{i=1}^{\ell }E_iF_i$. Once obtaining $\sum _{j=1}^{\ell }E_jF_j$, one recovers $E_1,E_2,\ldots ,E_\ell$ and computes the support $E = \sum _{j=1}^{\ell }E_j$ of the error $\boldsymbol{e}$. Finally, the coordinates of $\boldsymbol{e}$ are computed by solving a linear system. The decoding algorithm is described in Algorithm 1.

4.3 Correctness of the Decoding Algorithm

The correctness of Algorithm 1 depends on the recovery of correct $E_j$, which requires $\textrm{dim} S = \textrm{dim}\left( \sum _{j=1}^{\ell }E_jF_j\right)$ and $\textrm{dim}\left( \bigcap _{i=1}^{d_j}S_{ji}\right) = r_j$ for $j\in \{1 .. \ell \}$. We assume that these two conditions hold.

Step 1: the first step of the algorithm is obvious.

Step 2: we prove that $E_j=\bigcap _{i=1}^{d_j}S_{ji}$ for $j\in \{1 .. \ell \}$. Let $(\varepsilon _{j1},\varepsilon _{j2},\ldots ,\varepsilon _{jr_j})\in \mathbb {F}_{q^m}^{r_j}$ be the basis of $E_j$. Since $\boldsymbol{s}=\boldsymbol{H}\boldsymbol{e}^{\top } =\sum _{j=1}^{\ell }\boldsymbol{H}_j\boldsymbol{e}_j^{\top }$, $\boldsymbol{H}\in \mathcal {M}_{\boldsymbol{d}}^{\boldsymbol{n}}(k)$ is a matrix of support $(F_1,F_2,\ldots , F_\ell )$, and $\boldsymbol{e}\in \mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ is an $\ell$-error of support $(E_1,E_2,\ldots ,E_\ell )$, we have that the entries of $\boldsymbol{H}_j\boldsymbol{e}_j^{\top }$ respectively lie in $E_jF_j$. Thus, $S \subset \sum _{j=1}^{\ell }E_jF_j$. By assumption $\textrm{dim} S = \textrm{dim}\left( \sum _{j=1}^{\ell }E_jF_j\right)$, we have $S=\sum _{j=1}^{\ell }E_jF_j$. Further, for any $i\in \{1..d_j\}$, since $f_{ji}\varepsilon _{j\kappa }\in \sum _{j=1}^{\ell }E_jF_j$ for all $\kappa \in \{1..r_j\}$, we have $\varepsilon _{j\kappa }\subset S_{ji} = \{f_{ji}^{-1}x: x\in S \}\Rightarrow E_j \subset S_{ji}$. Then, $E_j\subset \bigcap _{i=1}^{d_j}S_{ji}$. By assumption $\textrm{dim}\left( \bigcap _{i=1}^{d_j}S_{ji}\right) = r_j$, we have $E_j=\bigcap _{i=1}^{d_j}S_{ji}$.

Step 3: one expresses $\boldsymbol{e}$ under the basis $\boldsymbol{\varepsilon }$ of E:

$$\begin{aligned}\begin{gathered} \boldsymbol{e} = (e_1,e_2,\ldots ,e_n)= (\varepsilon _1,\varepsilon _2,\ldots ,\varepsilon _r) \begin{pmatrix} e_{11}&{} e_{12}&{} \cdots &{} e_{1n} \\ e_{21}&{} e_{22}&{} \cdots &{} e_{2n}\\ \vdots &{} \vdots &{} \cdots &{} \vdots \\ e_{r1}&{} e_{r2}&{}\cdots &{} e_{rn} \end{pmatrix} = (\varepsilon _1,\varepsilon _2,\ldots ,\varepsilon _r) \begin{pmatrix} \overline{\boldsymbol{e}}_1 \\ \overline{\boldsymbol{e}}_2\\ \vdots \\ \overline{\boldsymbol{e}}_r \end{pmatrix}, \end{gathered}\end{aligned}$$

where $\overline{\boldsymbol{e}}_i = (e_{i1}, e_{i2}, \ldots , e_{in})$ for $i \in \{1 .. r\}$, and computes $\overline{\boldsymbol{e}}_i$ from Eq. (15):

$$\begin{aligned} \boldsymbol{H} \boldsymbol{e}^{\top } &= \begin{pmatrix} \boldsymbol{h}_1 \\ \boldsymbol{h}_2\\ \vdots \\ \boldsymbol{h}_{n-k} \end{pmatrix}(\overline{\boldsymbol{e}}^{\top }_1,\overline{\boldsymbol{e}}^{\top }_2,\ldots ,\overline{\boldsymbol{e}}^{\top }_r) \begin{pmatrix} \varepsilon _1 \\ \varepsilon _2\\ \vdots \\ \varepsilon _r \end{pmatrix}\nonumber \\ &= \begin{pmatrix} \boldsymbol{h}_{1}\varepsilon _1 &{} \boldsymbol{h}_{1}\varepsilon _2&{} \cdots &{} \boldsymbol{h}_{1}\varepsilon _r \\ \boldsymbol{h}_{2}\varepsilon _1 &{} \boldsymbol{h}_{2}\varepsilon _2&{} \cdots &{} \boldsymbol{h}_{2}\varepsilon _r \\ \vdots &{} \vdots &{} \cdots &{} \vdots \\ \boldsymbol{h}_{n-k}\varepsilon _1 &{} \boldsymbol{h}_{n-k}\varepsilon _2&{} \cdots &{} \boldsymbol{h}_{n-k}\varepsilon _r \\ \end{pmatrix} \begin{pmatrix} \overline{\boldsymbol{e}}^{\top }_1 \\ \overline{\boldsymbol{e}}^{\top }_2\\ \vdots \\ \overline{\boldsymbol{e}}^{\top }_r \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2\\ \vdots \\ s_{n-k} \end{pmatrix}, \end{aligned}$$

(15)

where $\boldsymbol{h}_j$ is the j-th row of $\boldsymbol{H}$.

There are two methods to solve Eq. (15):

• 1. Solve-$\mathbb {F}_{q^m}$: Obtaining a linear system with nr unknowns and $m(n-k)$ equations over $\mathbb {F}_{q}$ by expressing $\boldsymbol{h}_j\varepsilon _i$ and $s_j$ as a matrix $\textrm{Mat}(\boldsymbol{h}_j\varepsilon _i)\in \mathbb {F}^{m\times n}_{q}$ and column vector of length m, respectively, $\underline{\mathrm{under\,the\,basis} \ \boldsymbol{\alpha }}$. The system has one solution with overwhelming probability if $nr\le m(n-k)$;

• 2. Solve-EF: As $\sum _{j=1}^{\ell }E_jF_j \subset EF$, where $F = \sum _{j=1}^{\ell }F_j$, the entries of $\boldsymbol{h}_j\varepsilon _i$ and $s_j$ lie in EF. We then can express Equation (15) $\underline{\mathrm{under\,the\,basis\,of} \ EF }$ by expressing $\boldsymbol{h}_j\varepsilon _i$ and $s_j$ as a matrix of $rd\times n$ and column vector of length rd, respectively. Finally, we will obtain a linear system with nr unknowns and $rd(n-k)$ equations over $\mathbb {F}_{q}$. The system has one solution with overwhelming probability if $nr\le rd(n-k)$, where $d = \sum _{j=1}^{\ell }d_j$ and $r = \sum _{j=1}^{\ell }r_j$.

Once all $\overline{\boldsymbol{e}}_i$’s are obtained, one can recover $\boldsymbol{e}$. We experimentally find that Solve-$\mathbb {F}_{q^m}$ is more efficient than Solve-EF on SageMath 9.0.

Step 4: the fourth step of the algorithm is obvious.

4.4 The Decoding Complexity

The most costly part is the intersection in Step 2 and solving linear systems in Step 3. The intersection $\bigcap _{i=1}^{d_j}S_{ji}$ of spaces $S_{ji}$ of dimension $\mu = \sum _{j=1}^{\ell }r_jd_j$ costs $\mathcal {O}\left( 4\mu ^2m\sum _{j=1}^{\ell }d_j\right)$ operations in $\mathbb {F}_{q}$ for $j\in \{1..\ell \}$. By Solve-EF, expressing $\boldsymbol{h}_j\varepsilon _i$ as a matrix of $rd\times n$ in the basis of EF consists in solving n linear systems with rd unknowns and m equations. This costs $(n-k)nr^{\omega +1}d^\omega$ operations in $\mathbb {F}_{q}$. Expressing $s_j$ as a column vector of length rd in the basis of EF consists in solving a linear system with rd unknowns and m equations. This costs $(n-k)(rd)^\omega$ operations in $\mathbb {F}_{q}$. Solving the linear system $\boldsymbol{H}\boldsymbol{e}^{\top } = \boldsymbol{s}$ with nr unknowns and $rd(n-k)$ equations costs about $\mathcal {O}((nr)^\omega )$ operations in $\mathbb {F}_{q}$. Thus, the complexity of the decoding algorithm is bounded by $\mathcal {O}((nr)^\omega )$.

4.5 Decoding Failure Probability

By the correctness assumption of Algorithm 1, two cases can make the algorithm fail: (i) $\textrm{dim} S < \textrm{dim}\left( \sum _{j=1}^{\ell }E_jF_j\right)$; (ii) $\textrm{dim}\left( \bigcap _{i=1}^{d_j}S_{ji}\right) > r_j$ for $j\in \{1 .. \ell \}$. Propositions 4.2 and 4.3 estimate the probability of two cases.

Proposition 4.2

The probability of $\textrm{dim} S < \textrm{dim}\left( \sum _{j=1}^{\ell }E_jF_j\right)$ is bounded by $q^{-(n-k-\mu )}$ where $\mu = \sum _{j=1}^{\ell }r_jd_j$.

Proposition 4.3

The probability that there is $j\in \{1 .. \ell \}$ such that is bounded by $\sum _{j=1}^{\ell }q^{\mu -r_j}\left( \frac{q^{\mu -r_j}-1}{q^{m-r_j}}\right) ^{d_j-1}$ where $\mu = \sum _{j=1}^{\ell }r_jd_j$.

We give the detailed proofs for Propositions 4.2 and 4.3 in Appendices (C.8 and C.9) of full version [40]. Combining these two propositions, we deduce the decoding failure probability of Algorithm 1 in Theorem 4.4.

Theorem 4.4

Under assumptions that $S_{ji}$ behaves as independent and random subspaces containing $E_j$, the decoding failure probability of Algorithm 1 is bounded by $q^{-(n-k-\mu )}+\sum _{j=1}^{\ell }q^{\mu -r_j}\left( \frac{q^{\mu -r_j}-1}{q^{m-r_j}}\right) ^{d_j-1}$ where $\mu = \sum _{j=1}^{\ell }r_jd_j$.

The analysis shows that the failure probability can be made arbitrarily small.

4.6 Error Correction Capability

From the correctness of Algorithm 1, we have $nr\le rd(n-k) \Rightarrow d \ge \frac{n}{n-k}$. Under this condition, the decoding capacity is constrained by $\sum _{j=1}^{\ell }r_jd_j \le n-k$. The following Theorem 4.5 is obvious.

Theorem 4.5

When $d_1=d_2=\cdots =d_\ell$, the $\ell$-LRPC code allows to decode $\ell$-errors of weight up to $r=\sum _{j=1}^{\ell }r_j=\frac{n-k}{d_1}$. By setting $d_1=d_2=\cdots =d_\ell$= 2, it can decode $\ell$-errors of weight up to $\frac{n-k}{2}$.

Theorem 4.5 implies that the decoding algorithm can benefit from the blockwise structure: the decoding capacity can be significantly improved by a factor of $\ell$. An $[n,k]_{q^m}$ LRPC code defined by a parity-check matrix of weight d can decode the standard errors of weight up to $r = \frac{n-k}{d}$ with a DFR of about $q^{rd - n-k}$. Let $\ell |d$, $d_i=d/\ell$, $\boldsymbol{H} \in \mathcal {M}_{\boldsymbol{d}}^{\boldsymbol{n}}(k)$ be a parity-check matrix of an $[n,k]_{q^m}$ $\ell$-LRPC code. This $\ell$-LRPC code can decode $\ell$-errors in $\mathcal {S}_{\boldsymbol{r}}^{\boldsymbol{n}}$ of weight up to $\ell r$ with the same DFR, which comes from

$$\sum _{j=1}^{\ell }r_jd_j =\frac{d}{\ell }\sum _{j=1}^{\ell }r_j \le n-k \ \ \Longrightarrow \ \ \sum _{j=1}^{\ell }r_j \le \frac{\ell (n-k)}{d} = \ell r.$$

For example, fixing $d=4$, $r=8$, and the DFR of $q^{32-n-k}$, an $[n,k]_{q^m}$ LRPC code can decode errors of weight 8, but an $[n,k]_{q^m}$ 2-LRPC codes with parameter $\boldsymbol{d}= (d_1,d_2)=(2,2)$ can decode $\ell$-errors with parameter $\boldsymbol{r}= (r_1,r_2)=(8,8)$ of weight up to $r = r_1 + r_2 = 16$.

For the accurate failure probability of decoding errors of maximal weight, it is hard to estimate theoretical value and the value in Theorem 4.4 seems not practical for $q>2$. We give a simulation of the decoding algorithm for 2-LRPC codes on SageMath 9.0. When $\ell =2$ and $d_1=d_2=2$, the 2-LRPC codes can decode 2-errors of weight up to $\frac{n-k}{2}$. The simulated result shows that the failure probability is about 0.73 for $q=2$. Figure 2 shows the decreasing trend of the failure probability as q increases. For $q=2$, the failure probability is bounded by $q^{-\left( n-k-\sum _{j=1}^{2}r_jd_j\right) }=1$. For $q>2$, the upper bound of failure probability seems to be $q^{-\left( n-k+1-\sum _{j=1}^{2}r_jd_j\right) }$. The code parameters are $(m,n,k,n_1,n_2,r_1,r_2,d_1,d_2) = (43,44,22,22,22,6,5,2,2)$ for $q = 2, 3, 5, 7, 11, 13, 17, 19$.

Fig. 2.

Simulated failure probability of decoding 2-errors of weight $\frac{n-k}{2}$ for 2-LRPC codes.

4.7 The $\ell$-RSR Algorithm

For cryptography applications in Sect. 5, one just recovers the support of the error. In this subsection, we give the $\ell$-Rank Support Recover ($\ell$-RSR) algorithm (Algorithm 2), which is a shortened version of the decoding Algorithm 1 without the computation of the error. The correctness follows Algorithm 1. The failure probability follows Theorem 4.4. The cost is only the recovery of support and is given in Subsect. 4.4.

5 Applications to Cryptography

In this section, we apply the ideal variants of the $\ell$-RD problem and the $\ell$-LRPC codes to improve RQC [30] and ROLLO [29] kept in NIST PQC Round 2. Due to space limitations, we present the ideal variants in Appendix E of full version [40] and only list improved schemes and comparisons in this section.

RQC [30] and ROLLO [29] include Public Key Encryptions (PKE) and Key Encapsulation Mechanisms (KEM). RQC is an IND-CCA2 KEM built from its IND-CPA PKE construction based on the HHK transformation [26] and uses the Gabidulin codes. We only consider the PKE version of RQC for simplicity. ROLLO is the merge of the three cryptosystems Laker, Locker, and Ouroboros-R which all share the same decryption algorithm for the LRPC codes. Laker (ROLLO-I) and Ouroboros-R (ROLLO-III) are two IND-CPA KEM. Locker (ROLLO-II) is an IND-CCA2 PKE scheme built from its IND-CPA PKE construction based on the HHK transformation [26]. We only consider the IND-CPA PKE version of Locker for simplicity.

5.1 Improved RQC

In this subsection, we improve RQC [30] based on the 2-IRSD and 3-IRSD problems. Our RQC uses three types of codes: a Gabidulin code $\mathcal {C}$ [18] with generator matrix $\boldsymbol{G}\in \mathbb {F}_{q^m}^{k\times n}$ which can correct up to $\lfloor \frac{n-k}{2}\rfloor$ errors by a deterministic decoding algorithm $\mathcal {C}.\textsf{Decode}$ [6, 27], a random $[2n, n]_{q^m}$-ideal code with parity-check matrix $(\boldsymbol{1} \ \ \boldsymbol{h})$, and a random $[3n, n]_{q^m}$-ideal code with parity-check matrix $\begin{pmatrix} \boldsymbol{1} \ {} &{} \ \boldsymbol{0} \ {} &{} \ \boldsymbol{h} \\ \boldsymbol{0} \ {} &{}\ \boldsymbol{1} \ {} &{} \ \boldsymbol{s} \end{pmatrix}$.

Fig. 3.

Description of our RQC PKE scheme.

Correctness. We have $\boldsymbol{v}-\boldsymbol{u}\boldsymbol{y} = \boldsymbol{m} \boldsymbol{G} + \boldsymbol{x}\boldsymbol{r}_2 + \boldsymbol{e} -\boldsymbol{r}_1\boldsymbol{y}$. The correctness of our encryption scheme is based on the decoding capability of the Gabidulin code $\mathcal {C}$, i.e., the error term $\boldsymbol{x}\boldsymbol{r}_2 + \boldsymbol{e} -\boldsymbol{r}_1\boldsymbol{y}$ must fulfill: $\left\| \boldsymbol{x}\boldsymbol{r}_2 + \boldsymbol{e} -\boldsymbol{r}_1 \boldsymbol{y}\right\| _\textrm{R}= w_{\boldsymbol{x}}w_{\boldsymbol{r}_2}+w_{\boldsymbol{y}}w_{\boldsymbol{r}_1}+w_{\boldsymbol{e}}\le \lfloor \frac{n-k}{2}\rfloor$.

In the decryption step, one needs to decode an error of weight $w_{\boldsymbol{x}}w_{\boldsymbol{r}_2}+w_{\boldsymbol{y}}w_{\boldsymbol{r}_1}+w_{\boldsymbol{e}}$. This weight increase is slow, which brings the gain of decoding capacity and saves code parameters. Although the $\ell$-errors can also be used to speed up the attacks for decoding problems, the performance in Table 3 shows that the gain in the decoding method greatly outweighs the gain in the attacks, and eventually allows scheme with small parameters.

Theorem 5.1

Under the decisional 2-IRSD and 3-IRSD problems, our RQC PKE in Fig. 3 is IND-CPA secure.

Proof

The proof is similar to [30] with 2-IRSD and 3-IRSD instances. The two instances are defined by

$$\begin{aligned} \boldsymbol{s} = \begin{pmatrix} \boldsymbol{1} \ {} & \ \boldsymbol{h} \end{pmatrix}\begin{pmatrix} \boldsymbol{x} \\ \boldsymbol{y} \end{pmatrix}, \ \ \begin{pmatrix} \boldsymbol{u} \\ \boldsymbol{v}-\boldsymbol{m}\boldsymbol{G} \end{pmatrix} = \begin{pmatrix} \boldsymbol{1} \ {} &{} \ \boldsymbol{0} \ {} &{} \ \boldsymbol{h} \\ \boldsymbol{0} \ {} &{}\ \boldsymbol{1} \ {} &{} \ \boldsymbol{s} \end{pmatrix} \begin{pmatrix} \boldsymbol{r}_1 \\ \boldsymbol{r}_2\\ \boldsymbol{e} \end{pmatrix}. \end{aligned}$$

   $\square$

5.2 Improved Lake (ROLLO-I)

In this subsection, we improve Lake based on the 2-IRSD problem and the 2-ILRPC codes indistinguishability problem. Our Laker has three building blocks: a random $[2n, n]_{q^m}$ 2-ILRPC code with parity-check matrix $(\boldsymbol{x} \ \ \boldsymbol{y})$, the algorithm $2\text {-}\textsf{RSR}$ (see Algorithm 2), and a random $[2n, n]_{q^m}$-ideal code with parity-check matrix $(\boldsymbol{1} \ \ \boldsymbol{h})$.

Fig. 4.

Description of our Lake KEM scheme.

5.3 Improved Locker (ROLLO-II)

Locker (ROLLO-II [29]) is a PKE scheme and is obtained from ROLLO-I. In this subsection, we improve ROLLO-II by the 2-IRSD problem. As our Lake, our Locker has three building blocks: a random $[2n, n]_{q^m}$ 2-ILRPC code with parity-check matrix $(\boldsymbol{x} \ \ \boldsymbol{y})$, the algorithm $2\text {-}\textsf{RSR}$ (see Algorithm 2), and a random $[2n, n]_{q^m}$-ideal code with parity-check matrix $(\boldsymbol{1} \ \ \boldsymbol{h})$.

Fig. 5.

Description of our Locker PKE scheme.

In Laker and Locker, the decapsulation and decryption steps obtain the support of $(\boldsymbol{e}_1,\boldsymbol{e}_2)$ from $\boldsymbol{x}\boldsymbol{e}_1 - \boldsymbol{y}\boldsymbol{e}_2$ of weight $r_1d_1 + r_2d_2$. This weight increase implies that the parameters $(r_1,r_2)$ and $(d_1,d_2)$ can be increased a lot. Although the 2-errors and the 2-LRPC codes can also be used to speed up the attacks for decoding problems, the performance in Tables 4, 5 and 7 shows that the gain in the decoding method outweighs the gain in the attacks, and eventually allows schemes with small parameters.

Theorem 5.2

Under the 2-ILRPC codes indistinguishability, and 2-IRSR problems our Lake KEM in Fig. 4 and Locker PKE in Fig. 5 are IND-CPA secure in the random oracle model.

Proof

The proofs are similar to [29] with the 2-ILRPC codes indistinguishability and 2-IRSR instances. The two instances are defined by

$$\begin{aligned} \boldsymbol{0} = \begin{pmatrix} \boldsymbol{1} \ {} & \ \boldsymbol{h} \end{pmatrix}\begin{pmatrix} \boldsymbol{y}\\ -\boldsymbol{x} \end{pmatrix}, \ \ \boldsymbol{c} = \begin{pmatrix} \boldsymbol{1} \ {} & \ \boldsymbol{h} \end{pmatrix}\begin{pmatrix} \boldsymbol{e}_1 \\ \boldsymbol{e}_2 \end{pmatrix}. \end{aligned}$$

   $\square$

5.4 Improved Ouroboros-R (ROLLO-III)

In this subsection, we improve ROLLO-III based on the 2-IRSD and 3-IRSD problems. Our Ouroboros-R has three building blocks: a 3-ILRPC code with parity-check matrix $(\boldsymbol{h}_0 \ \boldsymbol{h}_1 \ \boldsymbol{1})$, the algorithm $\text {3-}\textsf{RSR}$ (see Algorithm 2), a $[2n, n]_{q^m}$-ideal code with parity-check matrix $(\boldsymbol{1} \ \boldsymbol{f}_1)$, and a $[3n, n]_{q^m}$-ideal code with parity-check matrix $\begin{pmatrix} \boldsymbol{1} &{} \boldsymbol{0} &{} \boldsymbol{f}_0 \\ \boldsymbol{0} &{} \boldsymbol{1} &{} \boldsymbol{f}_1 \end{pmatrix}$.

Fig. 6.

Description of our Ouroboros-R KEM scheme.

In the decapsulation step, one obtains the support of $(\boldsymbol{e}_0,\boldsymbol{e}_1)$ from $\boldsymbol{h}_1\boldsymbol{e}_1 - \boldsymbol{h}_0\boldsymbol{e}_0 + \boldsymbol{e}$ of weight $r_1d_1 + r_2d_2 + r_3$. This weight increasing implies that the parameters $(r_1,r_2,r_3)$ and $(d_1,d_2)$ can be increased a lot. Although the blockwise errors and LRPC codes can also be used to speed up the attacks for decoding problems, the performance in Tables 6 and 7 shows that the gain in the decoding method outweighs the gain in the attacks, and eventually allows scheme with small parameters.

Theorem 5.3

Under the decisional 2-IRSD and 3-IRSD problems, our Ouroboros-R KEM in Fig. 6 is IND-CPA secure in the random oracle model.

Proof

The proof is similar to [2] with the (decisional) 2-IRSD and 3-IRSD instances. The two instances are defined by

$$\begin{aligned} \boldsymbol{f}_0 = \begin{pmatrix} \boldsymbol{1} \ {} & \ \boldsymbol{f}_1 \end{pmatrix}\begin{pmatrix} \boldsymbol{h}_1 \\ \boldsymbol{h}_0 \end{pmatrix}, \quad \begin{pmatrix} \boldsymbol{c}_0 \\ \boldsymbol{c}_1 \end{pmatrix} = \begin{pmatrix} \boldsymbol{1} \ {} &{} \ \boldsymbol{0} \ {} &{} \ \boldsymbol{f}_0 \\ \boldsymbol{0} \ {} &{}\ \boldsymbol{1} \ {} &{} \ \boldsymbol{f}_1 \end{pmatrix} \begin{pmatrix} \boldsymbol{e} \\ \boldsymbol{e}_0\\ \boldsymbol{e}_1 \end{pmatrix}. \end{aligned}$$

   $\square$

5.5 Performance and Comparison

In this subsection, we compare performance of our RQC and ROLLO with original versions.

In Tables 3, 4 and 5, parameters are chosen in two principles. First, the hardness of decoding problems (the 2-IRSD and 3-IRSD problems) is ensured to reach the target security level. The hardness is estimated by our complexity formulas. Secondly, the error-correcting capacity of rank metric codes is ensured to satisfy the decryption correctness condition. $[n,k]_{q^m}$ Gabidulin codes used in RQC require $k < n \le m$ and correct errors of weight up to $\lfloor (n-k)/2\rfloor$; in the decryption step, the weight of the decoded errors must $\le \lfloor (n-k)/2\rfloor$. The $\ell$-LRPC codes used in ROLLO must satisfy a reasonable DFR in Theorem 4.4. In Tables 3 and 6, “2n” (“3n”) represents the complexity of solving the 2-IRSD (3-IRSD) instances in RQC and Ouroboros-R. In Tables 4 and 5, the structural attack is estimated with parameters $(m,n,k,r_1,r_2) = \left( m,2n-\lfloor \frac{n}{d}\rfloor ,n-\lfloor \frac{n}{d}\rfloor ,d_1.d_2\right)$; the message attack is estimated with parameters $(m,n,k,r_1,r_2) = (m,2n,n,r_1,r_2)$.

From Tables (3, 4, 5 and 6), our parameters sizes are smaller than those of the original ones due to the blockwise stricture, which brings a low complexity redundancy, improved the public key/ciphertext sizes, and more efficient implementations. The improved performance benefits from that the gain of using $\ell$-errors and $\ell$-LRPC codes in decoding capacity outweighs the complexity loss in solving the $\ell$-RD problem. As an example, we provide concrete timings of implementations for our ROLLO and original versions (Table 7). The benchmark is performed on Intel(R) Core(TM) i5-7440HQ CPU@ 3.40 GHz with SageMath 9.0. The tests are available online at https://github.com/YCSong232431/NH-ROLLO. Note that, we do not compare with most recent works [12, 32], where the authors constructed a series of efficient PKE and KEM schemes without ideal structure by proposing augmented Gabidulin codes and LRPC codes with multiple syndromes. Our techniques are different from [12, 32] and we only consider cryptosystems with ideal structure and one syndrome.

Table 3. Comparison of parameters and sizes for RQC.

pks: $\left( \left\lceil \frac{mn}{8}\right\rceil +40\right)$ bytes; cts: $\left( 2\left\lceil \frac{mn}{8}\right\rceil +64\right)$ bytes; total = pks + cts.

Table 4. Comparison of parameters and sizes for Lake (ROLLO-I).

pks: $\left\lceil \frac{mn}{8}\right\rceil$ bytes. cts: $\left\lceil \frac{mn}{8}\right\rceil$ bytes.

Table 5. Comparison of parameters and sizes for Locker (ROLLO-II).

pks: $\left\lceil \frac{mn}{8}\right\rceil$ bytes; cts: $\left\lceil \frac{mn}{8}\right\rceil + 64$ bytes. To obtain the IND-CCA2 security, another hash is added to the ciphertext such that cts = $\left\lceil \frac{mn}{8}\right\rceil + 2*64$ bytes.

Table 6. Comparison of parameters and sizes for Ouroboros-R (ROLLO-III).

pks: $\left( \left\lceil \frac{mn}{8}\right\rceil + 40\right)$ bytes and cts: $\left\lceil \frac{2mn}{8}\right\rceil$ bytes. We update DFR of Ouroboros-R.

Table 7. Timings comparisons of our ROLLO and original ROLLO.

6 Conclusion and Future Work

In this paper, we studied blockwise structures in rank-based cryptosystems and introduced $\ell$-errors, $\ell$-RD problem, and $\ell$-LRPC codes. They are natural generalizations of the standard errors, RD problem, and LRPC codes. We found that (1) the blockwise structure does not ease the problem too much: the $\ell$-RD problem is still exponentially hard for appropriate choices of $\ell >1$; (2) the decoding algorithm can benefit from the blockwise structure: the decoding capacity can be significantly improved by a factor of $\ell$. Interestingly, the gain of the decoding capacity outweighs the complexity loss in solving the $\ell$-RD problem, which allows to improve RQC and ROLLO. For 128-bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece.

Recent works [3, 12, 32] proposed unstructured PKE and KEM without ideal structure for more reliable security. We would in next work analyze the complexity of blockwise rank support learning problem and apply the $\ell$-LRPC codes with multiple syndromes to improve unstructured schemes.