Solving the Problem of Blockwise Isomorphism of Polynomials with Circulant Matrices

Abstract

The problem of Isomorphism of Polynomials (IP problem) is known to be important to study the security of multivariate public key cryptosystems, one of major candidates of post-quantum cryptography, against key recovery attacks. In these years, several schemes based on the IP problem itself or its generalization have been proposed. At PQCrypto 2020, Santoso introduced a generalization of the problem of Isomorphism of Polynomials, called the problem of Blockwise Isomorphism of Polynomials (BIP problem), and proposed a new Diffie-Hellman type encryption scheme based on this problem with Circulant matrices (BIPC problem). Quite recently, Ikematsu et al. proposed an attack called the linear stack attack to recover an equivalent key of Santoso’s encryption scheme. While this attack reduced the security of the scheme, it does not contribute to solve the BIPC problem itself. In the present paper, we describe how to solve the BIPC problem directly by simplifying the BIPC problem due to the conjugation property of circulant matrices. In fact, we experimentally solved the BIPC problem with the parameter, which has 256 bit security by Santoso’s security analysis and has 72.7 bit security against the linear stack attack, by about 10 min.

A Toy Example

We now demonstrate how to solve the BIPC problem for $(q,n,m,k)=(2,6,2,2)$ as a toy example. The public keys $\mathbf {f}=(\mathbf {f}_{1},\mathbf {f}_{2})=(f_{11},f_{12},f_{21},f_{22})$ and $\mathbf {g}=(\mathbf {g}_{1},\mathbf {g}_{2})=(g_{11},g_{12},g_{21},g_{22})$ are as follows.

$$\begin{aligned}&f_{11}(\mathbf {x})= {}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ &{} 1 &{} 0 &{} 0 &{} 0 &{} 1 \\ &{} &{} 0 &{} 0 &{} 0 &{} 0 \\ &{} &{} &{} 0 &{} 0 &{} 0 \\ &{} &{} &{} &{} 1 &{} 1 \\ &{} &{} &{} &{} &{} 0 \end{pmatrix}}\mathbf {x}, \qquad f_{12}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 0 &{} 0 &{} 1 &{} 1 &{} 1 \\ &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 \\ &{} &{} 1 &{} 0 &{} 1 &{} 1 \\ &{} &{} &{} 0 &{} 0 &{} 0 \\ &{} &{} &{} &{} 1 &{} 1 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \\&f_{21}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 \\ &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 \\ &{} &{} 0 &{} 1 &{} 0 &{} 0 \\ &{} &{} &{} 0 &{} 1 &{} 1 \\ &{} &{} &{} &{} 0 &{} 0 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \qquad f_{22}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} 1 &{} 0 &{} 1 &{} 0 \\ &{} 0 &{} 0 &{} 1 &{} 1 &{} 1 \\ &{} &{} 0 &{} 1 &{} 0 &{} 0 \\ &{} &{} &{} 0 &{} 0 &{} 1 \\ &{} &{} &{} &{} 1 &{} 1 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \\&g_{11}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} 1 &{} 1 &{} 0 &{} 1 \\ &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ &{} &{} 1 &{} 0 &{} 0 &{} 1 \\ &{} &{} &{} 0 &{} 1 &{} 1 \\ &{} &{} &{} &{} 1 &{} 0 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \qquad g_{12}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ &{} &{} 0 &{} 1 &{} 1 &{} 1 \\ &{} &{} &{} 1 &{} 1 &{} 1 \\ &{} &{} &{} &{} 0 &{} 0 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \\&g_{21}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ &{} 0 &{} 1 &{} 1 &{} 0 &{} 1 \\ &{} &{} 1 &{} 1 &{} 0 &{} 1 \\ &{} &{} &{} 0 &{} 0 &{} 1 \\ &{} &{} &{} &{} 1 &{} 0 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \qquad g_{22}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 1 &{} 1 &{} 0 &{} 0 &{} 0 \\ &{} 1 &{} 1 &{} 1 &{} 1 &{} 0 \\ &{} &{} 0 &{} 0 &{} 0 &{} 1 \\ &{} &{} &{} 0 &{} 0 &{} 0 \\ &{} &{} &{} &{} 1 &{} 0 \\ &{} &{} &{} &{} &{} 0 \end{pmatrix}}\mathbf {x}, \end{aligned}$$

