Cryptanalysis of Ivanov–Krouk–Zyablov Cryptosystem

Abstract

Recently, F. Ivanov, E. Krouk and V. Zyablov proposed new cryptosystem based of Generalized Reed–Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message–recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret key of Ivanov–Krouk–Zyablov cryptosystem can successfully recovered in polynomial time with a linear–algebra based attack and a square–based attack.

1 Introduction

Due to the development of quantum computing and the vulnerability of traditional asymmetric cryptosystems to attacks using quantum computers, there is a need to create new secure cryptosystems. Code–based cryptography is considered as one of the most promising and mature candidates for post–quantum cryptography. The first code–based cryptosystem based on binary Goppa codes was proposed by R. J. McEliece in 1978 [19] and in its modern version ClassicMcEliece [7] submitted to NIST–PQC competition is still believed to be secure. However due to large public key sizes, the McEliece cryptosystem is limited in some practical applications. In order to get smaller key sizes, there were attempts to replace binary Goppa codes by other classes of efficient algebraic codes, such as Generalized Reed–Solomon (GRS) codes [22], Reed–Muller codes [26], AG–codes [16], concatenated codes [25], rank–metric Gabidulin codes [13]. However, most of this modifications were proven unsecure [8, 11, 21, 24, 25, 27]. With general McEliece framework being masking a fast–decodable code by using a hiding permutation, there were also attempts to employ more sophisticated hiding mechanisms (e.g. [3, 6, 26, 28, 29]). However most of this modifications were also successfully attacked [10, 12, 29]. Another approach to reduce public key size is using random group–structured codes, which was successfully implemented in BIKE [1, 2] and HQC [20] cryptosystems, however this introduces some decryption failure rate (DFR) making it harder to prove CCA security.

Recently, several protocols based on subfield images of algebraic codes over field extensions were proposed. Namely, in [5] T. Berger, C. Gueye, J. Klamti introduced the notion of generalized subspace (GS) subcodes, which are intermediate level between subfield subcodes and subfield images of codes over field extensions $\mathbb {F}_{q^m}$, and proposed using such codes in cryptography. In addition, it was shown in [5] that a McEliece–like cryptosystem based on subfield images of GRS codes can be attacked by a modification of the Sidelnikov–Shestakov attack, and quasi–cyclic variant of this cryptosystem can be attacked by using approach of [23]. In [17], K. Khathuria, J. Rosenthal and V. Weger proposed using the punctured subfield images of GRS codes in the Niederreiter–like cryptosystem (XGRS cryptosystem). However, in [9], a cryptosystem based on generalized subspace subcodes of GRS codes (SSRS cryptosystem), which generalizes XGRS cryptosystem, was successfully attacked using a modification of Schur–Hadamard product in the case $\lambda > m/2$, where $\lambda$ is dimension of subspaces. More recently, F. Ivanov, E. Krouk and V. Zyablov proposed a new protocol [15] based on subfield images of GRS–codes, with the public code being neither subfield image of GRS–code naither its subcode. However, in this paper we show that Ivanov–Krouk–Zyablov (IKZ) cryptosystem is also insecure.

This paper is organized is follows. In Sect. 2 we give necessary preliminaries on m–block codes, subfield images of codes, generalized subspace subcodes and generalized projected codes. In Sect. 3, we consider a generalization of Ivanov–Krouk–Zyablov protocol and estimate the complexity of information–set decoding attack on it. In Sect. 4, we propose a key–recovery attack based on linear algebra. In Sect. 5, we propose a faster attack based on twisted squares attack of [9] which however requires larger degree field extensions.

2 Preliminaries

Let $\mathbb {F}_q$ be a finite field of size q. Given a vector $\textbf{c} \in \mathbb {F}_q^n$, by ${\text {supp}}(c) = \{ i = 1, \dots , n \mid c_i \ne 0 \}$ we denote the support of $\textbf{c}$ and by ${\text {wt}}(\textbf{c}) = |{\text {supp}}(\textbf{c})|$ we denote the Hamming weight of $\textbf{c}$. The Hamming distance between $\textbf{x},\textbf{y} \in \mathbb {F}^n$ is denoted by $d(\textbf{x},\textbf{y}) = {\text {wt}}(\textbf{x}-\textbf{y})$. A linear $[n,k,d]_q$–code is a linear subspace $C \subset \mathbb {F}_q^n$, such that $\dim (C) = k$ and $d = \min _{c \in C \setminus \{0\}} {\text {wt}}(c)$. $G_C$ denotes a generator matrix of C and $H_C$ denotes a parity–check matrix of C. Given a code C, its dual code is denoted by $C^{\perp }$. By $I_n$ we denote $n \times n$–identity matrix.

Shortened and punctured codes are well–known constructions for building new codes from existing ones. Let $\overline{1, n} = \{ 1, \dots , n\}$ and let $I \subset \overline{1,n}$. Given a $[n,k,d]_q$–code C, the punctured code of C on positions I is defined as follows

$$\begin{aligned} {\text {Pct}}_I(C) = \left\{ \left( c_i \right) _{i \notin I} \mid (c_1, c_2, \dots , c_n) \in C \right\} , \end{aligned}$$

(1)

i.e. ${\text {Pct}}_I(C)$ is obtained from C by deleting coordinates indexed by I. The shortened code of C on I is

$$\begin{aligned} {\text {Sh}}_I(C) = {\text {Pct}}_{I}\left( \left\{ c \in C \mid {\text {supp}}(c) \cap I = \varnothing \right\} \right) . \end{aligned}$$

(2)

Note that ${\text {Pct}}_I(C)$ and ${\text {Sh}}_I(C)$ are also linear codes and the following relations hold.

Proposition 1

([14], Theorem 1.5.7). Let C be a $[n,k,d]_q$–code. Then

• 1. ${\text {Pct}}_I(C)^{\perp } = {\text {Sh}}_I(C^{\perp })$ and ${\text {Sh}}_I(C)^{\perp } = {\text {Pct}}_I(C^{\perp })$;

• 2. if $|I| < d$, then $\dim \left( {\text {Pct}}_I(C) \right) = k$ and $\dim \left( {\text {Sh}}(C^{\perp }) \right) = n-k-|I|$; if $|I|=d$ and I is the set of coordinates where a minimum weight codeword is nonzero, then

  $$\begin{aligned} \dim ({\text {Pct}}_I(C)) = k-1, \quad \dim ({\text {Sh}}_I(C^{\perp })) = n-k-|I|+1. \end{aligned}$$

2.1 m–block Codes

In [4, 5] T. Berger et. al. proposed the notion of m–block codes for which the ambient alphabet is the set of m–tuples of elements of $\mathbb {F}_q$. Namely, a m–block code of length n is an additive code over the alphabet $\mathbb {E}_m = \mathbb {F}_q^m$ (i.e. a subgroup of $(\mathbb {E}_m^n, +)$), which is stable by scalar multiplication by any $\lambda \in \mathbb {F}_q$. The integer m is called the block size. Given $\textbf{c} = (\mathbf {c_1}, \dots , \mathbf {c_n}) \in \mathbb {E}_m^n \simeq \mathbb {F}_q^{mn}$, by ${\text {supp}}_m(\textbf{c}) = \{ i \mid \mathbf {c_i} \ne 0 \}$ we denote block support of c, by ${\text {wt}}_m(\textbf{c}) = |{\text {supp}}_m(\textbf{c})|$ and $d_m(\textbf{x},\textbf{y}) = {\text {wt}}_m(\textbf{x}-\textbf{y})$ we denote block Hamming weight and block Hamming distance respectively. Since $\mathbb {E}_m^n$ and $\mathbb {F}_q^{nm}$ can be identified, it follows that a m–block code is also a linear code over $\mathbb {F}_q$ of length mn, equipped with block Hamming metric. A m–block code C of block length n, $\mathbb {F}_q$–dimension k and minimum block distance $d_m = \min _{c \in C \setminus \{0 \}} {\text {wt}}_m(c) \}$ is said to be $[n,k,d_m]_q^m$–block code.

