Fast Kötter–Nielsen–Høholdt Interpolation over Skew Polynomial Rings

Skew polynomials are a class of non-commutative polynomials, that were introduced by Ore (1933b) and that have a variety of applications in computer science, coding theory and cryptography. The non-commutativity stems from the multiplication rule, which involves both, a field automorphism $\sigma$ and a field derivation $\delta$. Unlike ordinary polynomials, there exist several ways to evaluate skew polynomials. In Lam (1985); Lam and Leroy (1988) general results regarding the so-called remainder evaluation of skew polynomials were defined. First results on the generalized operator evaluation were derived in Leroy et al. (1995). Depending on the choice of the automorphism $\sigma$ and the derivation $\delta$, skew polynomial rings include several polynomial rings as a special case, such as the ordinary polynomial ring as well as the linearized polynomial ring Ore (1933a, b). This property along with the different ways to evaluate skew polynomials make them a very versatile tool with many different applications.

One important application of skew polynomials is the construction of evaluation codes, that have distance properties in several decoding metrics, including the Hamming, rank, sum-rank, skew and other related metrics such as the (sum-)subspace metric Boucher and Ulmer (2014); Martínez-Peñas (2018); Martínez-Peñas and Kschischang (2019b); Caruso (2019).

In general, evaluation codes can be decoded via efficient interpolation-based decoding algorithms, like e.g. the Welch and Berlekamp (1986) and Sudan (1997) algorithms for decoding Reed–Solomon codes. In Kötter (1996) a bivariate interpolation algorithm for Sudan-like decoding of Reed–Solomon codes Kötter (1996) (over ordinary polynomial rings) was presented that since then is often referred to as the Kötter interpolation. The Kötter interpolation as it is known today was first stated by Nielsen and Høholdt in Nielsen and Høholdt (2000) as a generalization of Kötter’s algorithm Kötter (1996). To acknowledge the contribution by Nielsen and Høholdt we refer to the algorithm as Kötter–Nielsen–Høholdt (KNH) interpolation. A fast divide-and-conquer variant of the KNH interpolation for the Guruswami–Sudan algorithm for decoding Reed–Solomon codes was presented in Nielsen (2014).

A multivariate generalization of the KNH interpolation Wang et al. (2005) for free modules over ordinary polynomial rings was proposed in Wang et al. (2005). This approach was generalized to free modules over linearized polynomial rings by Xie et al. (2011). A further generalization to free modules over skew polynomial rings was proposed by Liu et al. (2014), which contains the variants over ordinary polynomial rings Wang et al. (2005) and linearized polynomial rings Xie et al. (2011) as special cases.

The evaluation and interpolation of multivariate skew polynomials was also considered in Martínez-Peñas and Kschischang (2019a); here with the main motivation to construct Reed-Muller-like codes (see also Geiselmann and Ulmer (2019); Martínez-Peñas (2020)).

In this paper, we propose a fast  divide-and-conquer (DaC) variant of the KNH interpolation over skew polynomial rings Liu et al. (2014), that uses ideas from Nielsen (2014). The main idea of the proposed algorithm (Algorithm 3) is, that the interpolation problem is divided into smaller sub-problems, that can be solved and merged efficiently. In particular, the update operations in each loop of the KNH interpolation are “recorded” and then applied to a degree-reduced basis in the merge step rather than to a non-reduced basis. This allows to restrict the degree of the polynomials during the interpolation procedure which in turn results in a lower computational complexity.

We state the interpolation problem and the fast skew KNH interpolation algorithm in a general way using linear functionals over skew polynomial rings with arbitrary automorphisms and derivations. The proposed framework can be used for interpolation-based decoding of skew evaluation codes such as (linearized) Reed–Solomon and Gabidulin codes in several decoding metrics by an appropriate choice of the automorphism/derivation and definition of the linear functionals. The correctness proofs are omitted due to space restrictions and will be provided in a future full version of the paper.

The considered interpolation problem can also be solved using the skew minimal approximant bases methods from Bartz et al. (2020). Compared to the proposed approach, the approach from Bartz et al. (2020) requires the quite involved theory of minimal approximant bases in skew polynomial rings, whereas the proposed approach uses ideas from the well-known KNH interpolation which is simpler and therefore easier to understand.