where the coefficient matrices are expressed by triangular matrices. Our aim is to recover $S_{1},S_{2}\in \mathrm {Circ}(6)$, $T_{1},T_{2}\in \mathrm {Circ}(2)$ satisfying

$$\begin{aligned} \begin{aligned} \begin{pmatrix}g_{11}(\mathbf {x}) \\ g_{12}(\mathbf {x})\end{pmatrix} =&T_{1}\begin{pmatrix}f_{11}(S_{1}(\mathbf {x})) \\ f_{12}(S_{1}(\mathbf {x}))\end{pmatrix} +T_{2}\begin{pmatrix}f_{21}(S_{2}(\mathbf {x})) \\ f_{22}(S_{2}(\mathbf {x}))\end{pmatrix},\\ \begin{pmatrix}g_{21}(\mathbf {x}) \\ g_{22}(\mathbf {x})\end{pmatrix} =&T_{1}\begin{pmatrix}f_{21}(S_{1}(\mathbf {x})) \\ f_{22}(S_{1}(\mathbf {x}))\end{pmatrix} +T_{2}\begin{pmatrix}f_{11}(S_{2}(\mathbf {x})) \\ f_{12}(S_{2}(\mathbf {x}))\end{pmatrix}. \end{aligned} \end{aligned}$$

(8)

Let $\theta$ be a cubic root of 1 (i.e. $\theta ^{2}+\theta +1=0$),

$$\begin{aligned}&K_{6}:= {\begin{pmatrix} 1 &{} &{} &{} &{} &{} \\ &{} &{} &{} 1 &{} &{} \\ &{} &{} &{} &{} 1 &{} \\ &{} 1 &{} &{} &{} &{} \\ &{} &{} 1 &{} &{} &{} \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}, \quad \varTheta _{3}:=\begin{pmatrix} 1 &{} 1 &{} 1 \\ 1 &{} \theta &{} \theta ^{2} \\ 1 &{} \theta ^{2} &{} \theta \end{pmatrix},\quad Q_{2}=B_{2}:=\begin{pmatrix}1 &{} 0 \\ 1 &{} 1\end{pmatrix} \end{aligned}$$

and $Q_{6}:=K_{6}\left( \varTheta _{3}\otimes B_{2}\right)$. Then $\bar{\mathbf {f}}_{1}=Q_{2}^{-1}\circ \mathbf {f}_{1} \circ Q_{6}=(\bar{f}_{11},\bar{f}_{12})$, $\bar{\mathbf {f}}_{2}=Q_{2}^{-1}\circ \mathbf {f}_{2} \circ Q_{6}=(\bar{f}_{21},\bar{f}_{22})$, $\bar{\mathbf {g}}_{1}=Q_{2}^{-1}\circ \mathbf {g}_{1} \circ Q_{6}=(\bar{g}_{11},\bar{g}_{12})$, $\bar{\mathbf {g}}_{2}=Q_{2}^{-1}\circ \mathbf {g}_{2} \circ Q_{6}=(\bar{g}_{21},\bar{g}_{22})$ are as follows.