Block codes are of particular interest due to having ability to correct error bursts. Indeed, let $\mathcal {S}_{m,n,t} = \{ e \in \mathbb {E}_m^n \mid {\text {wt}}_m(e) \le t \}$ be a set of synchronous t error burst of length m, then clearly a $[n,k,d_m]_q^m$–code can correct any error from $\mathcal {S}_{m,n,\lfloor (d_m-1)/2 \rfloor }$.

Remark 1

Let $\mathcal {E}_{mn,l} \subset \mathbb {F}_q^{nm}$ denote a set of l error bursts of length up to m (non–synchronous to m–block structure of a code). Note that if an m–block code can correct any error from $\mathcal {S}_{m,n,t}$, then it can correct any error from $\mathcal {E}_{mn,\lfloor t/2 \rfloor }$ since any non–synchronous error burst of length m covers at most two m–blocks.

Note that the notion of block codes can be easily generalized to multi-block codes. Namely, a multi–block code is an additive subgroup of $\mathbb {E}_{m_1} \times \dots \times \mathbb {E}_{m_n}$, which is stable by scalar multiplication by any $\lambda \in \mathbb {F}_q$.

Two multi–block codes $C_1$ and $C_2$ of length are said to be multiplier equivalent if there exist $\varLambda _1, \dots , \varLambda _n \in {\text {GL}}_{m_i}(\mathbb {F}_q)$ such that

$$ C_2 = \left\{ \textbf{c}\cdot \varLambda \mid \textbf{c}\in C_1 \right\} , \quad \varLambda = {\text {diag}}(\varLambda _1, \dots , \varLambda _n). $$

Proposition 2

Let $C_2 = \left\{ \textbf{c}\cdot \varLambda \mid c \in C_1 \right\}$. Then $C_2^{\perp } = \{ \textbf{h} \cdot \left( \varLambda ^{-1}\right) ^\textsf{T}\mid \textbf{h} \in C_1^{\perp } \}.$

Proof

Let $G_{C_1}$ be a generator matrix of $C_1$ and $H_{C_1}$ be a parity check matrix of $C_1$. Since $G_{C_1} \cdot \varLambda$ is a generator matrix of $C_2$ and

$$\begin{aligned} (G_{C_1} \cdot \varLambda ) \cdot (\varLambda ^{-1} \cdot H_{C_1}^{\textsf{T}}) = 0, \end{aligned}$$

it follows that $H_{C_1} \cdot \left( \varLambda ^{-1}\right) ^\textsf{T}$ is a parity–check matrix of $C_2$.

Let $V_1, \dots , V_n$ be a tuple of $\mathbb {F}_q$–linear subspaces of $\mathbb {E}_{m_1}, \dots , \mathbb {E}_{m_n}$ of $\mathbb {F}_q$–dimensions $\mu _i \le m_i$, $i=1,\dots ,n$. The generalized subspace subcode of a multi–block code C relative to $V_1, \dots , V_n$ is defined as

$$ C_{\mid V_1, \dots , V_n} = C \cap \left( V_1 \oplus \dots \oplus V_n \right) . $$

One can easily notice that this codes allow short representation. Let $T_1, \dots , T_n \in \mathbb {F}_{q}^{\mu _i \times m_i}$ be generator matrices of $V_1, \dots , V_n$ viewed as $[m_i, \mu _i]_q$–linear codes. Define the maps

$$\begin{aligned} \psi _i: V_i \rightarrow \mathbb {E}_{\mu _i} = \mathbb {F}_{q}^{\mu _i}, \quad v \mapsto m, \; \text {s.t. }v = m T_i. \end{aligned}$$

Then the short representation of $C_{\mid V_1, \dots , V_n}$ relative to $T_1, \dots , T_n$ is

$$ {\text {GSS}}(C; T_1, \dots , T_n) = \left\{ \left( \psi _1(\mathbf {c_1}), \dots , \psi _n(\mathbf {c_n}) \right) \mid \left( \mathbf {c_1}, \dots , \mathbf {c_n} \right) \in C_{\mid V_1, \dots , V_n}, \; \mathbf {c_i} \in \mathbb {E}_{m_i} \right\} . $$

Remark 2

We clearly have

$$\begin{aligned} C_{\mid V_1,\dots ,V_n} = \left\{ c \cdot {\text {diag}}(T_1, \dots , T_n) \mid c \in {\text {GSS}}(C; T_1, \dots , T_n) \right\} . \end{aligned}$$

Let $P_1, \dots , P_n \in \mathbb {F}_q^{m_i \times \mu _i}$ be full-rank matrices, which define projection maps $x \mapsto xP_i$. Given a multi–block code C, the generalized projected code relative to $P_1, \dots , P_n$ is defined as follows

$$ {\text {GPC}}(C; P_1, \dots , P_n) = \{ \left( \mathbf {c_1} P_1, \dots , \mathbf {c_n} P_n \right) \mid \left( \mathbf {c_1}, \dots , \mathbf {c_n} \right) \in C, \; \mathbf {c_i} \in \mathbb {E}_{m_i} \}. $$

Proposition 3

Let C be a multi–block code, $1 \le \mu _i \le m_i$, and let $T_1, \dots , T_n \in \mathbb {F}_{q}^{\mu _i \times m_i}$ be full-rank matrices. Then

$$ {\text {GSS}}(C; T_1, \dots , T_n)^{\perp } = {\text {GPC}}(C^{\perp }; T_1^{\textsf{T}}, \dots , T_n^{\textsf{T}}). $$

Proof

Let $\widetilde{T_i} \in \mathbb {F}_{q}^{m_i \times m_i}$ be a non–singular matrix derived from $T_i$ by adding $m_i - \mu _i$ linearly independent rows. Let

$$ \widetilde{C} = \left\{ c \cdot {\text {diag}}\left( \widetilde{T_1}^{-1}, \dots , \widetilde{T_n}^{-1} \right) \; \big \vert \; c \in C \right\} . $$

Since ${\text {GSS}}(C; T_1, \dots , T_n)$ is shortened subcode of $\widetilde{C}$ on last $m_i - \mu _i$ positions of each $m_i$–block, using Proposition 1 we obtain that ${\text {GSS}}(C; T_1, \dots , T_n)^{\perp }$ is punctured code of

$$ \widetilde{C}^{\perp } = \left\{ h \cdot {\text {diag}}\left( \widetilde{T_1}^\textsf{T}, \dots , \widetilde{T_n}^{\textsf{T}} \right) \; \big \vert \; h \in C^{\perp } \right\} $$

(see Proposition 2) on the same positions, which is ${\text {GPC}}(C^{\perp }; T_1^{\textsf{T}}, \dots , T_n^{\textsf{T}})$.

For more details on m–block codes, generalized subspace and generalized projected codes we refer to [4, 5, 9].

2.2 Subfield Images of Codes

A possible way to construct m–block codes with known parameters is to consider subfield images of codes over some extension field $\mathbb {F}_{q^m}$. Let $\mathcal {B}= \{ b_1, \dots , b_m \}$ be a $\mathbb {F}_q$–basis of $\mathbb {F}_{q^m}$, by $\phi _{\mathcal {B}}$ we denote $\mathbb {F}_q$–linear isomorphism between $\mathbb {F}_{q^m}$ and $\mathbb {E}_m= \mathbb {F}_q^m$, i.e.

$$\begin{aligned} \phi _{\mathcal {B}} \left( \sum _{i=1}^m t_i b_i \right) = (t_1, \dots , t_m). \end{aligned}$$