Let $\mathbb{F}_{q}$ be a finite field and denote by $\mathbb{F}_{q^{m}}$ the extension field of degree $m$. Let $\sigma:\mathbb{F}_{q^{m}}\mapsto\mathbb{F}_{q^{m}}$ be a field automorphism of $\mathbb{F}_{q^{m}}$ and let $\delta:\mathbb{F}_{q^{m}}\mapsto\mathbb{F}_{q^{m}}$ be a $\sigma$-derivation such that

Skew polynomials are non-commutative polynomials that were introduced by Ore Ore (1933b). The set of all polynomials of the form

together with the ordinary polynomial addition and the multiplication rule

forms the non-commutative ring of skew polynomials that is denoted by $\mathbb{F}_{q^{m}}[x;\sigma,\delta]$. The degree of a polynomial $f\in\mathbb{F}_{q^{m}}[x;\sigma,\delta]$ is defined as $\deg(f)\overset{\operatorname{def}}{=}\max_{i}\{i:f_{i}\neq 0\}$ for $f\neq 0$ and $-\infty$ else. Further, by $\mathbb{F}_{q^{m}}[x;\sigma,\delta]_{<n}$ we denote the set of skew polynomials from $\mathbb{F}_{q^{m}}[x;\sigma,\delta]$ of degree less than $n$.

The monic  least common left multiple (LCLM) of some polynomials $p_{0},p_{1},\dots,p_{n-1}\in\mathbb{F}_{q^{m}}[x;\sigma,\delta]$ is denoted by

The skew polynomial ring $\mathbb{F}_{q^{m}}[x;\sigma,\delta]$ is a left and right Euclidean domain. Efficient Euclidean-like algorithms for performing left/right skew polynomial division exist (see Caruso and Le Borgne (2017b, a); Puchinger and Wachter-Zeh (2018)). For two skew polynomials $f,g\in\mathbb{F}_{q^{m}}[x;\sigma,\delta]$, denote by $f\;\mathrm{mod}_{\mathrm{r}}\;g$ the remainder of the right division of $f$ by $g$.

Skew polynomial rings include several polynomial rings as special cases, like e.g. ordinary polynomial rings and linearized polynomial rings.

The generalized operator evaluation defined in Leroy et al. (1995) allows to $\mathbb{F}_{q}$-linearize the skew polynomial evaluation and therefore establishes the link between the skew polynomial ring and the linearized polynomial ring (cf.  Ore (1933a, b)).

In Nielsen (2014) a fast DaC variant of the Kötter interpolation over ordinary polynomial rings for the Guruswami–Sudan decoder was presented. We now use ideas from Nielsen (2014) to speed up the skew KNH interpolation from Liu et al. (2014). The main idea is to split up Problem 2 into smaller subproblems and to consider degree-reduced skew polynomial matrices rather than the full matrices as in Liu et al. (2014). In the following, we describe the general framework for the fast skew KNH interpolation algorithm w.r.t. to general vector evaluation maps based on e.g. the generalized operator evaluation and remainder evaluation.

The operations performed on the basis $\mathbf{B}$ in the inner loop of the $i$-th iteration of Algorithm 1 can be represented by the matrix

Note, that if $\Delta_{j}=0$ no update on the row $\mathbf{b}_{j}$ is performed since $\Delta_{j}/\Delta_{j^{*}}=0$.

To describe the following algorithms we introduce some notations. $\mathbf{M}_{[i,j]}\in\mathbb{F}_{q^{m}}[x;\sigma,\delta]^{s+1}$ denotes a polynomial vector that is dependent on the index set $\{i,i+1,\ldots,j-1,j\}$ with $j\geq i$ and $\mathbf{M}_{[i,i]}=\mathbf{M}_{i}$. The set $\mathcal{M}$ is globally available for all algorithms and is defined as

for an integer $n\in\mathbb{Z}_{+}$. For a set of evaluation maps $\mathcal{E}=\{\mathscr{E}_{0},\ldots,\mathscr{E}_{n-1}\}$ we use a similar notation to access a subset of $\mathcal{E}$ as $\mathcal{E}_{[i,j]}=\{\mathscr{E}_{i},\dots,\mathscr{E}_{j}\}$.

In order to describe a general framework for the fast skew KNH interpolation, we need the following assumption for the linear functionals.

Equipped with the routine SkewInterpolatePoint in Algorithm 2 to solve the basic step we can now state a DaC variant of the skew KNH interpolation from Liu et al. (2014), which is given in Algorithm 3.