$$\begin{aligned}&\bar{f}_{11}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} 0 &{} \theta &{} 0 &{} \theta ^{2} \\ &{} 0 &{} \theta ^{2} &{} 1 &{} \theta &{} 1 \\ &{} &{} 1 &{} 1 &{} 0 &{} \theta \\ &{} &{} &{} \theta &{} \theta ^{2} &{} 1 \\ &{} &{} &{} &{} 1 &{} 1 \\ &{} &{} &{} &{} &{} \theta ^{2} \end{pmatrix}}\mathbf {x}, \qquad \bar{f}_{12}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 0 &{} 1 &{} \theta ^{2} &{} 1 &{} \theta \\ &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ &{} &{} \theta ^{2} &{} 1 &{} 0 &{} 0 \\ &{} &{} &{} \theta &{} 0 &{} 0 \\ &{} &{} &{} &{} \theta &{} 1 \\ &{} &{} &{} &{} &{} \theta ^{2} \end{pmatrix}}\mathbf {x}, \\&\bar{f}_{21}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 \\ &{} 1 &{} 1 &{} 0 &{} 1 &{} 0 \\ &{} &{} \theta &{} \theta &{} 0 &{} \theta \\ &{} &{} &{} 1 &{} \theta ^{2} &{} 1 \\ &{} &{} &{} &{} \theta ^{2} &{} \theta ^{2} \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \qquad \bar{f}_{22}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 1 &{} 0 &{} \theta ^{2} &{} 0 &{} \theta \\ &{} 1 &{} \theta ^{2} &{} 0 &{} \theta &{} 0 \\ &{} &{} 0 &{} 1 &{} 0 &{} 1 \\ &{} &{} &{} \theta ^{2} &{} 1 &{} 0 \\ &{} &{} &{} &{} 0 &{} 1 \\ &{} &{} &{} &{} &{} \theta 1 \end{pmatrix}}\mathbf {x}, \\&\bar{g}_{11}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 0 &{} 0 &{} \theta ^{2} &{} \theta &{} \theta &{} \theta ^{2} \\ &{} 0 &{} 1 &{} \theta &{} 1 &{} \theta ^{2} \\ &{} &{} \theta ^{2} &{} 1 &{} 0 &{} 0 \\ &{} &{} &{} 1 &{} 0 &{} 1 \\ &{} &{} &{} &{} \theta &{} 1 \\ &{} &{} &{} &{} &{} 1 \end{pmatrix}}\mathbf {x}, \qquad \bar{g}_{12}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} 1 &{} \theta ^{2} &{} 1 &{} \theta \\ &{} 0 &{} 1 &{} 0 &{} 1 &{} 0 \\ &{} &{} \theta ^{2} &{} \theta &{} 0 &{} 1 \\ &{} &{} &{} \theta &{} 1 &{} 0 \\ &{} &{} &{} &{} \theta &{} \theta ^{2} \\ &{} &{} &{} &{} &{} \theta ^{2} \end{pmatrix}}\mathbf {x}, \\&\bar{g}_{21}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 \\ &{} 0 &{} \theta ^{2} &{} 0 &{} \theta &{} 0 \\ &{} &{} 1 &{} 0 &{} 0 &{} 1 \\ &{} &{} &{} \theta &{} 1 &{} 1 \\ &{} &{} &{} &{} 1 &{} 0 \\ &{} &{} &{} &{} &{} \theta ^{2} \end{pmatrix}}\mathbf {x}, \qquad \bar{g}_{22}(\mathbf {x})={}^{t}\!\mathbf {x}{\begin{pmatrix} 1 &{} 1 &{} \theta &{} \theta &{} \theta ^{2} &{} \theta ^{2} \\ &{} 0 &{} \theta ^{2} &{} \theta ^{2} &{} \theta &{} \theta \\ &{} &{} \theta &{} \theta &{} 0 &{} 1 \\ &{} &{} &{} \theta ^{2} &{} 1 &{} 0 \\ &{} &{} &{} &{} \theta ^{2} &{} \theta ^{2} \\ &{} &{} &{} &{} &{} \theta \end{pmatrix}}\mathbf {x}. \end{aligned}$$

Then the problem of recovering $S_{1},S_{2},T_{1},T_{2}$ with (8) is reduced to the problem of recovering $\bar{S}_{1}=Q_{6}^{-1}\circ S_{1}\circ Q_{6}$, $\bar{S}_{2}=Q_{6}^{-1}\circ S_{2}\circ Q_{6}$, $\bar{T}_{1}=Q_{2}^{-1}\circ T_{1}\circ Q_{2}$, $\bar{T}_{2}=Q_{2}^{-1}\circ T_{2}\circ Q_{2}$ satisfying