Let

$$ \varPhi _{\mathcal {B}}: \mathbb {F}_{q^m}^n \rightarrow \mathbb {E}_m^n, \quad (c_1, \dots , c_n) \mapsto \left( \phi _{\mathcal {B}}(c_1), \dots , \phi _{\mathcal {B}}(c_n) \right) $$

be an extension of $\phi _{\mathcal {B}}$ to $\mathbb {F}_{q^m}^n$. The subfield image of a $[n, k, d]_{q^m}$ code $C \subset \mathbb {F}_{q^m}^n$ relative to the basis $\mathcal {B}$ is defined as $\varPhi _{\mathcal {B}}(C) = \{ \varPhi _{\mathcal {B}}(c) \mid c \in C \}$. Clearly, $\varPhi _{\mathcal {B}}(C)$ is $[n, k, d]_{q}^m$ block code and if ${\text {Dec}}_C: \mathbb {F}_{q^m}^n \rightarrow C$ is a decoder of C, then $\varPhi _{\mathcal {B}} \circ {\text {Dec}}_C \circ \varPhi _{\mathcal {B}}^{-1}$ is a decoder of $\varPhi _{\mathcal {B}}(C)$.

Remark 3

Let $\mathbb {F}_{q^m} = \mathbb {F}_{q}[\gamma ]$, where $\gamma$ is a root of a primitive polynomial. Note that the usual choice of a basis of $\mathbb {F}_{q^m}$ is $\varGamma = \{ \gamma ^0, \dots , \gamma ^{m-1} \}$.

Proposition 4

(Proposition 3 of [5]). Suppose $\mathcal {B}'$ is another basis of $\mathbb {F}_{q^m}$ and M is basis change matrix, i.e. $\phi _{\mathcal {B}'}(x) = \phi _{\mathcal {B}}(x)M$ for any $x \in \mathbb {F}_{q^m}$, then $\varPhi _{\mathcal {B}}(C)$ and $\varPhi _{\mathcal {B}'}(C)$ are multiplier equivalent with $\varLambda _1 = \dots = \varLambda _n = M$, i.e.

$$\begin{aligned} \varPhi _{\mathcal {B}'}(C) = \{ (\mathbf {c_1} M, \dots , \mathbf {c_n} M) \mid (\mathbf {c_1}, \dots , \mathbf {c_n}) \in \varPhi _{\mathcal {B}}(C) \} \end{aligned}$$

Remark 4

Note that $\varPhi _{\mathcal {B}}(C) = \varPhi _{\lambda \mathcal {B}}(C)$ for any nonzero $\lambda \in \mathbb {F}_{q^m}$.

Given $\xi \in \mathbb {F}_{q^m}$, by $\textbf{M}_{\mathcal {B}}(\xi )$ we denote the matrix of transformation $x \mapsto \xi x$ written in basis $\mathcal {B}$, i.e.

$$ \textbf{M}_{\mathcal {B}}(\xi ) = \begin{pmatrix} \phi _{\mathcal {B}}(b_1 \xi ) \\ \vdots \\ \phi _{\mathcal {B}}(b_m \xi ) \end{pmatrix}. $$

Note that for any $\lambda , \xi \in \mathbb {F}_{q^m}$, $\xi \ne 0$, the following equality holds

$$ \phi _{\mathcal {B}}(\xi \lambda ) = \phi _{\mathcal {B}}(\lambda ) \cdot \textbf{M}_{\mathcal {B}}(\xi ) = \phi _{\xi ^{-1} \mathcal {B}}(\lambda ). $$

Proposition 5

(Proposition 4 of [5]). If $G_{C} = (g_{i,j}) \in \mathbb {F}_{q^m}^{k \times n}$ is a generator matrix of C, then

is a generator matrix of $\varPhi _{\mathcal {B}}(C)$.

Given a basis $\mathcal {B}$ of $\mathbb {F}_{q^m}$, the dual basis $\mathcal {B}^{*}$ is the unique basis of $\mathbb {F}_{q^m}$, such that $\textbf{M}_{\mathcal {B}^*}(\xi ) = \left( \textbf{M}_{\mathcal {B}}(\xi )\right) ^{\textsf{T}}$ for any $\xi \in \mathbb {F}_{q^m}$.

Proposition 6

(Proposition 5 of [5]). Let $C \subset \mathbb {F}_{q^m}$ be a $[n,k]_{q^m}$–code with a parity–check matrix $H_C$, then

$$ \left( \varPhi _{\mathcal {B}}(C) \right) ^{\perp } = \varPhi _{\mathcal {B}^*}(C^{\perp }). $$

and the parity–check matrix of $\varPhi _{\mathcal {B}}(C)$ is

$$ {\text {Exp}}^{*}_{\mathcal {B}}(H_C) = {\text {Exp}}_{\mathcal {B}^*}(H_C) = \begin{pmatrix} \textbf{M}_{\mathcal {B}}(h_{1,1})^\textsf{T}&{} \dots &{} \textbf{M}_{\mathcal {B}}(h_{1,n})^\textsf{T}\\ \vdots &{} \ddots &{} \vdots \\ \textbf{M}_{\mathcal {B}}(h_{n-k,1})^\textsf{T}&{} \dots &{} \textbf{M}_{\mathcal {B}}(h_{n-k,n})^\textsf{T}\end{pmatrix}. $$

Corollary 1

Let $C \subset \mathbb {F}_{q^m}$ be a $[n,k]_{q^m}$–code. Then Proposition 3 and Proposition 6 imply

$$ {\text {GSS}}(\varPhi _{\mathcal {B}}(C); T_1, \dots , T_n)^{\perp } = {\text {GPC}}(\varPhi _{\mathcal {B}^*}(C^{\perp }); T_1^{\textsf{T}}, \dots , T_n^{\textsf{T}}). $$

2.3 Generalized Reed–Solomon Codes

Let $\textbf{x}= (x_1, \dots , x_n) \in \mathbb {F}_q^n$ be a vector of distinct non–zero values and let $\textbf{y} = (y_1, \dots , y_n) \in \mathbb {F}_q^n$ be a vector, such that $y_i \ne 0$ for all i. The generalized Reed–Solomon code with support $\textbf{x}$ and multiplier $\textbf{y}$ of length n and dimension k is

$$\begin{aligned} {\text {GRS}}_{k}(\textbf{x},\textbf{y}) = \left\{ (y_1 f(x_1),\dots , y_n f(x_n)) \mid f \in \mathbb {F}_q[x], \; \deg (f) \le k-1 \right\} . \end{aligned}$$

When $\textbf{y} = (1,1, \dots , 1)$, the code is said to be a Reed–Solomon code and denoted as ${\text {RS}}_k(\textbf{x})$. As is well–known, ${\text {GRS}}_{k}(\textbf{x}, \textbf{y})$ is a $[n,k,n-k+1]_q$–code, the generator matrix of ${\text {GRS}}_{k}(\textbf{x}, \textbf{y})$ is

$$ G_k(\textbf{x}, \textbf{y}) = \begin{pmatrix} x_1^0&{}\cdots &{}x_n^0\\ x_1^1&{}\cdots &{}x_n^1\\ \vdots &{}\ddots &{}\vdots \\ x_1^{k-1}&{}\cdots &{}x_n^{k-1} \end{pmatrix} {\text {diag}}(y_1,...,y_n), $$

the generator matrix of ${\text {RS}}_k(\textbf{x})$ is $G_k(\textbf{x}) = G_k(\textbf{x}, \textbf{1})$, the dual of ${\text {GRS}}_{k}(\textbf{x},\textbf{y})$ is ${\text {GRS}}_{n-k}(\textbf{x},\textbf{z})$, where

$$\begin{aligned} z_i^{-1} = y_i \prod _{\begin{array}{c} i,j \in \overline{1,n} \\ j \ne i \end{array}} (x_i-x_j). \end{aligned}$$

(3)

Note that for a given GRS code multiplier and support are not unique. We refer [18, Chapter 12] and [14, §5.3] for more details on GRS codes.

Remark 5

Any subfield image of ${\text {GRS}}_k(\textbf{x}, \textbf{y})$ is multiplier equivalent to a subfield image of ${\text {RS}}_k(\textbf{x})$. Indeed,

$$ \varPhi _{\mathcal {B}}({\text {GRS}}_k(\textbf{x}, \textbf{y})) = \left\{ \left( \phi _{\mathcal {B}}(c_i) \cdot \textbf{M}_{\mathcal {B}}(y_i) \right) _{i=1,\dots ,n} \mid (c_1, \dots , c_n) \in {\text {RS}}_k(\textbf{x}) \right\} . $$

3 Ivanov–Krouk–Zyablov Cryptosystem

In [15] F. Ivanov, E. Krouk and V. Zyablov proposed a new cryptosystem based on subfield images of generalized Reed–Solomon codes, with its key feature being that public code is not equivalent to a subfield image. In this section, we give a generalized version of it, consider some of its properties, and estimate the complexity of a key–recovery attack.

3.1 Protocol Description

• Key generation. Let $C = {\text {RS}}_k(\textbf{x})$ be a random $[n,k]_{q^m}$ RS–code of even length with support $\textbf{x}= (x_1, \dots , x_n)$. Choose a random non–singular matrix $S \in {\text {GL}}_{km}(\mathbb {F}_q)$, and random non–singular matrices $Y_j \in {\text {GL}}_m(\mathbb {F}_q)$, $M_j \in {\text {GL}}_{m_j}(\mathbb {F}_q)$, $j=1,\dots ,n$, where

  $$ m_{j} = {\left\{ \begin{array}{ll} m - 1, &{} j\text { is odd} \\ m + 1, &{} j\text { is even} \end{array}\right. }. $$

  The public key is $G_{pub} = S \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x})) \cdot \overline{Y} \cdot \overline{M}$, where

  $$ \overline{Y} = {\text {diag}}(Y_1, \dots , Y_n), \quad \overline{M} = {\text {diag}}(M_1, \dots , M_n) $$

  and secret key is $(\textbf{x}, S, Q = \overline{Y} \cdot \overline{M})$.