An essential part in Algorithm 3 is the degree-reduction via the minimal skew polynomial vectors ${\mathbf{M}}_{[i,j]}$ from the globally available set $\mathcal{M}$ defined in (11). We now sketch a generic procedure to pre-compute the set $\mathcal{M}$ efficiently. We consider minimal polynomials which can be constructed by means of the LCLM of polynomial sequences, such as minimal skew polynomials with respect to the generalized operator and remainder evaluation (see (Caruso and Le Borgne, 2017a, Theorem 3.2.7)).

The DaC structure of the proposed procedure is illustrated in Figure 1 for an example of $\kappa=4$. The initial minimal polynomial vectors ${\mathbf{M}}_{0},{\mathbf{M}}_{1},\ldots,{\mathbf{M}}_{\kappa-1}$ from which all other minimal polynomials are computed via the LCLM, are computed w.r.t. to the generalized operator or remainder evaluation depending on the application.

Efficient methods for solving instances of Problem 2 are essential for several applications in coding theory and code-based quantum-resistant cryptography.

For $\delta=0$, instances of Problem 2 correspond to the complexity-dominating interpolation problem of interpolation-based decoding of (interleaved/folded) linearized Reed–Solomon codes in the sum-rank metric (see Martínez-Peñas (2018); Caruso (2019); Bartz and Puchinger (2022); Hörmann and Bartz (2022)). Compared to the original skew KNH interpolation by Liu et al. (2014), which requires at most $\mathcal{O}({s^{2}n^{2}})$ operations in $\mathbb{F}_{q^{m}}$, Algorithm 3 can solve the corresponding interpolation problem requiring only at most $\widetilde{O}\mathopen{}\left(s^{\omega}\mathfrak{M}(n)\right)\mathclose{}$ operations in $\mathbb{F}_{q^{m}}$, where $s\ll n$ is the interleaving order (or the decoding parameter for folded codes), $\omega$ the matrix multiplication exponent (currently $\omega<2.37286$), $n$ the length of the code and $\widetilde{O}\mathopen{}\left(\cdot\right)\mathclose{}$ the soft-$O$ notation which neglects log factors.

As (interleaved/folded) linearized Reed–Solomon codes include (interleaved/folded) Reed–Solomon codes (see Bleichenbacher et al. (2003); Guruswami and Rudra (2008)) in the Hamming metric and (interleaved/folded) Gabidulin codes (see Overbeck (2006); Mahdavifar and Vardy (2012)) in the rank metric as special cases, the interpolation steps in the respective interpolation-based decoders (see e.g. Guruswami and Rudra (2008); Wachter-Zeh and Zeh (2014); Mahdavifar and Vardy (2012)) can be sped-up by Algorithm 3 to at most $\widetilde{O}\mathopen{}\left(s^{\omega}\mathfrak{M}(n)\right)\mathclose{}$ operations in $\mathbb{F}_{q^{m}}$.

Similarly, the interpolation step in the interpolation-based decoder for ($s$-interleaved) skew Reed–Solomon codes in the skew metric can be solved using Algorithm 3 requiring at most $\widetilde{O}\mathopen{}\left(s^{\omega}\mathfrak{M}(n)\right)\mathclose{}$ operations in $\mathbb{F}_{q^{m}}$.

Apart from error correction in communication systems, variants of (linearized) Reed–Solomon and Gabidulin codes are used to design quantum-resistant code-based cryptosystems (see e.g. Melchor et al. (2018, 2017); Loidreau (2017); Renner et al. (2021); Puchinger et al. (2020)). In order to obtain a good encryption/decryption performance of the corresponding cryptosystems, fast decoding algorithms for the respective codes are required. As in general the interpolation step dominates the overall complexity of interpolation-based decoders, the proposed fast skew KNH interpolation algorithm is an important factor for developing high-performance code-based cryptosystems.

In order to prevent side-channel attacks that exploit correlations between the error patterns and the runtime of the interpolation algorithm, future work will consider constant-time variants of the proposed algorithm in the spirit of Bettaieb et al. (2019).

We presented a fast divide-and-conquer variant of the Kötter–Nielsen–Høholdt (KNH) interpolation over free modules over skew polynomial rings. The proposed algorithm divides the interpolation problem into smaller sub-problems, which can be solved and merged efficiently, and uses degree-restricted polynomials for the intermediate steps to reduce the computational complexity. The fast interpolation algorithm can be used to speed up existing interpolation-based decoders for variants of linearized and skew Reed–Solomon codes in the Hamming, (sum-)rank and skew metric.