$$\begin{aligned} \begin{aligned} \begin{pmatrix}\bar{g}_{11}(\mathbf {x}) \\ \bar{g}_{12}(\mathbf {x})\end{pmatrix} =&\bar{T}_{1}\begin{pmatrix}\bar{f}_{11}(\bar{S}_{1}(\mathbf {x})) \\ \bar{f}_{12}(\bar{S}_{1}(\mathbf {x}))\end{pmatrix} +\bar{T}_{2}\begin{pmatrix}\bar{f}_{21}(\bar{S}_{2}(\mathbf {x})) \\ \bar{f}_{22}(\bar{S}_{2}(\mathbf {x}))\end{pmatrix},\\ \begin{pmatrix}\bar{g}_{21}(\mathbf {x}) \\ \bar{g}_{22}(\mathbf {x})\end{pmatrix} =&\bar{T}_{1}\begin{pmatrix}\bar{f}_{21}(\bar{S}_{1}(\mathbf {x})) \\ \bar{f}_{22}(\bar{S}_{1}(\mathbf {x}))\end{pmatrix} +\bar{T}_{2}\begin{pmatrix}\bar{f}_{11}(\bar{S}_{2}(\mathbf {x})) \\ \bar{f}_{12}(\bar{S}_{2}(\mathbf {x}))\end{pmatrix}. \end{aligned} \end{aligned}$$

(9)

Due to Lemma 2, we see that $\bar{S}_{1},\bar{S}_{2},\bar{T}_{1},\bar{T}_{2}$ are written by

$$\begin{aligned} \bar{S}_{1}=&\mathrm {diag}\left( \begin{pmatrix}1 &{} s_{12}^{(1)} \\ {} &{} 1 \end{pmatrix}, \begin{pmatrix}s_{21}^{(1)} &{} s_{22}^{(1)} \\ {} &{} s_{21}^{(1)} \end{pmatrix}, \begin{pmatrix}s_{31}^{(1)} &{} s_{32}^{(1)} \\ {} &{} s_{31}^{(1)} \end{pmatrix} \right) ,\\ \bar{S}_{2}=&\mathrm {diag}\left( \begin{pmatrix}1 &{} s_{12}^{(2)} \\ {} &{} 1 \end{pmatrix}, \begin{pmatrix}s_{21}^{(2)} &{} s_{22}^{(2)} \\ {} &{} s_{21}^{(2)} \end{pmatrix}, \begin{pmatrix}s_{31}^{(2)} &{} s_{32}^{(2)} \\ {} &{} s_{31}^{(2)} \end{pmatrix} \right) , \\ \bar{T}_{1}=&\begin{pmatrix} t_{1}^{(1)} &{} t_{2}^{(1)} \\ {} &{} t_{1}^{(1)}\end{pmatrix},\qquad \bar{T}_{2}=\begin{pmatrix} t_{1}^{(2)} &{} t_{2}^{(2)} \\ {} &{} t_{1}^{(2)}\end{pmatrix}. \end{aligned}$$

We first study the coefficients of $x_{1}^{2}$ in $\bar{g}_{12},\bar{g}_{22}$. The relation (9) gives the following equations.

$$\begin{aligned} \begin{pmatrix} 1 \\ 1 \end{pmatrix} =\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} t_{1}^{(1)} \\ t_{1}^{(2)} \end{pmatrix}. \end{aligned}$$

We then get $t_{1}^{(1)}=1$ and $t_{1}^{(2)}=1$. Similarly, from the coefficients of $x_{1}^{2}$ in $\bar{g}_{11},\bar{g}_{21}$, we have

$$\begin{aligned} \begin{pmatrix} 0 \\ 1 \end{pmatrix} =\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} t_{2}^{(1)} \\ t_{2}^{(2)} \end{pmatrix} +\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} t_{1}^{(1)} \\ t_{1}^{(2)} \end{pmatrix}. \end{aligned}$$

From the equations above, we obtain $t_{2}^{(1)}=1$ and $t_{2}^{(2)}=0$. We thus have $T_{1},T_{2}$ as

$$\begin{aligned} T_{1}=Q_{2}\begin{pmatrix} 1 &{} 1 \\ {} &{} 1 \end{pmatrix}Q_{2}^{-1} =J_{2},\qquad T_{2}=Q_{2}\begin{pmatrix} 1 &{} \\ &{} 1\end{pmatrix}Q_{2}^{-1} =I_{2}. \end{aligned}$$

(10)

Next, we study the coefficient of $x_{1}x_{3}$ in $\bar{g}_{12},\bar{g}_{22}$. From (9) and (10), we have

$$\begin{aligned} \begin{pmatrix} 1 \\ \theta \end{pmatrix} =\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} s_{21}^{(1)} \\ s_{21}^{(2)} \end{pmatrix}. \end{aligned}$$