• Encryption. Let $t = {(n-k)}/{2}$ be a number of errors that can be corrected by C. Let $m \in \mathbb {F}_{q}^{km}$ be a plain text, then the ciphertext is

  $$\begin{aligned} z = m G_{pub} + e, \quad e \in \mathcal {E}_{mn, t/3}. \end{aligned}$$

• Decryption. Let ${\text {Dec}}_C: \mathbb {F}_{q^m} \rightarrow C$ be a decoder of C. Then $mG_{pub}$ can be found as follows

  $$ mG_{pub} = \varPhi _{\mathcal {B}} \circ {\text {Dec}}_C \circ \varPhi _{\mathcal {B}}^{-1} \left( z \cdot Q^{-1} \right) . $$

Remark 6

Note that $eQ^{-1} \in \mathcal {S}_{m,n,t}$. Indeed, let j be a starting position of an error burst of length m. Two cases are possible:

• 1) $(2s - 1)m + 1 \le j \le 2sm$ for some s. It follows that after multiplying by $Q^{-1}$ only two m–blocks get corrupted.

• 2) $2sm + 1 \le j \le (2s + 1)m$ for some s. It follows that after multiplying by $Q^{-1}$ three m–blocks can get corrupted. Namely, 2s, $2s+1$, $2s+2$–th blocks.

Note that in [15] case 2) hasn’t been considered and due to this it was erroneously proposed to sample e from $\mathcal {E}_{mn,t/2}$.

Remark 7

The use of GRS–codes in this protocol is equivalent to the use of RS–codes due to the presence of $\overline{Y}$ (see Remark 5).

Remark 8

Without loss of generality, one can assume that $Y_{2i} = I_{m}$ and $M_{2i-1} = I_{m-1}$. Indeed,

$$\begin{aligned} {\text {diag}}(Y_{2i-1}, Y_{2i}) {\text {diag}}(M_{2i-1}, M_{2i})&= {\text {diag}}\left( Y_{2i-1} \begin{pmatrix} M_{2i-1} &{} \\ {} &{} 1 \end{pmatrix}, I_m \right) \\ \cdot&{\text {diag}}\left( I_{m-1}, \begin{pmatrix} 1 &{} \\ {} &{} Y_{2i} \end{pmatrix} M_{2i} \right) \end{aligned}$$

Proposition 7

Let $G_{pub} = S \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x}, \textbf{y})) \cdot Q$ be a public key of IKZ–cryptosystem based on ${\text {GRS}}_{k}(\textbf{x}, \textbf{y})$–code. Then any parity–check matrix of $C_{pub}^{\perp }$ is of the form

$$ H = S' \cdot {\text {Exp}}_{\varGamma *}(G_{n-k}(\textbf{x}, \textbf{z})) \cdot {Q^{-1}}^{\textsf{T}}, \quad z_i^{-1} = y_i \prod _{\begin{array}{c} i,j \in \overline{1,n} \\ j \ne i \end{array}} (x_i - x_j). $$

In addition, since

$$ {Q^{-1}}^{\textsf{T}} = {\text {diag}}({Y_1^{-1}}^{\textsf{T}}, \dots , {Y_n^{-1}}^{\textsf{T}}) \cdot {\text {diag}}({M_1^{-1}}^{\textsf{T}}, \dots , {M_n^{-1}}^{\textsf{T}}), $$

it follows that H is a public key of IKZ cryptosystem based on ${\text {GRS}}_{n-k}(\textbf{x}, \textbf{z})$–code.

Proof

Using Proposition 6 and (3), we obtain

$$ G_{pub} H^{\textsf{T}} = S \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x}, \textbf{y})) \cdot Q \cdot Q^{-1} \cdot {\text {Exp}}_{\varGamma ^{*}}(G_{n-k}(\textbf{x}, \textbf{z}))^{\textsf{T}} \cdot S'^{\textsf{T}} = 0. $$

Fig. 1.

non–synchronous error burst of length 2 corrupts 4 blocks

3.2 Message–Recovery Attack

Since the error $\textbf{e}$ is structured, it is possible to exploit it for reducing complexity of information–set decoding attack. Indeed, we can consider $C_{pub} = {\text {Span}}_{\mathbb {F}_q}(G_{pub})$ as a m–block code, then any error from $\mathcal {E}_{mn,t/3}$ covers at most 2t/3 m–blocks (see Fig. 1). It follows that remaining $n-2t/3$ blocks are error–free and the probability of finding error–free information set of k blocks is

$$\begin{aligned} {\text {Prob}}_{\textrm{ISD}} = \frac{ \left( {\begin{array}{c}n-2t/3\\ k\end{array}}\right) }{ \left( {\begin{array}{c}n\\ k\end{array}}\right) }, \end{aligned}$$

which does not depend on m. Therefore, the workfactor of Ivanov–Krouk–Zyablov cryptosystem is significantly lower than estimates of [15]. We also note that due to using structured errors a significant reduction in complexity of ISD–attacks also extends to several more IKZ–like cryptosystems recently proposed in [30].

So, due to simple message–recovery attack, Ivanov–Krouk–Zyablov cryptosystem [15] can only be considered as a way to avoid key–recovery attacks since it produces a public code which is not multiplier equivalent to a subfield image of a GRS–code. However, below we show that such application of Ivanov–Krouk–Zyablov protocol is also insecure.

4 Direct Key–Recovery Attack

