Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

Abstract

We address the problem of decoding Gabidulin codes beyond their unique error-correction radius. The complexity of this problem is of importance to assess the security of some rank-metric code-based cryptosystems. We propose an approach that introduces row or column erasures to decrease the rank of the error in order to use any proper polynomial-time Gabidulin code error-erasure decoding algorithm. The expected work factor of this new randomized decoding approach is a polynomial term times $q^{m(n-k)-w(n+m)+w^2+\min \{2\xi (\frac{n+k}{2}-\xi ),wk\} }$, where n is the code length, q the size of the base field, m the extension degree of the field, k the code dimension, w the number of errors, and $\xi := w-\tfrac{n-k}{2}$. It improves upon generic rank-metric decoders by an exponential factor.

The work of J. Renner and A. Wachter-Zeh was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 801434).

Sven Puchinger has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement no. 713683 (COFUNDfellowsDTU).

Appendices

A Proof of Lemma 1

The number of q-vector spaces of dimension v, which intersections with $\mathcal {U}$ have dimension at least $\omega$, is equal to

$$\begin{aligned} \sum _{i=\omega }^{\min \{u,v\}}\left[ \begin{matrix} \ell -u \\ v-i \end{matrix} \right] _{q} \left[ \begin{matrix} u \\ i \end{matrix} \right] _{q}q^{(u-i)(v-i)} = \sum _{j=\max \{0,v-u\}}^{v-\omega }\left[ \begin{matrix} \ell -u \\ j \end{matrix} \right] _{q} \left[ \begin{matrix} u \\ v-j \end{matrix} \right] _{q}q^{j(u-v+j)}, \end{aligned}$$

see [8]. Since the total number of v-dimensional subspaces of a $\ell$-dimensional space is equal to $\left[ \begin{matrix} \ell \\ v \end{matrix} \right] _{q}$, the probability

$$\begin{aligned} \mathrm {Pr}[\dim (\mathcal {U}\cap \mathcal {V}) \ge \omega ]&=\frac{ \sum _{i=\omega }^{\min \{u,v\}} \left[ \begin{matrix} \ell -u \\ v-i \end{matrix} \right] _{q} \left[ \begin{matrix} u \\ i \end{matrix} \right] _{q} q^{(u-i)(v-i)} }{\left[ \begin{matrix} \ell \\ v \end{matrix} \right] _{q}} \\&= \frac{\sum _{j=\max \{0,v-u\}}^{v-\omega }\left[ \begin{matrix} \ell -u \\ j \end{matrix} \right] _{q} \left[ \begin{matrix} u \\ v-j \end{matrix} \right] _{q}q^{j(u-v+j)}}{\left[ \begin{matrix} \ell \\ v \end{matrix} \right] _{q}}. \end{aligned}$$

Using the upper bound on the Gaussian coefficient derived in [20, Lemma 4], it follows that

$$\begin{aligned} \mathrm {Pr}[\dim (\mathcal {U}\cap \mathcal {V}) \ge \omega ]&\le 16\sum _{j=\max \{0,v-u\}}^{v-\omega } q^{j(\ell -u-j)+v(u-v+j)-v(\ell -v)}\\&=16\sum _{j=\max \{0,v-u\}}^{v-\omega } q^{(j-v)(\ell -u-j)}\\&\le 16 ~(\min \{u,v\}+1-\omega ) q^{(j^{*}-v)(\ell -u-j^{*})}, \end{aligned}$$

where $j^{*}:= \min \{ v-\omega , \frac{1}{2}(\ell +v-u) \}$. The latter inequality follows from the fact that the term $(j-v)(\ell -u-j)$ is a concave function in j and is maximum for $j = \frac{1}{2}(\ell +v-u)$.   $\square$

B Guessing Jointly the Column and Row Space of the Error

We analyze the success probability of decoding to a specific codeword (i.e., the analog of Lemma 2) for guessing jointly the row and the column space of the error.

Lemma 4

Let $\varvec{r}\in \mathbb {F}_{q^m}^n$ be defined as in Sect. 2.2, where neither parts of the error row space nor column space are known, i.e., $\gamma =\rho =0$ and $t = w$. The probability that an error-erasure decoder using a random

• $\delta _r$-dimensional guess of the error row space and a

• $\delta _c$-dimensional guess of the error column space,

where $\delta _r+\delta _c =: \delta \in [2\xi ,n-k]$, outputs $\varvec{m}\varvec{G}_\mathrm {Gab}$ is upper-bounded by

$$\begin{aligned} \frac{\displaystyle \sum _{i=\lceil \xi + \frac{\delta }{2}\rceil }^{\displaystyle \min \{\delta ,w\}} \sum _{\begin{array}{c} 0 \le w_r,w_c \le i \\ w_r+w_c=i \end{array}} \left[ \begin{matrix} n-w \\ \delta _r-w_r \end{matrix} \right] _{q} \left[ \begin{matrix} w \\ w_r \end{matrix} \right] _{q}q^{(w-w_r)(\delta _r-w_r)} \left[ \begin{matrix} m-w \\ \delta _c-w_c \end{matrix} \right] _{q} \left[ \begin{matrix} w \\ w_c \end{matrix} \right] _{q}q^{(w-w_c)(\delta _c-w_c)}}{\left[ \begin{matrix} n \\ \delta _r \end{matrix} \right] _{q}\left[ \begin{matrix} m \\ \delta _c \end{matrix} \right] _{q}}. \end{aligned}$$

Proof

The statement follows by the same arguments as Lemma 2, where we computed the probability that the row space of a random vector space of dimension $\delta$ intersects with the w-dimensional row space of the error in i dimensions (where i must be sufficiently large to apply the error erasure decoder successfully). Here, we want that a random guess of $\delta _r$- and $\delta _c$-dimensional vector spaces intersect with the row and column space of the error in exactly $w_r$ and $w_c$ dimensions, respectively. We sum up over all choices of $w_r$ and $w_c$ that sum up to an i that is sufficiently large to successfully apply the error erasure decoder. This is an optimistic argument since guessing correctly $w_r$ dimensions of the row and $w_c$ dimensions of the column space of the error might not reduce the rank of the error by $w_r+w_c$. However, this gives an upper bound on the success probability.    $\square$

Example 1 shows that guessing row and column space jointly is not advantageous for some specific parameters.

Example 1

Consider the example $q=2$, $m=n=24$, $k=16$, $w=6$. Guessing only the row space of the error with $\delta = 4$ succeeds with probability $1.66 \cdot 10^{-22}$ and joint guessing with $\delta _r = \delta _c = 2$ succeeds with probability $1.93 \cdot 10^{-22}$. Hence, it is advantageous to guess only the row space (or due to $m=n$ only the column space). For a larger example with $m=n=64$, $k=16$, and $w=19$, the two probabilities are almost the same, $\approx 5.27 \cdot 10^{-82}$ (for $\delta =32$ and $\delta _r=\delta _c=16$).