We then get $s_{21}^{(1)}=1$, $s_{21}^{(2)}=\theta$. Similarly, the following equations are derived from the coefficients of $x_{1}x_{4}$, $x_{1}x_{5}$ and $x_{1}x_{6}$ in $\bar{g}_{12},\bar{g}_{22}$.

$$\begin{aligned} \begin{pmatrix} \theta ^{2} \\ \theta \end{pmatrix} =&\begin{pmatrix} \theta ^{2} &{} \theta ^{2} \\ \theta ^{2} &{} \theta ^{2} \end{pmatrix} \begin{pmatrix} s_{21}^{(1)} \\ s_{21}^{(2)} \end{pmatrix} +\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} s_{22}^{(1)} \\ s_{22}^{(2)} \end{pmatrix},\\ \begin{pmatrix} 1 \\ \theta ^{2} \end{pmatrix} =&\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} s_{31}^{(1)} \\ s_{31}^{(2)} \end{pmatrix}, \\ \begin{pmatrix} \theta \\ \theta ^{2} \end{pmatrix} =&\begin{pmatrix} \theta &{} \theta \\ \theta &{} \theta \end{pmatrix} \begin{pmatrix} s_{31}^{(1)} \\ s_{31}^{(2)} \end{pmatrix} +\begin{pmatrix} 1 &{} 0 \\ 0 &{} 1 \end{pmatrix} \begin{pmatrix} s_{32}^{(1)} \\ s_{32}^{(2)} \end{pmatrix}. \\ \end{aligned}$$

Then we get $s_{22}^{(1)}=1$, $s_{22}^{(2)}=0$, $s_{31}^{(1)}=1$, $s_{31}^{(2)}=\theta ^{2}$, $s_{32}^{(1)}=1$ and $s_{32}^{(2)}=0$. To recover the remaining parameters $s_{12}^{(1)},s_{12}^{(2)}$, we study the coefficients of $x_{2}^{2}$ in $\bar{g}_{12},\bar{g}_{22}$ and have

$$\begin{aligned} 0=s_{12}^{(1)}{}^{2}+s_{12}^{(2)}, \qquad 0=s_{12}^{(1)}+s_{12}^{(2)}{}^{2}. \end{aligned}$$

Since $s_{12}^{(1)},s_{12}^{(2)}\in \mathbf{F}_{2}$, the solution of the equations above is $s_{12}^{(1)}=s_{12}^{(2)}$. To fix $s_{12}^{(1)},s_{12}^{(2)}$ uniquely, we further study the coefficients $x_{2}x_{3}$ in $\bar{g}_{12},\bar{g}_{22}$ and have the equations

$$\begin{aligned} 1=s_{12}^{(1)}s_{21}^{(1)}+\theta ^{2}s_{21}^{(2)}, \qquad \theta ^{2}=\theta ^{2}s_{21}^{(1)}+s_{12}^{(2)}s_{21}^{(2)}. \end{aligned}$$

Since $s_{21}^{(1)}=1$, $s_{21}^{(2)}=\theta$, we obtain $s_{12}^{(1)}=s_{12}^{(2)}=0$. We thus conclude that

$$\begin{aligned} \begin{aligned} S_{1}=&Q_{6}\cdot \mathrm {diag}\left( \begin{pmatrix} 1 &{} 0 \\ {} &{} 1 \end{pmatrix}, \begin{pmatrix} 1 &{} 1 \\ {} &{} 1 \end{pmatrix}, \begin{pmatrix} 1 &{} 1 \\ {} &{} 1 \end{pmatrix} \right) Q_{6}^{-1}=I_{6}+J_{6}+J_{6}^{2}+J_{6}^{4}+J_{6}^{5},\\ S_{2}=&Q_{6}\cdot \mathrm {diag}\left( \begin{pmatrix} 1 &{} 0 \\ {} &{} 1 \end{pmatrix}, \begin{pmatrix} \theta &{} 0 \\ {} &{} \theta \end{pmatrix}, \begin{pmatrix} \theta ^{2} &{} 0 \\ {} &{} \theta ^{2} \end{pmatrix} \right) Q_{6}^{-1}=J_{6}^{4}. \end{aligned} \end{aligned}$$

(11)

The solution of this BIPC problem is given by (10) and (11).    $\square$