In this section, we propose a key–recovery attack which is based on the uniqueness of systematic generator matrix of $C_{pub}$ and distinguishability of matrices $\textbf{M}_{\varGamma }(a)$, $a \in \mathbb {F}_{q^m}$, from random ones.

4.1 Case of Even k

Define $Q_{i} \in \mathbb {F}_{q}^{2m \times 2m}$ as

$$ Q_{i} = {\text {diag}}(Y_{2i-1}, Y_{2i}) \cdot {\text {diag}}(M_{2i-1}, M_{2i}), $$

so $Q = {\text {diag}}(Q_1, \dots , Q_{n/2})$. Let $G^{sys}_C = \left[ I_k \mid L \right] = (l_{i,j}) \in \mathbb {F}_{q^m}^{k \times n}$ be the systematic generator matrix of C. One can easily notice that

$$ \left( \begin{array}{ccc|ccc} Q_1 &{} &{} &{} K_{1,k/2 + 1} Q_{k/2 + 1} &{} \dots &{} K_{1,(n-k)/2} Q_{n/2} \\ &{} \ddots &{} &{} \vdots &{} \ddots &{} \vdots \\ &{} &{} Q_{k/2} &{} K_{k/2,k/2+1} Q_{k/2 + 1} &{} \dots &{} K_{k/2,(n-k)/2} Q_{n/2} \end{array} \right) , $$

where

$$ K_{i,j} = \begin{pmatrix} \textbf{M}_{\varGamma }\left( l_{2i-1, 2j-1} \right) &{} \textbf{M}_{\varGamma }\left( l_{2i-1, 2j} \right) \\ \textbf{M}_{\varGamma }\left( l_{2i, 2j-1} \right) &{} \textbf{M}_{\varGamma }\left( l_{2i, 2j} \right) \end{pmatrix}, $$

is a generator matrix of $C_{pub}$. It follows that the unique systematic generator matrix $G_{pub}^{sys}$ of $C_{pub}$ is of the form

$$\begin{aligned} \left( \begin{array}{ccc|ccc} I_{2m} &{} &{} &{} Q_1^{-1} K_{1,k/2 + 1} Q_{k/2 + 1} &{} \dots &{} Q_1^{-1} K_{1,(n-k)/2} Q_{n/2} \\ &{} \ddots &{} &{} \vdots &{} \ddots &{} \vdots \\ &{} &{} I_{2m} &{} Q_{k/2}^{-1} K_{k/2,k/2+1} Q_{k/2 + 1} &{} \dots &{} Q_{k/2}^{-1} K_{k/2,(n-k)/2} Q_{n/2} \end{array} \right) . \end{aligned}$$

(4)

Let us denote $Q_i^{-1} K_{i,j} Q_{j}$ by $K_{i,j}'$. For $1 \le i,r \le k/2$ and $k/2 + 1 \le j,s \le n/2$ define

$$\begin{aligned} V_{i, j, r, s} = K'_{i,j} {(K'_{r,j})}^{-1} K'_{r,s} {(K'_{i,s})}^{-1} = Q_i^{-1} \left( K_{i,j} K_{r,j}^{-1} K_{r,s} K_{i,s}^{-1} \right) Q_i, \end{aligned}$$

(5)

$$\begin{aligned} W_{i,j,r,s} = {(K'_{i,j})}^{-1} K'_{i,s} {(K'_{r,s})}^{-1} K'_{r,j} = Q_j^{-1} \left( K_{i,j}^{-1} K_{i,s} K_{r,s}^{-1} K_{r,j} \right) Q_j \end{aligned}$$

(6)

if corresponding inverse matrices exist (which is true in most cases). Since matrices $K_{i,j}$ have very special structure, namely, $K_{i,j}$ belong to the $\mathbb {F}_{q}$–algebra

$$ \varDelta = \left\{ \begin{pmatrix} \textbf{M}_{\varGamma }\left( a \right) &{} \textbf{M}_{\varGamma }\left( b \right) \\ \textbf{M}_{\varGamma }\left( c \right) &{} \textbf{M}_{\varGamma }\left( d \right) \end{pmatrix} \; \Big \vert \; a,b,c,d \in \mathbb {F}_{q^m} \right\} , $$

we can exploit it to recover the matrix Q up to certain equivalences.

Proposition 8

Let a $\mathbb {F}_{q^m}$–code $C'$ be semi–linear equivalent over $\mathbb {F}_q$ to C, i.e.

$$ C' = \{ \left( \theta (\alpha _1 c_1), \theta (\alpha _2 c_2), \dots , \theta (\alpha _n c_n) \right) \mid (c_1, \dots , c_n) \in C \} $$

(see [14]), where $\alpha _i \in \mathbb {F}_{q^m} \setminus \{ 0 \}$, and $\theta \in \textsf{Gal}(\mathbb {F}_{q^m}/\mathbb {F}_q)$ is an automorphism of $\mathbb {F}_{q^m}$ that fixes $\mathbb {F}_q$ pointwise. Let $A_{\theta }$ be a matrix representation of $\theta$ written in the basis $\varGamma = \{ \gamma ^0, \dots , \gamma ^{m-1} \}$ of $\mathbb {F}_{q^m} = \mathbb {F}_q[\gamma ]$, i.e.

Then the matrix ${\text {Exp}}_{\varGamma }(G_{C'}) \cdot {\text {diag}}(Q'_1, \dots , Q'_{n/2})$, where

$$\begin{aligned} Q'_{i+1} = {\text {diag}}\left( A_{\theta }^{-1} \cdot \textbf{M}_{\varGamma }(\alpha _{2i+1}^{-1}), A_{\theta }^{-1} \cdot \textbf{M}_{\varGamma }(\alpha _{2i+2}^{-1}) \right) \cdot Q_{i+1}, \end{aligned}$$

(7)

also spans $C_{pub}$.

Conjecture 1

Let $X, Y \in \textsf{QMat}$, where

$$ \textsf{QMat} = \left\{ {\text {diag}}(Y, I_m) \cdot {\text {diag}}(I_{m-1}, M) \mid Y \in {\text {GL}}_m(\mathbb {F}_q), M \in {\text {GL}}_{m+1}(\mathbb {F}_q) \right\} . $$

Let $\varXi$ be a sufficiently large subset of $\varDelta$ and $\zeta \in \varDelta$ be non–zero. Then

• 1. if $\left\{ Y X^{-1} \cdot \xi \cdot X Y^{-1} \mid \xi \in \varXi \right\} \subset \varDelta$, then there exist $a,b \in \mathbb {F}_{q^m}^*$ and $\theta \in \textsf{Gal}(\mathbb {F}_{q^m}/\mathbb {F}_{q})$, such that

  $$ Y = {\text {diag}}(A_{\theta }^{-1} \cdot \textbf{M}_{\varGamma }(a), A_{\theta }^{-1} \cdot \textbf{M}_{\varGamma }(b)) \cdot X, $$

• 2. if $\zeta \cdot XY^{-1} \in \varDelta$ or $YX^{-1} \cdot \zeta \in \varDelta$ and $\left\{ Y X^{-1} \cdot \xi \cdot X Y^{-1} \mid \xi \in \varXi \right\} \subset \varDelta$, then there exist $a,b \in \mathbb {F}_{q^m}^*$, such that

  $$ Y = {\text {diag}}(\textbf{M}_{\varGamma }(a), \textbf{M}_{\varGamma }(b)) \cdot X $$

with high probability.

Remark 9

Note that the set $\varXi$ has to contain at least one matrix which is not of the form

$$\begin{aligned} \xi = {\text {diag}}(\textbf{M}_{\varGamma }(\alpha ), \textbf{M}_{\varGamma }(\beta )). \end{aligned}$$

Otherwise, the conjecture does not hold, i.e. $Y = {\text {diag}}(A_{\theta _1} \cdot \textbf{M}_{\varGamma }(a), A_{\theta _2} \cdot \textbf{M}_{\varGamma }(b)) \cdot X$ for some $a,b \in \mathbb {F}_{q^m}^*$, $\theta _1, \theta _2 \in \textsf{Gal}(\mathbb {F}_{q^m}/\mathbb {F}_{q})$. Indeed,

$$ \begin{aligned} YX^{-1} \cdot \xi \cdot X Y^{-1} = {\text {diag}}\left( \textbf{M}_{\varGamma }(\theta _1^{-1}(\alpha )), \textbf{M}_{\varGamma }(\theta _2^{-1}(\beta )) \right) \in \varDelta . \end{aligned} $$

Our experiments performed in computer algebra system Sage evince that Conjecture 1 is most likely correct as soon as $|\varXi | \ge 3$. So, the resulting key–recovery algorithm can be summarized as follows.¹

Step 1.:

Compute the systematic generator matrix (4) of $C_{pub}$. Using a brute-force search, find a matrix $Q_{1}' \in \textsf{QMat}$ such that

$$ {\left\{ \begin{array}{ll} Q_{1}' \cdot V_{1,j,r,s} \cdot {Q_{1}'}^{-1} \in \varDelta \end{array}\right. } $$

(see (5)) for some set of indices $1 \le r \le k/2$ and $k/2 + 1 \le j,s \le n/2$ of size $\ge 5$. Conjecture 1 implies that $Q_1'$ is of the form (7). Since Proposition 8 allows replacing C with any semi–linear equivalent code, it follows that without loss of generality, we may assume that $\theta \in \textsf{Gal}(\mathbb {F}_{q^m} / \mathbb {F}_q)$ is the identity automorphism.

Step 2.:

For $j=k/2+1, \dots , n/2$, find matrices $Q_j' \in \textsf{QMat}$, such that

$$ {\left\{ \begin{array}{ll} \left( {Q_1'} \cdot K'_{1,j} \right) \cdot {Q'_{j}}^{-1} \in \varDelta , \\ Q_j' \cdot W_{i,j,r,s} \cdot {Q_j'}^{-1} \in \varDelta , \end{array}\right. } $$

(see (4), (6)) for some set of indices $1 \le i,r \le k/2$ and $k/2 + 1 \le s \le n/2$ of size $\ge 5$.

Step 3.:

Finally, for $i=2,\dots ,k$ find $Q_i' \in \textsf{QMat}$ satisfying

$$ {\left\{ \begin{array}{ll} Q'_i \cdot \left( K_i \cdot {Q_j'}^{-1} \right) \in \varDelta \quad \text {for all }j=k/2+1,\dots ,n/2. \end{array}\right. } $$

Step 4.:

Let $Q' = {\text {diag}}(Q'_1, \dots , Q'_{n/2})$, using Conjecture 1 we obtain

$$\begin{aligned} Q' = {\text {diag}}(A_\theta ^{-1} \textbf{M}_{\varGamma }(\alpha _1), \dots A_\theta ^{-1} \textbf{M}_{\varGamma }(\alpha _n)) \cdot Q \end{aligned}$$

for some $\theta \in \textsf{Gal}(\mathbb {F}_{q^m}/\mathbb {F}_{q})$ and $(\alpha _1, \dots , \alpha _n) \in \mathbb {F}_{q^m}^*$. Hence

$$\begin{aligned} C' = \varPhi _{\varGamma }^{-1}\left( {\text {Span}}_{\mathbb {F}_{q^m}}(G_{pub} \cdot Q'^{-1}) \right) \end{aligned}$$

is semi–linear equivalent to C and is therefore a GRS code. Indeed,

$$\begin{aligned} C'&= \left\{ \left( \theta (\alpha _1 c_1), \dots , \theta (\alpha _n c_n) \right) \mid (c_1,\dots ,c_n) \in {\text {RS}}_k(\textbf{x}) \right\} = \\ {}&= \left\{ \left( \theta (\alpha _1) f(\theta (x_1)), \dots , \theta (\alpha _1) f(\theta (x_n)) \right) \mid f \in \mathbb {F}_{q^m}[x], \deg (f) \le k-1 \right\} . \end{aligned}$$

So, after applying the Sidelnikov–Shestakov attack [27] to $C'$, it is possible to decode $C_{pub}$.

4.2 Case of Odd k

Suppose first that $Q_{(k+1)/2}$ is known. Let $G^{sys}_C = (l_{i,j}) \in \mathbb {F}_{q^m}^{k \times n}$ be the systematic generator matrix of C. It follows that the systematic form of $G_{pub} \cdot {\text {diag}}(I_{(k-1)m}, Q_{(k+1)/2}^{-1}, I_{(n-k-1)m})$ is

$$\begin{aligned} \left( \begin{array}{c|cc} \begin{matrix} I_{2m} &{} &{} &{} \\ &{} \ddots &{} &{} \\ &{} &{} I_{2m} &{} \\ &{} &{} &{} I_{m} \end{matrix} &{} \begin{matrix} J_{1} \\ \vdots \\ J_{(k-1)/2} \\ C \end{matrix} &{} \begin{matrix} K'_{1,(k+1)/2+1} &{} \dots &{} K'_{1,n/2} \\ \vdots &{} \ddots &{} \vdots \\ K'_{(k-1)/2,(k+1)/2+1} &{} \dots &{} K'_{(k-1)/2,n/2} \\ D_{(k+1)/2+1} &{} \dots &{} D_{n/2} \end{matrix} \end{array} \right) , \end{aligned}$$

(8)

where

$$ J_i = Q_i^{-1} \cdot {\left( \textbf{M}_{\varGamma }(l_{2i-1, k+1}) \; \textbf{M}_{\varGamma }(l_{2i, k+1})\right) }^\textsf{T}\in \mathbb {F}_{q}^{2m \times m}, $$

$$ C = \textbf{M}_{\varGamma }(l_{k,k+1}) \in \mathbb {F}_{q}^{m \times m}, $$

$$ D_j = \left( \textbf{M}_{\varGamma }(l_{k,2j-1}) \; \textbf{M}_{\varGamma }(l_{k,2j})\right) \cdot Q_j \in \mathbb {F}_{q}^{m \times 2m}, $$

$$ K'_{i,j} = Q_i^{-1} \cdot \begin{pmatrix} \textbf{M}_{\varGamma }(l_{2i-1, 2j-1}) &{} \textbf{M}_{\varGamma }(l_{2i-1, 2j}) \\ \textbf{M}_{\varGamma }(l_{2i, 2j-1}) &{} \textbf{M}_{\varGamma }(l_{2i, 2j}) \end{pmatrix} \cdot Q_j \in \mathbb {F}_{q}^{2m \times 2m}. $$

Hence the above–described attack can be modified as follows.

Step 1.:

In this step, we try to guess $Q_{(k+1)/2}$ (up to equivalences described in Proposition 8). To do this, for each $Q'_{(k+1)/2} \in \textsf{QMat}$ we compute the systematic form (8) of

$$\begin{aligned} G_{pub} \cdot {\text {diag}}(I_{(k-1)m}, {Q'_{(k+1)/2}}^{-1}, I_{(n-k-1)m}) \end{aligned}$$

and then check

$$ {\left\{ \begin{array}{ll} C \in \left\{ \textbf{M}_{\varGamma }(a) \mid a \in \mathbb {F}_{q^m} \right\} , \\ D_j {K'_{i,j}}^{-1} J_i, \in \left\{ \textbf{M}_{\varGamma }(a) \mid a \in \mathbb {F}_{q^m} \right\} \\ \quad \text {for all }1 \le i \le (k-1)/2, (k+1)/2 + 1 \le j \le n/2 \end{array}\right. } $$

until proper $Q'_{(k+1)/2}$ is found.

Step 2.:

For $j=(k+1)/2+1, \dots , n/2$, find matrices $Q_j' \in \textsf{QMat}$, such that

$$ {\left\{ \begin{array}{ll} Q_j' \cdot W_{i,j,r,s} \cdot {Q_j'}^{-1} \in \varDelta , \\ D_j \cdot {Q'_j}^{-1} \in \left\{ \left( \textbf{M}_{\varGamma }(a), \textbf{M}_{\varGamma }(b)\right) \mid a,b \in \mathbb {F}_{q^m} \right\} \end{array}\right. } $$

(see (4), (6)) for some set of indices $1 \le i,r \le (k-1)/2$ and $(k+1)/2 + 1 \le s \le n/2$ of size $\ge 5$.

Step 3.:

For $i=1,\dots ,(k-1)/2$ find $Q_i' \in \textsf{QMat}$ satisfying

$$ {\left\{ \begin{array}{ll} Q'_i \cdot \left( K_i \cdot {Q_j'}^{-1} \right) \in \varDelta \quad \text {for all }j=(k+1)/2+1,\dots ,n/2. \end{array}\right. } $$

Compute $Q' = {\text {diag}}(Q'_1, \dots , Q_{n/2})$ and run Step 4 of Sect. 4.1.

Since the size of $\textsf{QMat}$ is $O(q^{m^2 + (m+1)^2})$, it follows that the complexity of the attack is $O(n q^{m^2 + (m+1)^2} m^3)$ assuming brute–force search is used in each step. Note that for large m this attack is too complex. However, for $m \ge 3$ it is possible to implement another attack based on twisted squares.

5 Twisted Squares–Based Attack

Let $\textbf{U}_i$ be an i–th $m_i$–block column of $G_{pub}$, i.e.

$$ \begin{array}{ccccccc} G_{pub}= & {} \Big ( \underbrace{\textbf{U}_1}_{m-1}&\underbrace{\textbf{U}_2}_{m+1}&\dots&\underbrace{\textbf{U}_{n-1}}_{m-1}&\underbrace{\textbf{U}_n}_{m+1} \Big ) \end{array}. $$

Attack we propose is consist of the following steps.

5.1 Recovering the Support $\textbf{x}$

By $\mathbf {x_{odd}}$ we denote $(x_1, x_3, \dots , x_{n-1})$. Let $\varPi \in \mathbb {F}_q^{m \times (m-1)}$ be the projection matrix of the following form

$$ \varPi = \left( \begin{array}{c} I_{m-1} \\ 0 \end{array} \right) , $$

Consider

$$ G_{odd} = (\textbf{U}_1 \mid \textbf{U}_3 \mid \dots \mid \textbf{U}_{n-1}). $$

We have

$$\begin{aligned} G_{odd} = S {\text {Exp}}_{\varGamma }\left( G_k(\mathbf {x_{odd}})) {\text {diag}}(N_1, N_3, \dots N_{n-1} \right) , \end{aligned}$$

(9)

where $N_i = Y_i \varPi M_i \in \mathbb {F}_{q}^{m \times m-1}$. It follows that $G_{odd}$ is a generator matrix of

$$ {\text {GPC}}\left( \varPhi _{\varGamma }({\text {RS}}_k(\mathbf {x_{odd}})); N_1, \dots , N_{n-1} \right) . $$

So, Proposition 3 and Corollary 1 imply that $G_{odd}$ is a parity–check matrix of the code

$$\begin{aligned} \begin{aligned} D = {\text {GSS}}(\varPhi _{\varGamma }({\text {RS}}_{k}(\mathbf {x_{odd}}))^{\perp }; N_1^T, N_3^T, \dots , N_{n-1}^T) = \\ = {\text {GSS}}(\varPhi _{\varGamma ^*}({\text {RS}}_{k}(\mathbf {x_{odd}})^{\perp }); N_1^T, N_3^T, \dots , N_{n-1}^T), \end{aligned} \end{aligned}$$

(10)

Remark 10

Recall that, ${\text {RS}}_{k}(\mathbf {x_{odd}})^{\perp } = {\text {GRS}}_{n-k}(\mathbf {x_{odd}}, \mathbf {z_{odd}})$, where

$$\begin{aligned} \mathbf {z_{odd}} = (z_1, z_3, \dots , z_{n-1}), \quad z_i^{-1} = \prod _{\begin{array}{c} i,j \in \{ 1, 3, \dots , n-1 \} \\ j \ne i \end{array}} \left( x_i - x_j \right) \end{aligned}$$

(11)

Hence D is short representation of generalized subspace subcode of a GRS code.

It follows that it is possible to recover one of the supports $\mathbf {x_{odd}}'$ of ${\text {RS}}_{k}(\mathbf {x_{odd}})^{\perp }$ from D by applying CL–attack [9, Alg. 1 and Alg. 2] to D. Indeed, given GSS–subcode of ${\text {GRS}}_{k}(\textbf{a}, \textbf{b})$, such that the dimension of all subspaces is $\lambda > m/2$, CL–attack reconstructs a support of corresponding ${\text {GRS}}$–code by applying the algorithm of [5, §VI.B] to its twisted square.

Remark 11

Note that in order to apply CL–attack, $G_{odd}$ has to be singular, which is true if

$$\begin{aligned} km < (m-1)n/2. \end{aligned}$$

In addition, it is also possible to find $\mathbf {x_{odd}}$ in the case when

$$\begin{aligned} (n-k)m < (m-1)n/2 \end{aligned}$$

by attacking the dual of the public code (see Proposition 7).

Remark 12

Since the support of a GRS code is completely defined by fixing arbitrary three points, it follows that without loss of generality we may assume that $\mathbf {x_{odd}}' = \mathbf {x_{odd}}$.

It remains now to recover $x_2, x_4, \dots , x_n$. For the sake of convenience, we describe the recovering procedure only for $x_2$. Consider the matrix

$$ G_{odd + 2} = (\textbf{U}_1 \mid \textbf{U}_2 \mid \textbf{U}_3 \mid \textbf{U}_5 \mid \dots \mid \textbf{U}_{n-1}). $$

One can easily notice that

$$ G_{odd + 2} = S \cdot {\text {Exp}}^{*}_{\varGamma }\left( G_k\left( x_1, x_2, x_3, x_5, \dots , x_{n-1} \right) \right) \cdot {\text {diag}}(Q_1, N_3, N_5, \dots , N_{n-1}), $$

where $N_i$ are the same as in (9) and

$$ Q_{1} = {\text {diag}}(Y_2, Y_2) \cdot {\text {diag}}(M_1, M_2) \in {\text {GL}}_{2m}(\mathbb {F}_q). $$

Using Proposition 3 and Corollary 1, we see that $G_{odd + 2}$ is a generator matrix of

$$ {\text {GPC}}\left( \varPhi _{\varGamma }({\text {RS}}_{k}(x_1, x_2, x_3, x_5, \dots , x_{n-1})); Q_1, N_3, \dots , N_{n-1} \right) . $$

and a parity–check matrix of

$$ D_2 = {\text {GSS}}\left( \varPhi _{\varGamma }({\text {RS}}_{k}(x_1, x_2, x_3, x_5, \dots , x_{n-1}))^{\perp };Q_1^\textsf{T}, N_3^{\textsf{T}}, \dots , N_{n-1}^{\textsf{T}} \right) . $$

Let $G_{D_2}$ be a generator matrix of $D_2$. We have

$$ {\text {Span}}_{\mathbb {F}_q} \left( G_{D_2} \cdot {\text {diag}}\left( Q_1^\textsf{T}, N_3^{\textsf{T}}, \dots , N_{n-1}^{\textsf{T}} \right) \right) \subset \left[ \varPhi _{\varGamma }\left( {\text {RS}}_{k}\left( x_1, x_2, x_3, x_5, \dots , x_{n-1} \right) \right) \right] ^{\perp } $$

(see Sect. 2.1), it follows that

$$ G_{D_2} \cdot {\text {diag}}\left( Q_1^\textsf{T}, N_3^{\textsf{T}}, \dots , N_{n-1}^{\textsf{T}} \right) \cdot {\text {Exp}}_{\varGamma }\left( G_k(x_1, x_2, x_3, x_5, \dots , x_{n-1}) \right) ^{\textsf{T}} = 0. $$

With $\mathbf {x_{odd}}=(x_1, x_3, \dots , x_{n-1})$ being known, it is possible to find $x_2$ by iterating $w \in \mathbb {F}_{q^m}^* \setminus \{ x_1, x_3, x_5, \dots , x_{n-1} \}$ and checking whether the linear system

$$\begin{aligned} G_{D_2} \cdot {\text {diag}}\left( X_1^\textsf{T}, X_3^{\textsf{T}}, \dots , X_{n-1}^{\textsf{T}} \right) \cdot {\text {Exp}}_{\varGamma }\left( G_k(x_1, w, x_3, x_5, \dots , x_{n-1}) \right) ^{\textsf{T}} = 0, \end{aligned}$$

(12)

where $X_3, \dots , X_{n-1} \in \mathbb {F}_q^{m \times m-1}$ and

$$ X_1 = \begin{pmatrix} X_1^{(1)} &{} X_1^{(2)} \\ 0 &{} X_1^{(3)} \end{pmatrix}, \quad X_1^{(1)} \in \mathbb {F}_{q}^{m \times m-1}, X_1^{(2)} \in \mathbb {F}_{q}^{m \times m+1}, X_1^{(3)} \in \mathbb {F}_{q}^{m \times m+1} $$

has a non–zero solution. Note that in most practical cases the number of unknowns $(n/2-1)(m-1)m + 3m^2 + m = O(nm^2/2)$ is much less than the number of equations $(n/2 + 1 - k)k m^2$ and the solution, if it exists, is most likely unique up to multiplication by

$$\begin{aligned} {\text {diag}}(\textbf{M}_{\varGamma }(a_1), \textbf{M}_{\varGamma }(a_2), \textbf{M}_{\varGamma }(a_3), \textbf{M}_{\varGamma }(a_5), \dots , \textbf{M}_{\varGamma }(a_{n-1})), \quad a_i \in \mathbb {F}^*_{q^m}. \end{aligned}$$

In our experiments, the above described method allowed successfully recovering correct $x_2$ in all cases.²

Remark 13

It is also possible to reconstruct $\textbf{x}$ when neither $km < (m-1)n/2$ and $(n-k)m < (m-1)n/2$ hold. Choose the smallest $s \in \overline{1,n/2}$ such that

$$\begin{aligned} (n'-k)m > (m-1)n'/2 \end{aligned}$$

where $n' = n-2s$. Consider

$$ G_{pub}' = \begin{pmatrix} \textbf{U}_1&\textbf{U}_2&\dots&\textbf{U}_{n-2s-1}&\textbf{U}_{n-2s} \end{pmatrix} \in \mathbb {F}_{q}^{km \times n'm}, $$

$$ G_{pub}'' = \begin{pmatrix} \textbf{U}_{2s + 1}&\textbf{U}_{2s+2}&\dots&\textbf{U}_{n-1}&\textbf{U}_{n} \end{pmatrix} \in \mathbb {F}_{q}^{km \times n'm}. $$

One can easily notice that

$$ G_{pub}' = S \cdot {\text {Exp}}_{\mathcal {B}}\left( G_k \left( (x_1, \dots , x_{n-2s}) \right) \right) \cdot {\text {diag}}(Y_1, \dots Y_{n-2s}) \cdot {\text {diag}}(M_1, \dots M_{n-2s}), $$

$$ G_{pub}'' = S \cdot {\text {Exp}}_{\mathcal {B}}\left( G_k \left( (x_{2s+1}, \dots , x_{n}) \right) \right) \cdot {\text {diag}}(Y_{2s+1}, \dots Y_{n}) \cdot {\text {diag}}(M_{2s+1}, \dots M_{n}), $$

i.e. $G'_{pub}$ and $G''_{pub}$ are public keys of IKZ–cryptosystem. Therefore, it is possible to recover $x_1, \dots , x_{n-2s}$ by attacking $G'_{pub}$ as above first and then to recover $x_{n-2s+1}, \dots x_n$ by attacking $G''_{pub}$.

5.2 Recovering the Matrix Q

Since $G_{pub} = S \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x})) \cdot {\text {diag}}(Q_1, \dots , Q_{n/2})$, is follows that $G_{pub}$ is a generator matrix of

$$ {\text {GPC}}(\varPhi _{\varGamma }(G_k(\textbf{x}); Q_1, \dots , Q_{n/2}), $$

so, due to Proposition 3 $G_{pub}$ a parity–check matrix of

$$ \hat{D} = {\text {GSS}}(\varPhi _{\varGamma }(G_k(\textbf{x})^\perp ; Q_1^\textsf{T}, \dots , Q_{n/2}^\textsf{T}). $$

Let $G_{\hat{D}}$ be a generator matrix of $\hat{D}$. Since

$$\begin{aligned} {\text {Span}}_{\mathbb {F}_q}\left( G_{\hat{D}} \cdot {\text {diag}}\left( Q_1^\textsf{T}, \dots , Q_{n/2}^\textsf{T}\right) \right) \subset \varPhi _{\varGamma }(G_k(\textbf{x}))^\perp , \end{aligned}$$

it follows that

$$\begin{aligned} G_{\hat{D}} \cdot {\text {diag}}\left( Q_1^\textsf{T}, \dots , Q_{n/2}^\textsf{T}\right) \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x}))^{\textsf{T}} = 0. \end{aligned}$$

With $\textbf{x}$ being known after previous step, $Q_1, \dots , Q_{n/2}$ can be found by solving the linear system

$$ G_{\hat{D}} \cdot {\text {diag}}\left( X_1^\textsf{T}, \dots , X_{n/2}^\textsf{T}\right) \cdot {\text {Exp}}_{\varGamma }(G_k(\textbf{x}))^{\textsf{T}} = 0, $$

where $X_i$ are of the form

$$ X_i = \begin{pmatrix} X_i^{(1)} &{} X_i^{(2)} \\ 0 &{} X_i^{(3)} \end{pmatrix}, \quad X_i^{(1)} \in \mathbb {F}_{q}^{m \times m-1}, X_1^{(2)} \in \mathbb {F}_{q}^{m \times m+1}, X_1^{(3)} \in \mathbb {F}_{q}^{m \times m+1}. $$

Since again the number of equations is larger than the number of unknowns the solution is most likely be unique up to multiplication by ${\text {diag}}_{n}(\textbf{M}_{\varGamma }(\beta ))$ for some $\beta \in \mathbb {F}_{q^m}$, which was experimentally validated. The complexity of CL-attack is $O(n q^m)$ operations in $\mathbb {F}_q$, the complexity of support recovering is $O(q^m (mn)^3)$ and the complexity of recovering Q is $O((mn)^3)$. Hence the overall complexity of the attack is $O((mn)^3 q^m)$.

6 Conclusion

In this paper, it was shown that Ivanov–Krouk–Zyablov cryptosystem is insecure and its secret key can be recovered in polynomial time due to proposed key–recovery attacks. Since the first one is based only on linear algebra, it can easily be generalized to recover the matrix Q even for other classes of codes. So, the masking transform used by Ivanov, Krouk and Zyablov is intrinsically flawed. It also seems that using hiding transforms that allow decoding error bursts cannot improve key sizes compared to classic approaches due to simple message–recovery attacks based on information–set decoding.