Multivariate Encryption Schemes Based on Polynomial Equations over Real Numbers

Abstract

The MQ problem, an NP-complete problem, is related to the security of Multivariate Public Key Cryptography (MPKC). Its variant, the constrained MQ problem, was first considered in constructing secure multivariate encryption schemes using the pq-method proposed at ProvSec2018. In this paper, we propose an encryption scheme named PERN, whose key space completely includes that of the pq-method. The decryption of PERN uses methods of solving nonlinear equations over the real numbers, which is different from the decryption of the existing encryption schemes in MPKC. The construction of PERN is fairly flexible, which enables us to construct a multivariate encryption scheme, whose public key consists of multivariate polynomials of degree 2, 3 or higher degrees while constraining its public key to a reasonable size.

1 Introduction

Multivariate Public Key Cryptography (MPKC) [8], which is a candidate for post-quantum cryptography, uses multivariate polynomial systems as its public key, and in most cases, its security is based on the difficulty of solving a set of multivariate polynomials. This problem of solving a set of multivariate polynomials is called the MP problem as follows.

MP problem: For a prime number q and positive integers m, n, let $\mathcal {F}(\mathbf {x})$ be a polynomial system of m polynomials over a finite field $\mathbb {F}_{q}$ in n variables $\mathbf {x}=(x_1,\ldots ,x_n)$. Then, find $\mathbf {x}_0\in \mathbb {F}_{q}^n$ such that $\mathcal {F}(\mathbf {x}_0)=\mathbf {0}$.

The constrained MP problem is derived from the MP problem.

Constrained MP problem: For a prime number q and positive integers m, n, L, let $\mathcal {F}(\mathbf {x})$ be a polynomial system of m polynomials over $\mathbb {F}_{q}$ in n variables $\mathbf {x}=(x_1,\ldots ,x_n)$. Then, find $\mathbf {x}_0=(x_{0,1},\ldots ,x_{0,n})\in \mathbb {Z}^n$ such that $\mathcal {F}(\mathbf {x}_0)=\mathbf {0}$ and $-\frac{L}{2}<x_{0,i}\le \frac{L}{2}\ \ (i=1,\ldots ,n)$.

When only quadratic polynomials are used in the (constrained) MP problem, the problem is called the (constrained) MQ problem. At ProvSec2018, Yasuda [37] introduced the constrained MQ problem for the first time, and proposed a method called the pq-method for constructing multivariate encryption schemes whose security is mainly based on the difficulty of solving the constrained MQ problem. The constrained MP problem is also related to the SIS problem. In fact, the SSNE Problem [30] derived from the SIS problem is very similar to the constrained MP problem.

As MPKC encryption schemes, Simple Matrix Scheme [31], EFC [29], and HFERP [16] are known. A detailed cryptanalysis for HFERP is not yet done since it was recently proposed. For Simple Matrix Scheme and EFC, critical attacks have not been reported, but they require using very large parameters, which sacrifices the performance of encryption and decryption. Because of such circumstances, developing new encryption schemes in MPKC becomes an important problem.

One reason that accounts for the difficulty of designing a secure MPKC encryption scheme is the difficulty of constructing trapdoor one-way functions given by injective polynomial maps. However, by adding a restriction on the definition range of a polynomial map, the map can easily become injective. Consequently, it is easy to construct an injective trapdoor one-way function with a constrained polynomial map, and this function can be used to construct MPKC encryption schemes whose security is based on the difficulty of solving the constrained MP problem.

Most of the MPKC encryption schemes uses a bipolar structure. The key generation of a multivariate encryption scheme with the bipolar structure is described as follows.

• 1. Choose an injective multivariate polynomial map $G(\mathbf {x}):\mathbb {F}_q^n\rightarrow \mathbb {F}_q^m$ whose inverse can be computed efficiently.

• 2. Choose randomly affine isomorphisms S, T on $\mathbb {F}_q^n,\mathbb {F}_q^m$, respectively.

• 3. Compute $F(\mathbf {x})=T\circ G(\mathbf {x})\circ S:\mathbb {F}_q^n\rightarrow \mathbb {F}_q^m$.

$F(\mathbf {x})$ is used as a public key, and the secret key consists of $G(\mathbf {x}),T$ and S. $G(\mathbf {x})$ is called the central map of this scheme. Encryption and decryption processes are described as follows.

• Encryption: For a plaintext $\mathbf {m}\in \mathbb {F}_q^n$, compute $\mathbf {c}=F(\mathbf {m})$. $\mathbf {c}$ is a ciphertext.

• Decryption: For a ciphertext $\mathbf {c}\in \mathbb {F}_q^m$, compute (1) $\mathbf {b}_1=T^{-1}(\mathbf {c})$, (2) $\mathbf {b}_2=G^{-1}(\mathbf {b}_1)$, (3) $\mathbf {m}'=S^{-1}(\mathbf {b}_2)$ in this order. $\mathbf {m}'$ coincides with the plaintext $\mathbf {m}$.

The security of the schemes using the bipolar structure is based on the difficulty of solving the (usual) MP problem. If we want to change this security assumption to the constrained MP problem, the map $G(\mathbf {x}):\mathbb {F}_q^n\rightarrow \mathbb {F}_q^m$ should be changed to a constrained polynomial map $G(\mathbf {x}):\mathcal {I}\rightarrow \mathbb {F}_q^m$ where $\mathcal {I}$ is a proper subset of $\mathbb {F}_q^n$ and $\mathbf {m}$ should be chosen from $\mathcal {I}$. Here, $G(\mathbf {x})$ is sufficient to be injective on $\mathcal {I}$. Note that the definition range of $F(\mathbf {x})$ is $S^{-1}(\mathcal {I})$. The pq-method also uses the bipolar structure. (However, S is restricted as $\mathcal {I}=S^{-1}(\mathcal {I})$.) The construction of $G(\mathbf {x})$ in the pq-method is as follows. First, we construct a central map $G_0(\mathbf {x})$ of an (previously proposed) encryption scheme (e.g. the Matsumoto-Imai scheme [22]) over $\mathbb {F}_{p}$, where p is enough smaller than q. $G_0(\mathbf {x})$ is then lifted into a polynomial map $\varPhi (\mathbf {x})$ with integer coefficients. Next, prepare a certain polynomial map $\varPsi _R(\mathbf {x})$ with integer coefficients, $G(\mathbf {x})$ is defined by $G(\mathbf {x})=\varPhi (\mathbf {x})\,+\,\varPsi _R(\mathbf {x})$. ($\varPsi _R(\mathbf {x})$ is a polynomial map appended to enhance security) In the decryption algorithm of the pq-method, the computation of $\mathbf {b}_2=G^{-1}(\mathbf {b}_1)$ is done as follows: From $\mathbf {b}_1=G(\mathbf {b}_2)=\varPhi (\mathbf {b}_2)+\varPsi _R(\mathbf {b}_2)$, the part $\varPsi _R(\mathbf {b}_2)$ can be eliminated due to its special design in the pq-method. After that, $\mathbf {b}_2$ can be obtained by inverting $G_0(\mathbf {x})$. We can say that the pq-method is a modifier that changes encryption schemes in MPKC over $\mathbb {F}_{p}$ to encryption schemes over $\mathbb {F}_{q}$. However, the pq-method requires a constraint on the domain of $G(\mathbf {x})$. Due to this constraint, $G(\mathbf {x})$ can become injective. By the existence of the constraint, the security of the pq-method is related to the constrained MQ problem.

In this paper, we propose a new multivariate encryption scheme called PERN (Polynomial Equations over the Real Numbers), whose security is mainly based on the difficulty of solving the constrained MP problem. PERN resembles the pq-method, but PERN does not use a central map of a previously proposed encryption scheme for the construction of $G(\mathbf {x})$. As a $\varPhi (\mathbf {x})$, we can choose any polynomial map with small integer coefficients. This implies that the key space of PERN completely includes that of the pq-method. In the decryption of PERN, we need to solve a system of 2n equations in n variables with integer coefficients. To solve such a system, we use techniques of solving a system of nonlinear equations over the real numbers, and the fact that its solution has integer components. Since these techniques of solving a system of nonlinear equations over the real numbers are applicable to polynomial systems of any degree, $\varPhi (\mathbf {x})$ (and $\varPsi _R(\mathbf {x})$) can be chosen with any degree in principle. For the first time, techniques for solving the system of nonlinear equations over the real numbers are used for the decryption in MPKC (Table 1).

Table 1. Different solvers used in the decryption of MPKCs

In the proposed scheme, the affine isomorphism S is fixed to be an identity map. Therefore, the set of monomials appearing in $G(\mathbf {x})$ and $F(\mathbf {x})$ can be adjusted freely. This means that the key length can also be adjusted freely. Hence, we do not need to restrict the degree of polynomials to 2 or 3 due to the key length considerations as in the previous MPKC schemes. As another advantage of the proposed scheme, the complexity of the Gröbner basis attack can be maximized. However, if the number of monomials appearing in $G(\mathbf {x})$ and $F(\mathbf {x})$ is too few, the complexity of the Gröbner basis attack decreases and the attack against the inhomogeneous SIS problem works effectively on the proposed scheme. Moreover, it may increase the number of equivalent keys. Therefore, the proposed scheme should take a large number of monomials.

2 Trapdoor Functions by Multivariate Polynomials with Integer Coefficients

For a positive integer l, we denote the least non-negative remainder of an integer a by $a\ \mathrm {mod}\ l$, and the least absolute remainder of a by $\mathrm {lift}_l(a)$. For $a\in \mathbb {Z}/l\mathbb {Z}$, $a\,\mathrm {mod}\,l$ and $\mathrm {lift}_l(a)$ are defined similarly. $I_l$ is defined by $I_l=(-l/2,l/2]\cap \mathbb {Z}$, then $a\,\mathrm {mod}\,l\in [0,l-1]$ and $\mathrm {lift}_l(a)\in I_l$.

Let $x_1,\ldots ,x_n$ be n independent variables and $\mathbf {x}=(x_1,\ldots ,x_n)$. Let

$$\begin{aligned} \varPhi (\mathbf {x})=(\phi _1(\mathbf {x}),\ldots ,\phi _n(\mathbf {x}))\in \mathbb {Z}[\mathbf {x}]^n,\ \ \varPsi (\mathbf {x})=(\psi _1(\mathbf {x}),\ldots ,\psi _n(\mathbf {x}))\in \mathbb {Z}[\mathbf {x}]^n \end{aligned}$$

be two polynomial systems with integer coefficients of which absolute values are small. Let L be an odd positive number, and $M_{\varPhi },M_{\varPsi }$ be positive integers such that

$$\begin{aligned} M_{\varPhi }\ge \underset{\,i=1,\ldots ,n}{\mathrm {max}}\big \{|\phi _i(\tilde{\mathbf {d}})|\ \big |\ \tilde{\mathbf {d}}\in I_L^{\,n}\big \},\ \ \ M_{\varPsi }\ge \underset{\,i=1,\ldots ,n}{\mathrm {max}}\big \{|\psi _i(\tilde{\mathbf {d}})|\ \big |\ \tilde{\mathbf {d}}\in I_L^{\,n}\big \}. \end{aligned}$$

(1)

For example, if $\phi _i^{\,\mathrm {abs}}(\mathbf {x})\ (i=1,\ldots ,n)$ are polynomials whose coefficients are given by the absolute value of the corresponding coefficients of $\phi _i(\mathbf {x})$, then

$$\begin{aligned} M_{\varPhi }=\underset{\,i=1,\ldots ,n}{\mathrm {max}}&\left\{ \phi _i^{\,\mathrm {abs}}\left( \frac{L-1}{2}\right) \right\} \end{aligned}$$

satisfies (1). This is similar for $M_{\varPsi }$.

Taking a (large) prime number q, we choose positive integers $r_1,\ldots ,r_n\,(<q)$ such that

$$\begin{aligned} 2M_{\varPhi }<\underset{\,k=1,\ldots ,2M_{\varPsi }}{\mathrm {min}}\{|\mathrm {lift}_q(r_ik)|\}\ \ \ (i=1,\ldots ,n) \end{aligned}$$

(2)

and define $\varLambda _i=\{\mathrm {lift}_q(r_ik)\ |\ k=0,\pm 1,\pm 2,\ldots ,\pm M_{\varPsi }\}$. The existence of such $r_i$ relies on q being sufficiently large. In fact, $q>4M_{\varPhi }M_{\varPsi }$ is necessary. Moreover, $r_i>2M_{\varPhi }$ is also needed.

From (2), for $i=1,\ldots ,n$, we have

$$\begin{aligned} |\mathrm {lift}_q(\lambda -\lambda ')|>2M_{\varPhi }\ \ (\forall \lambda ,\lambda '\in \varLambda _i\ (\lambda \not =\lambda ')). \end{aligned}$$

(3)

In fact, for $\lambda =r_ik,\lambda '=r_ik'\in \varLambda _i$, from $|k-k'|<2M_{\varPsi }$,

$$\begin{aligned} |\mathrm {lift}_q(\lambda -\lambda ')|=|\mathrm {lift}_q(r_i(k-k'))|=|\mathrm {lift}_q(r_i|k-k'|)|>2M_{\varPhi }. \end{aligned}$$

We define polynomial systems,

$$\begin{aligned} \varPsi _R(\mathbf {x})&=(r_1\psi _1(\mathbf {x}),\ldots ,r_n\psi _n(\mathbf {x}))\in \mathbb {Z}[\mathbf {x}]^n.\\ G(\mathbf {x})&=(g_1(\mathbf {x}),\ldots ,g_n(\mathbf {x}))=\left( \varPhi (\mathbf {x})+\varPsi _R(\mathbf {x})\right) \,\mathrm {mod}\,q\in \mathbb {F}_{q}[\mathbf {x}]^n. \end{aligned}$$

Then, $G(\mathbf {x})$ can be regarded as a map $G:\mathbb {Z}^n \rightarrow \mathbb {F}_{q}^n$. Regarding the relation between $\varPhi$, $\varPsi$ and G, we have the following lemma.

Lemma 1

For $\widetilde{\mathbf {d}}\in I_L^{\,n}$, let $\mathbf {c}=(c_1,\ldots ,c_n)=G(\widetilde{\mathbf {d}})\in \mathbb {F}_{q}^{\,n}$. Then, for $i=1,\ldots ,n$, there is a unique $\lambda _i\in \varLambda _i$ such that $|\mathrm {lift}_q(c_i-\lambda _i)|<M_{\varPhi }$. Moreover, when we write $\tilde{a}_i=\mathrm {lift}_q(c_i-\lambda _i),\ \tilde{b}_i=\mathrm {lift}_q(\lambda _i/r_i\ \mathrm {mod}\,q)\ \ (i=1,\ldots ,n)$,

$$\begin{aligned} \varPhi (\widetilde{\mathbf {d}})=(\tilde{a}_1,\ldots ,\tilde{a}_n),\ \ \varPsi (\widetilde{\mathbf {d}})=(\tilde{b}_1,\ldots ,\tilde{b}_n). \end{aligned}$$

From this lemma, we know for any $\mathbf {c}=(c_1,\ldots ,c_n)\in G(I_L^{\,n})(\subset \mathbb {F}_{q}^{\,n})$, the following holds:

• $\widetilde{\mathbf {d}}\in I_L^{\,n}$ is a solution of $G(\mathbf {x})=\mathbf {c}$.

• $\Leftrightarrow$ $\widetilde{\mathbf {d}}$ is a solution of the system of (constrained) nonlinear equations with integer coefficients, $\varPhi (\mathbf {x})=(\tilde{a}_1,\ldots ,\tilde{a}_n)$, $\varPsi (\mathbf {x})=(\tilde{b}_1,\ldots ,\tilde{b}_n)$ appeared in Lemma 1.

From the above, an algorithm for computing $G^{-1}(\mathbf {c})\in I_L^{\,n}$ is obtained as follows.

• 1. For all $i=1,\ldots ,n$, find $\tilde{b}_i\in \{0,\pm 1,\pm 2,\ldots ,\pm M_{\varPsi }\}$ such that $|\mathrm {lift}_q(c_i-r_i\tilde{b}_i)|$$<M_{\varPhi }$, and set $\tilde{a}_i=\mathrm {lift}_q(c_i-r_i\tilde{b}_i)\in \mathbb {Z}$.

• 2. Solve the system of constrained nonlinear equations with integer coefficients,

  $$\begin{aligned} \varPhi (\mathbf {x})=(\tilde{a}_1,\ldots ,\tilde{a}_n),\ \varPsi (\mathbf {x})=(\tilde{b}_1,\ldots ,\tilde{b}_n), \end{aligned}$$

  and output a solution $\tilde{\mathbf {d}}\in I_L^{\,n}$.

3 Encryption Scheme PERN

3.1 Key Generation, Encryption and Decryption

Let E be a finite subset of $(\mathbb {Z}_{\ge 0})^n$. For $\mathbf {e}=(e_1,\ldots ,e_n)\in E$, $\mathbf {x}^{\mathbf {e}}$ denotes the monomial $x_1^{e_1}\cdots x_n^{e_n}$. We define

$$\begin{aligned} \mathbb {Z}[\mathbf {x}]_E&:=\mathrm {Span}_{\mathbb {Z}}\{\mathbf {x}^{\mathbf {e}}\,|\,\mathbf {e}\in E\}(\subset \mathbb {Z}[\mathbf {x}]),\\ \mathbb {F}_{q}[\mathbf {x}]_E&:=\mathrm {Span}_{\mathbb {F}_{q}}\{\mathbf {x}^{\mathbf {e}}\,|\,\mathbf {e}\in E\}(\subset \mathbb {F}_{q}[\mathbf {x}]). \end{aligned}$$

$\varPhi (\mathbf {x}),\varPsi (\mathbf {x})$ appeared in the previous section are chosen as $\varPhi (\mathbf {x}),\varPsi (\mathbf {x})\in (\mathbb {Z}[\mathbf {x}]_E)^n$. Then, we construct $G(\mathbf {x})$ in the same way as shown in the previous section.

The new encryption scheme, PERN makes use of $G(\mathbf {x})$ as a trapdoor function. Choose a random affine isomorphism T on $\mathbb {F}_{q}^n$, then $F(\mathbf {x})=T\,\circ \, G(\mathbf {x})$ is the public key of PERN.

• Key Generation Algorithm Let $L,L_G$ be odd positive integers, n a positive integer, and E a finite subset of $(\mathbb {Z}_{\ge 0})^n$.

  • 1. Randomly choose multivariate polynomial systems $\varPhi (\mathbf {x}),\varPsi (\mathbf {x})=(\psi _1(\mathbf {x}),$ $\ldots ,\psi _n(\mathbf {x}))\in (\mathbb {Z}[\mathbf {x}]_E)^n$ whose all coefficients belong to $I_{L_G}$.

  • 2. Compute $M_{\varPhi },M_{\varPsi }$ satisfying (1), and choose an odd prime number q such that $q>4M_{\varPhi }M_{\varPsi }$.

  • 3. Choose positive integers $(M_{\varPhi }<)\ r_1,\ldots ,r_n\;(<q)$ such that

    $$\begin{aligned} 2M_{\varPhi }<\mathrm {min}_{\,k=1,\ldots ,2M_{\varPsi }}\{|\mathrm {lift}_q(r_ik)|\}\ \ (i=1,\ldots ,n). \end{aligned}$$

    If such $r_1,\ldots ,r_n$ can not be found, go back to Step 2 and reselect q.

  • 4. Compute $\varPsi _{\!R}(\mathbf {x})=(r_1\psi _1(\mathbf {x}),\ldots ,r_n\psi _n(\mathbf {x}))\in (\mathbb {Z}[\mathbf {x}]_E)^n$, and

    $$\begin{aligned} G(\mathbf {x})=(g_1(\mathbf {x}),\ldots ,g_n(\mathbf {x}))=\left( \varPhi (\mathbf {x})+\varPsi _{\!R}(\mathbf {x})\right) \,\mathrm {mod}\ q\in (\mathbb {F}_{q}[\mathbf {x}]_E)^n. \end{aligned}$$

  • 5. Choose an affine isomorphism T on $\mathbb {F}_{q}^n$.

  • 6. Compute $F(\mathbf {x})=T\circ G(\mathbf {x})\in (\mathbb {F}_{q}[\mathbf {x}]_E)^n$.

  The secret key is $\varPhi (\mathbf {x}),\varPsi (\mathbf {x}),\ \{r_1,\ldots ,r_n\},\ T$, and the public key is $F(\mathbf {x})$.

• Encryption Algorithm Let $\mathbf {m}\in I_L^{\,n}$ be a plaintext.

  • 1. Compute $\mathbf {c}=F(\mathbf {m})\in \mathbb {F}_{q}^{\,n}$.

  Then, $\mathbf {c}$ is the ciphertext corresponding to $\mathbf {m}$.

• Decryption Algorithm Let $\mathbf {c}\in \mathbb {F}_{q}^{\,n}$ be a ciphertext.

  • 1. Compute $\mathbf {c}'=(c'_1,\ldots ,c'_n)=T^{-1}(\mathbf {c})$.

  • 2. For all $i=1,\ldots ,n$, find $\tilde{b}_i\in \{0,\pm 1,\pm 2,\ldots ,\pm M_{\varPsi }\}$ satisfying $|\mathrm {lift}_q(c'_i-r_i\tilde{b}_i)|<M_{\varPhi }$ and compute $\tilde{a}_i=\mathrm {lift}_q(c'_i-r_i\tilde{b}_i)\in \mathbb {Z}$.

  • 3. Solve the nonlinear equation system with a box constraint $I_L^{\,n}$,

    $$\begin{aligned} \varPhi (\mathbf {x})=(\tilde{a}_1,\ldots ,\tilde{a}_n),\ \varPsi (\mathbf {x})=(\tilde{b}_1,\ldots ,\tilde{b}_n). \end{aligned}$$

    The solution is denoted by $\mathbf {m}'\in I_L^{\,n}$.

  Then, $\mathbf {m}'$ coincides with the plaintext $\mathbf {m}$.

4 Solving Constrained Nonlinear System with Integer Coefficients

In this section, we consider methods for solving the constrained nonlinear equation system with integer coefficients,

$$\begin{aligned} \varPhi (\mathbf {x})=(\tilde{a}_1,\ldots ,\tilde{a}_n),\ \varPsi (\mathbf {x})=(\tilde{b}_1,\ldots ,\tilde{b}_n) \end{aligned}$$

(4)

appeared in Step 3 of the decryption algorithm. We define $H(\mathbf {x}):\mathbb {R}^n\rightarrow \mathbb {R}^{2n}$ by

$$\begin{aligned} H(\mathbf {x})=(h_1(\mathbf {x}),h_2(\mathbf {x}),\ldots ,h_{2n}(\mathbf {x}))=(\varPhi (\mathbf {x})-(\tilde{a}_1,\ldots ,\tilde{a}_n))\,\Vert \,(\varPsi (\mathbf {x})-(\tilde{b}_1,\ldots ,\tilde{b}_n)), \end{aligned}$$

then the Eq. (4) is equivalent to the equation $H(\mathbf {x})=\mathbf {0}$.

From the structure of the proposed scheme, we know the plaintext $\mathbf {m}$ is a solution of $H(\mathbf {x})=\mathbf {0}$.

Let us discuss whether there are other solutions of $H(\mathbf {x})=\mathbf {0}$ in the definition range $\mathbb {R}^n$ or not. Since the coefficients of $\varPhi (\mathbf {x}), \varPsi (\mathbf {x})$ are chosen randomly, and by Bézout’s theorem, there is a subset S of $\{1,2,\ldots ,2n\}$ of cardinality n such that the number of the rational points of the variety defined by the ideal $I_S=(h_k(\mathbf {x})\mid k\in S)\subset \mathbb {R}[\mathbf {x}]$ is less than or equal to $\prod _{k\in S}\,\mathrm {deg}\,h_{k}(\mathbf {x})$ (Bézout’s bound). $\mathbf {m}$ is one of such rational points, and the chances of existing other rational points satisfying $h_{k}(\mathbf {x})=0$ for $k\in \{1,2,\ldots ,2n\} \setminus S$ are really low. In fact, in our actual experiments of 1000 trials with different parameters presented in Table 4, we had always only obtained one rational point. Therefore, we can assume that

$$\begin{aligned} \text {the system} \,H(\mathbf {x})=\mathbf {0}\, \text {has only one solution in} \,\mathbb {R}^n. \end{aligned}$$

As explained above, if we obtain a solution of the system $H(\mathbf {x})=\mathbf {0}$ of unconstrained nonlinear equations with real coefficients, it coincides with the plaintext $\mathbf {m}$. Moreover, from the fact that $\mathbf {m}$ has integer components, if we obtain an approximate solution whose component-wise errors from $\mathbf {m}$ are within less than 0.5, its component-wise rounding to integers becomes the exact solution of the system.

To compute an approximate solution of $H(\mathbf {x})=\mathbf {0}$, we define

$$\begin{aligned} \theta (\mathbf {x})=\frac{1}{2}\Vert H(\mathbf {x})\Vert _2^{\,2}=\frac{1}{2}(h_1^2(\mathbf {x})+h_2^2(\mathbf {x})+\cdots +h_{2n}^2(\mathbf {x})), \end{aligned}$$

and consider the least square problem, i.e. to solve the optimization problem of $\theta (\mathbf {x})$. The line search method is known as a method to solve optimization problems. The line search method uses a point sequence $\mathbf {x}_1,\mathbf {x}_2,\ldots (\in \mathbb {R}^n)$ with a cluster point. $\mathbf {x}_{k+1}$ is given by the previous term $\mathbf {x}_k$ as

$$\begin{aligned} \mathbf {x}_{k+1}=\mathbf {x}_k+t_k\mathbf {d}_k, \end{aligned}$$

where $\mathbf {d}_k(\in \mathbb {R}^n)$ is called a search direction, and $t_k(\in \mathbb {R})$ is called a step size. $\mathbf {d}_k$ is chosen to be a decent direction, i.e. $\mathbf {d}_k$ satisfies

$$\begin{aligned} (\nabla \theta (\mathbf {x}_k)\,\mathbf {d}_k^{\mathsf {T}})\,=\,H(\mathbf {x}_k) J_H(\mathbf {x}_k)\,\mathbf {d}_k^{\mathsf {T}}<0. \end{aligned}$$

Here, $J_H(\mathbf {x}_k)$ is the Jacobi matrix $\left( \frac{\partial }{\partial x_j}h_i(\mathbf {x})\right) (\in \mathbb {R}^{2n\times n})$ of $H(\mathbf {x})$. $t_k\in (0,1)$ is chosen to satisfy the Armijo condition: for an $\alpha \in (0,1)$,

$$\begin{aligned} \theta (\mathbf {x}_k+t_k\mathbf {d}_k)-\theta (\mathbf {x}_k)\le \alpha t_k H(\mathbf {x}_k) J_H(\mathbf {x}_k)\,\mathbf {d}_k^{\mathsf {T}}. \end{aligned}$$

Then, the sequence $\{\mathbf {x}_k\}$ is globally convergent to a cluster point $\mathbf {x}^*$, and $\mathbf {x}^*$ becomes a stationary point, i.e. it satisfies

$$\begin{aligned} \nabla \theta (\mathbf {x}^*)=H(\mathbf {x}^*)J_H(\mathbf {x}^*)=\mathbf {0}. \end{aligned}$$

(5)

We may assume that the rank of $J_H(\mathbf {x}^*)$ is n, hence the dimension of $\mathrm {ker}\,J_H(\mathbf {x}^*)$ is n. (5) implies that $H(\mathbf {x}^*)\in \mathrm {ker}\,J_H(\mathbf {x}^*)$, but does not mean $H(\mathbf {x}^*)=\mathbf {0}$ generally. Accordingly, by reselect a sequence $\{\mathbf {x}_k\}$ over and over again until $H(\mathbf {x}^*)=\mathbf {0}$ is satisfied, we eventually obtain a (approximate) solution of $H(\mathbf {x})=\mathbf {0}$.

Several methods for selecting a search direction have been proposed, and the difference of those methods results in different properties of convergence and efficiency of solving. In this paper, the following 4 line search methods are considered.

• 1. Steepest decent method

• 2. Levenberg-Marquardt method

• 3. Quasi-Newton method

• 4. Newton method (for optimization problems)

In the steepest decent method, the search direction is chosen by $\mathbf {d}_k=-\nabla \theta (\mathbf {x}_k)$, and in the Levenberg-Marquardt Method,

$$\begin{aligned} \mathbf {d}_k=-\nabla \theta (\mathbf {x}_k)(J_H(\mathbf {x}_k)^{\mathsf {T}}J_H(\mathbf {x}_k)+w_kI_{n})^{-1}. \end{aligned}$$

Here, $w_1,w_2,\ldots$ are a sequence of non-negative real numbers converging to 0, and have the effect of making $J_H(\mathbf {x}_k)^{\mathsf {T}}J_H(\mathbf {x}_k)+w_kI_{n}$ a positive definite symmetric matrix. Now, because $J_H(\mathbf {x}_k)$ is a (2n, n)-matrix, we can assume that $J_H(\mathbf {x}_k)^{\mathsf {T}}J_H(\mathbf {x}_k)$ is always a positive definite symmetric matrix, therefore we can take $w_k=0$. In the quasi-Newton method, a sequence $\{B_k\}$ of matrices are used,

$$\begin{aligned} \mathbf {d}_k=-\nabla \theta (\mathbf {x}_k)B_k. \end{aligned}$$

$B_{k+1}$ is defined by the BFGS update,

$$\begin{aligned} B_{k+1}=B_k-\frac{\mathbf {s}_k^{\mathsf {T}} \mathbf {y}_kB_k+(\mathbf {y}_kB_k)^{\mathsf {T}}\mathbf {s}_k}{(\mathbf {s}_k, \mathbf {y}_k)} +\left( 1+\frac{(\mathbf {y}_k,B_k\mathbf {y}_k)}{(\mathbf {s}_k, \mathbf {y}_k)}\right) \frac{\mathbf {s}_k^{\mathsf {T}}\mathbf {s}_k}{(\mathbf {s}_k, \mathbf {y}_k)}. \end{aligned}$$

Here, $\mathbf {s}_k=\mathbf {x}_{k+1}-\mathbf {x}_k,\ \mathbf {y}_k=\nabla \theta (\mathbf {x}_{k+1})-\nabla \theta (\mathbf {x}_{k})$, and $(\,\cdot ,\,\cdot \,)$ denotes the usual inner form. $B_1$ is defined by $(J_H(\mathbf {x}_1)^{\mathsf {T}}J_H(\mathbf {x}_1))^{-1}$. In the Newton method (for optimization problems), we take $\mathbf {d}_k=-\nabla \theta (\mathbf {x}_k)(\nabla ^2\theta (\mathbf {x}_k))^{-1}$ where $\nabla ^2\theta (\mathbf {x})$ is the Hessian matrix of $\theta (\mathbf {x})$.

For the steepest decent method, the Levenberg-Marquardt method and quasi-Newton method, it is known that $\mathbf {d}_k$ is a decent direction. For the Newton method, generally, $\mathbf {d}_k$ is not a decent direction, but we have checked that it is a decent direction in our experiment. Table 2 compares the performance of 4 line search methods. $H(\mathbf {x})$ consists of quadratic polynomials and all solutions are contained in $[-5,5]\cap \mathbb {Z}=I_{11}$. We experimented 1,000 times for $n=30,40,50$ with each method. In the table, “time” represents the average time (unit: milli seconds) of solving, “$\sharp$ seq” represents the average number of sequences up to reaching the solution $\mathbf {m}$, and “$\sharp$ terms” represents the average number of the terms up to reaching a stationary point $\mathbf {x}^*$ for a sequence. Table 2 shows remarkable feature of each method, and overall, the most efficient solving algorithm is the Levenberg-Marquardt method, so that we adopted the Levenberg-Marquardt method in the decryption of the proposed scheme. The algorithm of the Levenberg-Marquardt method is as follows. $\Vert \,\cdot \,\Vert _{\infty }$ represents the maximum of the absolute values of the components of a vector, and (2-6) judges whether a sequence gets close enough to a stationary point or not. $\text {round}(\mathbf {x}_0)$ represents the component-wise rounding $\mathbf {x}_0$ to integers.

Table 2. Comparison of algorithms for solving $H(\mathbf {x})=\mathbf {0}$

Levenberg-Marquardt Method

[Input]   $H(\mathbf {x})$, an odd number $L\in \mathbb {Z}_{>0},\ \alpha ,\beta ,\gamma \in (0,1)$.

[Output] A (constrained) solution of $H(\mathbf {x})=\mathbf {0}$ with integer components.

• 1. Choose $\mathbf {x}_0\in [-(L-1)/2,(L-1)/2]^{\,n}$ in the range of real numbers randomly.

• 2. Repeat (2-1)–(2-6):

  • 2-1. Compute $\mathbf {e}=-H(\mathbf {x}_0)J_H(\mathbf {x}_0)$.

  • 2-2. Compute $S=J_H(\mathbf {x}_0)^{\mathsf {T}}J_H(\mathbf {x}_0)$.

  • 2-3. Solve the linear equation $\mathbf {x}\, S=\mathbf {e}$, its solution is denoted by $\mathbf {d}_0$.

  • 2-4. Compute the minimal non-negative integer l satisfying the following condition, and set $t_0=\beta ^l$:

    $$\begin{aligned} \theta (\mathbf {x}_0+\beta ^l\mathbf {d}_0)-\theta (\mathbf {x}_0)\le -\alpha \beta ^l\mathbf {e}\,\mathbf {d}_0^{\mathsf {T}}. \end{aligned}$$

  • 2-5.$\mathbf {x}_0\leftarrow \mathbf {x}_0+t_0\mathbf {d}_0$.

  • 2-6. If $\Vert t_0\mathbf {d}_0\Vert _{\infty }<\gamma$ then finish the loop, and move to 3.

• 3.$\tilde{\mathbf {x}}_0\leftarrow \text {round}(\mathbf {x}_0)$.

• 4. If $H(\tilde{\mathbf {x}}_0)=\mathbf {0}$ then output $\tilde{\mathbf {x}}_0$, otherwise go back to 1.

The algorithms of the steepest decent method, quasi-Newton method and Newton method are described in the appendix.

Remark 1

The 4 methods explained as above have the only difference of taking the search direction $\mathbf {d}_k$, and other parts is common. In these methods, for any $\mathbf {x}_k$, $H(\mathbf {x}_k+\mathbf {d})$ is approximated by quadratic polynomials

$$\begin{aligned} m_{\mathbf {x}_k}(\mathbf {d})=H(\mathbf {x}_0)+\mathbf {d}\,\nabla H(\mathbf {x}_k)+\frac{1}{2}\mathbf {d}\,A_{k}\mathbf {d}^{\mathsf {T}}\ \ \ (A_k\in \mathbb {R}^{n\times n}), \end{aligned}$$

$\mathbf {d}_k$ is chosen by the solution $\mathbf {d}$ of the (unconstrained) optimization problem of $m_{\mathbf {x}_k}(\mathbf {d})$. For the steepest decent method, $A_k=I_n$ is taken, for the Levenberg-Marquardt method, $A_k=J_H(\mathbf {x}_0)^{\mathsf {T}}J_H(\mathbf {x}_0)$, for the quasi-Newton method, $A_k=B_k^{-1}$, for Newton method, $A_k=\nabla ^2\theta (\mathbf {x}_k)$ are taken, respectively.

5 Security Analysis of the Proposed Scheme

The security of the proposed scheme is mainly based on the difficulty of solving the constrained MP problem.

Constrained MP problem: For positive integers m, n, L, let $\mathcal {F}(\mathbf {x})$ be a polynomial system which consists of m polynomials over $\mathbb {F}_{q}$ in variables $\mathbf {x}=(x_1,\ldots ,x_n)$. Then, find $\mathbf {x}_0\in I_L^{\,n}$ such that $\mathcal {F}(\mathbf {x}_0)=\mathbf {0}$.

In this section, fixing a ciphertext $\mathbf {c}\in \mathbb {F}_{q}^n$, we consider a polynomial system $\mathcal {F}(\mathbf {x})=F(\mathbf {x})-\mathbf {c}$ for a public key $F(\mathbf {x})$ constructed by the proposed scheme. With this $\mathcal {F}(\mathbf {x})$, by solving the constrained MP problem, the plaintext corresponding to $\mathbf {c}$ is obtained.

5.1 Constrained MP Problem

For $\mathcal {F}(\mathbf {x})=(\hat{f}_1(\mathbf {x}),\ldots ,\hat{f}_n(\mathbf {x}))$, each component $\hat{f}_i(\mathbf {x})$ has $s=\sharp E$ monomials. (If E does not include the constant term, $s=\sharp E+1$.) Determining an order of these monomials, a vector $\mathbf {a}_i\in \mathbb {Z}^{s}$ is defined as the vector of coefficients lifted to integers from the coefficients of $\hat{f}_i(\mathbf {x})$. The q-ary lattice generated by $\mathbf {a}_1,\ldots ,\mathbf {a}_n$ is denoted by $\mathcal {A}$. We assume that by solving the Shortest Independent Vector Problem (SIVP) for $\mathcal {A}$, n linearly independent short vectors $\mathbf {b}_1,\ldots ,\mathbf {b}_n\in \mathbb {Z}^{s}$ in $\mathcal {A}$ are obtained. The polynomial over $\mathbb {Z}$ corresponding to the vector $\mathbf {b}_i$ is denoted by $\hat{h}_i(\mathbf {x})$, and let $\mathcal {H}(\mathbf {x})=(\hat{h}_1(\mathbf {x}),\ldots ,\hat{h}_n(\mathbf {x}))$. Then, the problem solving the equation $\mathcal {F}(\mathbf {x})=\mathbf {0}$ is reduced to the problem solving the equation $\mathcal {H}(\mathbf {x})\equiv \mathbf {0}\ \mathrm {mod}\ q$. Here, let us assume that for a solution $\mathbf {x}_0$ of the constrained MP problem,

$$\begin{aligned} |\hat{h}_i(\mathbf {x}_0)|<\frac{q-1}{2}\ \ \ (i=1,\ldots ,n) \end{aligned}$$

(6)

is satisfied. Beware that $\mathbf {x}_0$ is not only a solution of $\mathcal {H}(\mathbf {x})\equiv \mathbf {0}\ \mathrm {mod}\ q$, but also a solution of the equation over $\mathbb {Z}$, $\mathcal {H}(\mathbf {x})=0$. Therefore, $\mathbf {x}_0$ can be obtained by solving the equation over $\mathbb {Z}$. Solving the equation $\mathcal {H}(\mathbf {x})=0$ is efficiently carried out by combining techniques to solve approximately nonlinear equations over the real numbers with the fact that $\mathbf {x}_0$ has integer components. The approximate solution of $\mathcal {H}(\mathbf {x})=0$ can be obtained by, for example, the solving method of the (constrained) optimization problem (least square problem) of the function $\Vert \mathcal {H}(\mathbf {x})\Vert _2^{\,2}$ where $\Vert \cdot \Vert _2$ is the usual Euclid norm [5, 25].

First, let us consider the possibility that $\mathcal {H}(\mathbf {x})$ satisfies (6) for a general constrained MP problem. Since $\mathrm {vol}(\mathcal {A})=q^{s-n}$, by the Gaussian heuristic [24], it is expected that

$$\begin{aligned} \Vert \mathbf {b}_i\Vert _2\approx \sqrt{\frac{s}{2\pi e}}q^{1-\frac{n}{s}}\ \ \ (i=1,\ldots ,n). \end{aligned}$$

Here, e is Napier’s constant. Simply, assuming that $\sqrt{\frac{s}{2\pi e}}$ components of $\mathbf {b}_i$ are close to q, the probability satisfying (6) is negligible if s is sufficiently large.

Next, consider the case of the constrained MP problem obtained by the proposed scheme. $\varPhi (\mathbf {x}),\varPsi (\mathbf {x})$ have small coefficients, but, the distribution of $r_1,\ldots ,r_n$ is close to the uniformly distribution on $[2M_{\varPhi },q-2M_{\varPhi }-1]$. Therefore, taking account of the definition of $G(\mathbf {x})$, any coefficient of components of $G(\mathbf {x})$ behaves as chosen randomly in $[M_{\varPhi },q-M_{\varPhi }-1]$. Since $M_{\varPhi }$ is small enough compared to q, similarly for general constrained MP problem, the probability satisfying (6) must be negligible. The above argument implies that the part $\varPsi _R(\mathbf {x})$ is indispensable in the definition of $G(\mathbf {x})$.

5.2 Attack Against Inhomogeneous SIS Problem

For $\mathbf {e}\in E$, $v_{\mathbf {e}}$ denotes the row vector enumerating the coefficients with respect to $\mathbf {x}^{\mathbf {e}}$ of components of $F(\mathbf {x})=(f_1(\mathbf {x}),\ldots ,f_n(\mathbf {x}))$. Taking an order on E, a matrix $A\in \mathbb {F}_{q}^{\,n\times \sharp E}$ is defined by the matrix enumerating the column vector $v_{\mathbf {e}}\ (\mathbf {e}\in E)$. Then, for a solution $\mathbf {x}_0\in I_L^{\,n}$ of the constrained MP problem, $\mathbf {w}_0=(\mathbf {x}_0^{\mathbf {e}})_{\mathbf {e}\in E}\in \mathbb {Z}^{\sharp E}$ is a solution of the linear equation,

$$\begin{aligned} A\mathbf {w}=\mathbf {c}, \end{aligned}$$

(7)

and $\mathbf {w}_0$ has a considerably smaller Euclid norm among solutions of the linear equation. This means that $\mathbf {w}_0$ is a solution of the inhomogeneous SIS problem obtained from (7). Therefore, we can consider the attack as follows: First, we gather solutions of the inhomogeneous SIS problem obtained from (7). Next, we search $\mathbf {w}_0$ in the set of the solutions. The inhomogeneous SIS problem is changed to the SVP for a lattice $\mathcal {B}$ of dimension $\sharp E+1\ (\text {or}\ \sharp E)$, where the co-volume of $\mathcal {B}$, $\mathrm {vol}(\mathcal {B})=q^n$.

Theorem 1

([15]). For an m-dimensional lattice $\mathcal {L}$, we define

$$\begin{aligned} N_{\mathcal {L}}(r)=\sharp \{v\in \mathcal {L}\,|\,\Vert v\Vert _2\le r\}. \end{aligned}$$

If $m\ge 5$, then we have

$$\begin{aligned} N_{\mathcal {L}}(r)=\frac{V_m}{\mathrm {vol}(\mathcal {L})}r^m+\mathcal {O}(r^{m-2}). \end{aligned}$$

Here, $V_m$ is the volume of the unit sphere of $\mathbb {R}^m$.

From this theorem, the number of elements of $\mathcal {B}$ whose Euclid norm is almost same as r is close to

$$\begin{aligned} \frac{d}{dr}\left( \frac{V_m}{\mathrm {vol}(\mathcal {L})}r^m\right) \cdot 1=\frac{m\,V_m}{\mathrm {vol}(\mathcal {L})}r^{m-1}. \end{aligned}$$

Going back to our setting, the number of elements of $\mathcal {B}$ whose Euclid norm is almost same as $\Vert \mathbf {w}_0\Vert _2$ is about

$$\begin{aligned} \frac{b\, V_b\, \Vert \mathbf {w}_0\Vert _2^{b-1}}{q^n}=\frac{\pi ^{\frac{b}{2}}\,b\,\Vert \mathbf {w}_0\Vert _2^{b-1}}{\Gamma (\frac{b}{2}+1)\,q^n} \approx \left( \frac{2\pi e}{b}\right) ^{\frac{b}{2}}\frac{b\,\Vert \mathbf {w}_0\Vert _2^{b-1}}{\sqrt{b\pi }\,q^n}\ \ \ (b=\mathrm {dim}\mathcal {B}=\sharp E+1\ \text {or}\ \sharp E). \end{aligned}$$

Since the solution of the constrained MP problem is unique, the complexity of the attack is the same as this value. Moreover, if a large scale quantum computer is available, the complexity is the 1/2-th power of this value by the Grover’s algorithm.

5.3 Key Recovery Attack

Once the linear transformation part of the affine transformation T is known, $G(\mathbf {x})$ is also known from the public key, and $r_1,\ldots ,r_n,$ $\varPhi (\mathbf {x}),\varPsi (\mathbf {x})$ can be computed easily from $G(\mathbf {x})$, thus, the secret information which is necessary for decryption is obtained entirely. Therefore, let us consider an attack discovering the linear transformation part $T_1$ of T.

An adversary who knows $r_j$ for some j can compute the j-th row vector of $T_1^{-1}$ by the following procedure.

• 1. Choose an integer t such that $n<t\le \sharp E$, and choose a (ordered) subset M of E with cardinality t.

• 2. For $F(\mathbf {x})=(f_1(\mathbf {x}),\ldots ,f_n(\mathbf {x}))$ and $i=1,\ldots ,n$, compute a vector $\mathbf {a}_i\in \mathbb {Z}^t$ of coefficients lifted to integers from coefficients of $f_i(\mathbf {x})$ with respect to M. The q-ary lattice of $\mathbb {Z}^t$ generated by $\mathbf {a}_1,\ldots ,\mathbf {a}_n$ is denoted by $\mathcal {A}$.

• 3. Choose $\mathbf {b}=(b_1,\ldots ,b_s)\in I_{L_G}^{\,t}$ randomly.

• 4. Compute the vector $\mathbf {a}$ in $\mathcal {A}$ closest to $r_j\mathbf {b}$. If $\Vert r_j\mathbf {b}-\mathbf {a}\Vert _{\infty }<L/2$ is satisfied, output the coefficient vector $(c_1,\ldots ,c_n)$ of the linear combination $\mathbf {a}=c_1\mathbf {a}_1+\cdots +c_n\mathbf {a}_n$, and terminate. Otherwise, go back to Step 3.

Since $\mathbf {b}$ satisfying the inequality in Step 4 exists uniquely, even if the cost for searching the closest vector is estimated as 1, the complexity of the above algorithm becomes $\mathcal {O}(L_G^{\,t})$, which in particular, is larger than $\mathcal {O}(L_G^{\,n})$.

Moreover, the above attack can exchange the roll of $\varPhi (\mathbf {x})$ and $\varPsi (\mathbf {x})$. Namely, if the above algorithm is changed by $r_i \rightarrow 1/r_i$, it works as an attack. The complexity of this attack is also $\mathcal {O}(L_G^{\,t})(>\mathcal {O}(L_G^{\,n}))$. If the Grover’s algorithm is available, the complexity is $\mathcal {O}(L_G^{\,\frac{t}{2}})(>\mathcal {O}(L_G^{\,\frac{n}{2}}))$.

5.4 Exhaustive Search

For a ciphertext $\mathbf {c}$, the complexity of finding the solution of $F(\mathbf {x})=\mathbf {c}$ by the exhaustive search is $\mathcal {O}(L^n)$. In the case of using the Grover’s algorithm, the complexity is $\mathcal {O}(L^{\frac{n}{2}})$.

5.5 Algebraic Attack

The algebraic attack uses algebraic equation solver like XL [36] and Gröbner basis technique [12, 13] for solving the usual MP problem. The complexity of the algebraic attack is estimated by the complexity of the hybrid approach [1] of computing a Gröbner basis and exhaustive search. In the process of exhaustive search in [1], all elements in a finite field are substituted for several variables, but, in the proposed scheme, the finite field must be changed into $I_L$. A solution $\mathbf {x}_0$ of $\mathcal {F}=(\hat{f}_1(\mathbf {x}),\ldots ,\hat{f}_n(\mathbf {x}))=\mathbf {0}$ in $I_L^{\,n}$ is also a zero point of

$$\begin{aligned} \hat{g}_j(\mathbf {x})=\prod _{-\frac{L-1}{2}\le a\le \frac{L-1}{2}}(x_j-a)\ \ \ \ \ (j=1,2,\ldots ,n). \end{aligned}$$

(8)

Therefore, the ideal we should consider is

$$\begin{aligned} I=\langle \hat{f}_1(\mathbf {x}),\ldots ,\hat{f}_n(\mathbf {x}),\hat{g}_1(\mathbf {x}),\ldots , \hat{g}_n(\mathbf {x})\rangle . \end{aligned}$$

For $k=0,1,\ldots ,n$, we randomly choose $(v_{n-k+1},v_{n-k+2},\ldots ,v_n)\in {I_p}^k$. We denote the polynomial system in $n-k$ variables obtained by substituting $(x_{n-k+1},\ldots ,x_n)=(v_{n-k+1},\ldots ,v_n)$ for $\mathcal {F}(\mathbf {x})$ by $\mathcal {F}_{k}(\mathbf {x}^{(k)})$. Here, $\mathbf {x}^{(k)}=(x_1,\ldots ,x_{n-k})$. Note that $\mathcal {F}_{0}(\mathbf {x}^{(0)})$ is the same as $\mathcal {F}(\mathbf {x})$.

For $\mathcal {F}_{k}(\mathbf {x}^{(k)})=(\hat{f}_1(\mathbf {x}^{(k)}),\ldots ,\hat{f}_n(\mathbf {x}^{(k)}))$, the homogeneous part of $\hat{f}_i(\mathbf {x}^{(k)})$ of the maximal degree $(i=1,\ldots ,n)$ is denoted by $\hat{f}^h_i(\mathbf {x}^{(k)})$, and the homogeneous ideal $J^{(k)}$ of $\mathbb {F}_{q}[\mathbf {x}^{(k)}]$ is defined by

$$\begin{aligned} J^{(k)}=\langle \hat{f}^h_1(\mathbf {x}^{(k)}),\ldots ,\hat{f}^h_n(\mathbf {x}^{(k)})\rangle . \end{aligned}$$

For $d\ge 0$, let $\mathbb {F}_{q}[\mathbf {x}^{(k)}]_d$ denote the subspace of $\mathbb {F}_{q}[\mathbf {x}^{(k)}]$ consisting of homogeneous polynomials of degree d, and $J^{(k)}_d=J^{(k)}\cap \mathbb {F}_{q}[\mathbf {x}^{(k)}]_d$. The Hilbert series of the quotient ring $\mathbb {F}_{q}[\mathbf {x}^{(k)}]/J^{(k)}$ is defined by

$$\begin{aligned} \mathrm {HS}_{\mathbb {F}_{q}[\mathbf {x}^{(k)}]/J^{(k)}}(t)=\sum _{d=0}^{\infty }\text {dim}_{\mathbb {F}_{q}}(\mathbb {F}_{q}[\mathbf {x}^{(k)}]_d/J^{(k)}_d)\,t^d\in \mathbb {Z}[[t]]. \end{aligned}$$

If the Krull-dimension of $J^{(k)}$ is zero, $\mathrm {HS}_{\mathbb {F}_{q}[\mathbf {x}^{(k)}]/J^{(k)}}(t)$ becomes a polynomial. Then, the degree of regularity, $d_{\text {reg}}(k)$ is defined by $d_{\text {reg}}(k)=\mathrm {deg}(\mathrm {HS}_{\mathbb {F}_{q}[\mathbf {x}^{(k)}]/J^{(k)}}(t))+1$. For any $S(t)\in \mathbb {Z}[[t]]$, the power series obtained by truncating S(t) at its first non positive coefficient is denoted by $[S(t)]_+\in \mathbb {Z}_{>0}[[t]]$. If

$$\begin{aligned} \mathrm {HS}_{\mathbb {F}_{q}[\mathbf {x}^{(k)}]/J^{(k)}}(t)=\left[ \frac{(1-t^L)^{n-k}\prod _{i=1}^n(1-t^{d_i})}{(1-t)^{n-k}}\right] _+ \end{aligned}$$

(9)

is satisfied, it is said that $\mathcal {F}_{k}(\mathbf {x}^{(k)})$ is semi-regular. Here, $d_i$ is the total degree of $\hat{f}_i(\mathbf {x})$.

Remark 2

Taking the result in [35] into consideration, for most of random systems, the right hand side of (9) may seem to be equal to

$$\begin{aligned} \left[ \frac{(1-t^L)^{n-k}\cdot \prod _{i=1}^n(1-t^{d_i})}{(1-t)^{n-k}\cdot (1-t^{d_iL})^n}\right] _+, \end{aligned}$$

but, actually, the part $(1-t^{d_iL})^n$ is not needed. This is because, different from the case of the usual MP problem considered in [35], in the constrained MP problem, $f_i(\mathbf {x})^L-f_i(\mathbf {x})=0\ (i=1,2,\ldots ,n)$ (or this analogue) does not hold.

The complexity of the Gröbner basis computation for $J^{(k)}$ is described by

$$\begin{aligned} \mathcal {O}\left( \left( \begin{array}{c} n-k+d_{\text {reg}}(k)-1\\ d_{\text {reg}}(k) \end{array}\right) ^{\omega }\right) . \end{aligned}$$

(10)

Here, $2\le \omega \le 3$ is the linear algebra constant of solving a linear system. From (10), the complexity of the hybrid attack is described as follows [1]:

$$\begin{aligned} \underset{\,0\le k\le n}{\mathrm {min}}\,\mathcal {O}\left( L^k\left( \begin{array}{c} n-k+d_{\text {reg}}(k)-1\\ d_{\text {reg}}(k) \end{array}\right) ^{\omega }\right) . \end{aligned}$$

(11)

If the Grover’s algorithm is used for searching elements for substitution, the complexity is changed to

$$\begin{aligned} \underset{\,0\le k\le n}{\mathrm {min}}\,\mathcal {O}\left( L^{\frac{k}{2}}\left( \begin{array}{c} n-k+d_{\text {reg}}(k)-1\\ d_{\text {reg}}(k) \end{array}\right) ^{\omega }\right) . \end{aligned}$$

(12)

From randomness of the coefficients of $\varPhi (\mathbf {x}),\varPsi (\mathbf {x})$, and taking Fröberg conjecture [14] into consideration, it is expected that $J^{(k)}$ is semi-regular. In fact, for $n=3,4,\ldots ,15$, we confirmed that $J^{(k)}$ is semi-regular experimentally. Our experiment used Magma. Based on the experiment result, we assume that any $\mathcal {F}_{k}(\mathbf {x}^{(k)})$ is semi-regular (in particular, for estimation of security parameters).

Remark 3

In the case of that $\mathcal {F}_{k}(\mathbf {x}^{(k)})$ is semi-regular, the degree of regularity can be computed by using (9). Moreover, in this case, it is expected that the first fall degree $d_{\mathrm {FF}}(k)$ [10] coincides with the degree of regularity. In general, the complexity of the Gröbner basis computation for $J^{(k)}$ is also expressed by

$$\begin{aligned} \mathcal {O}\left( \left( \begin{array}{c} n-k+d_{\text {FF}}(k)-1\\ d_{\text {FF}}(k) \end{array}\right) ^{\omega }\right) . \end{aligned}$$

(13)

If $d_{\mathrm {reg}}(k)=d_{\mathrm {FF}}(k)$, the complexity (13) is equal to the complexity (10). Therefore, in the estimation of security parameters, we use the complexity (11), (12) with $\omega =2$.

Remark 4

In the security analysis of the pq-method in [37], the algebraic attack does not consider the polynomial (8) as one of generators of an ideal, but, this polynomial should be considered.

6 Security Parameters and Implementation

As a set of monomials E used to design the proposed scheme, we take $E=E_{\le 2}=\{\mathbf {e}\in (\mathbb {Z}_{\ge 0})^n\mid \mathrm {deg}\,\mathbf {e}\le 2\}$. Here, $\mathrm {deg}\,(e_1,\ldots ,e_n)=\sum _{i=1}^ne_i$, i.e. $E_{\le 2}$ corresponds to the whole monomials of degree less than or equal to 2. Table 3 shows the security parameters of $(n,L,L_G)$ estimated based on the security analysis in Sect. 5. Secure parameters are estimated considering attacks on classical computers and quantum computers.

Table 3. Security parameter $(n,L,L_G)$

Tables 4 and 5 show performance result of PERN with an implementation using Intel Core i7-6700, 3.4 GHz. Our implementation used C++ programming language with g++ compiler. $|q|_2$ represents the average of the bit length of q. Key gen., enc. and dec. represent the average time of key generation, encryption and decryption (unit: milli seconds). And SK and PK represent the secret key length and public key length (unit: kilobytes). $\Vert \mathbf {w}_0\Vert _2$ represents the minimal integer of $\Vert \mathbf {w}_0\Vert _2$ appeared in the analysis in Sect. 5.2 to maintain the corresponding security level. Moreover, in Table 5, $\Vert \mathbf {w}_0\Vert _2$ is estimated considering the Grover’s algorithm.

Table 4. Performance of PERN with parameters for classical attacks)

6.1 Implementation for Higher Degrees

For non-negative integers a, b, we define $E_{a,b}=\{a\,\mathbf {e}_i+b\,\mathbf {e}_j\in (\mathbb {Z}_{\ge 0})^n\mid 1\le i,j\le n\}$ where $\mathbf {e}_i$ is the i-th fundamental vector. We implemented the PERN with $E'=E_{2,1}\sqcup E_{\le 2}$ and $E''=E_{3,1}\,\sqcup \, E_{\le 2}$ as E. The case of $E'$ uses cubic polynomials, and the case of $E''$ uses quartic polynomials. For the fixed parameter $(n,L,L_G)$, it is expected that the PERN with $E'$ or $E''$ is more secure than the PERN with $E_{\le 2}$, but whether this is true or not is a future study issue, a performance comparison of PERN for $E=2, E', E''$ under $(n, L, LG) = (65, 7, 5)$ is shown in Table 6.

Table 5. Performance of PERN (with parameters for quantum attacks)

Table 6. Comparison of PERN for $E_{\le 2}$, $E^\prime$, $E^{\prime \prime }$ ($(n,L,L_G)=(65,7,5)$)

7 Conclusion

We proposed an encryption scheme called PERN whose security was mainly based on the constrained MP problem. The proposed scheme is flexible to use multivariate polynomials of any degree in its public key. And this public key polynomial system is semi-regular, which indicates the proposed scheme is strong against the algebraic attack.

For inverting the central polynomial map during the decryption process of the proposed scheme, methods for solving nonlinear equations over the real numbers are used, which is used for the first time in MPKC. In this paper, the line search method is used as a solving method for nonlinear equations. However, for solving unconstrained nonlinear equations, there are several solving techniques such as the trust region method [7, 11, 19,20,21, 34, 38]. Moreover, the solving method for constrained nonlinear equations can be related to the decryption of the proposed scheme, and in particular, for the case of the box constraint as $I_L^{\,n}$, there are many research results [2, 3, 17, 18, 23, 28, 32, 33]. We, therefore, would like to work on efficient algorithms for solving nonlinear equations from now on to improve the decryption efficiency of the proposed scheme.

ASolving Algorithms of Nonlinear Equations Except For the Levenberg-Marquardt Method

Steepest Decent Method

[Input]   $H(\mathbf {x})$, an odd number $L\in \mathbb {Z}_{>0},\ \alpha ,\beta ,\gamma \in (0,1)$.

[Output] A (constrained) solution of $H(\mathbf {x})=\mathbf {0}$ with integer components.

• 1. Choose $\mathbf {x}_0\in [-(L-1)/2,(L-1)/2]^{\,n}$ in the range of real numbers randomly.

• 2. Repeat (2-1)–(2-4):

  • 2-1. Compute $\mathbf {d}_0=-H(\mathbf {x}_0)J_H(\mathbf {x}_0)$.

  • 2-2. Compute the minimal non-negative integer l satisfying the following condition, and set $t_0=\beta ^l$.

    $$\begin{aligned} \theta (\mathbf {x}_0+\beta ^l\mathbf {d}_0)-\theta (\mathbf {x}_0)\le -\alpha \beta ^l\Vert \mathbf {d}_0\Vert _2^{\,2}. \end{aligned}$$

  • 2-3.$\mathbf {x}_0\leftarrow \mathbf {x}_0+t_0\mathbf {d}_0$.

  • 2-4. If $\Vert t_0\mathbf {d}_0\Vert _{\infty }<\gamma$ then finish the loop, and move to 3.

• 3.$\tilde{\mathbf {x}}_0\leftarrow \text {round}(\mathbf {x}_0)$.

• 4. If $H(\tilde{\mathbf {x}}_0)=\mathbf {0}$ then output $\tilde{\mathbf {x}}_0$, otherwise go back to 1.

Quasi-Newton Method

[Input]   $H(\mathbf {x})$, an odd number $L\in \mathbb {Z}_{>0},\ \alpha ,\beta ,\gamma \in (0,1)$.

[Output] A (constrained) solution of $H(\mathbf {x})=\mathbf {0}$ with integer components.

• 1. Choose $\mathbf {x}_0\in [-(L-1)/2,(L-1)/2]^{\,n}$ in the range of real numbers randomly.

• 2. Compute $\mathbf {e}_1=-H(\mathbf {x}_0)J_H(\mathbf {x}_0)$.

• 3. Compute $B=(J_H(\mathbf {x}_0)^{\mathsf {T}}J_H(\mathbf {x}_0))^{-1}$.

• 4. Repeat (4-1)–(4-8):

  • 4-1. Compute $\mathbf {d}_0=\mathbf {e}_1\, B$.

  • 4-2. Compute the minimal non-negative integer l satisfying the following condition, and set $t_0=\beta ^l$.

    $$\begin{aligned} \theta (\mathbf {x}_0+\beta ^l\mathbf {d}_0)-\theta (\mathbf {x}_0)\le -\alpha \beta ^l\mathbf {e}_1\mathbf {d}_0^{\mathsf {T}}. \end{aligned}$$

  • 4-3.   $\mathbf {s}_0=t_0\mathbf {d}_0,\ \ \mathbf {x}_0\leftarrow \mathbf {x}_0+\mathbf {s}_0$.

  • 4-4. If $\Vert \mathbf {s}_0\Vert _{\infty }<\gamma$ then finish the loop, and move to 5.

  • 4-5.   $\mathbf {e}_2\leftarrow \mathbf {e}_1.$

  • 4-6. Compute $\mathbf {e}_1=-H(\mathbf {x}_0)J_H(\mathbf {x}_0)$.

  • 4-7.   $\mathbf {y}_0=\mathbf {e}_1-\mathbf {e}_2$.

  • 4-8.   $B\leftarrow B-\frac{\mathbf {s}_0^{\mathsf {T}}\cdot \,\mathbf {y}_0B\,+\,(\mathbf {y}_0 B)^{\mathsf {T}}\cdot \,\mathbf {s}_0}{(\mathbf {s}_0,\mathbf {y}_0)} +\left( 1+\frac{(\mathbf {y}_0, B \mathbf {y}_0)}{(\mathbf {s}_0,\mathbf {y}_0)}\right) \frac{\mathbf {s}_0^{\mathsf {T}}\cdot \, \mathbf {s}_0}{(\mathbf {s}_0,\mathbf {y}_0)}$.

• 5.$\tilde{\mathbf {x}}_0\leftarrow \text {round}(\mathbf {x}_0)$.

• 6. If $H(\tilde{\mathbf {x}}_0)=\mathbf {0}$ then output $\tilde{\mathbf {x}}_0$, otherwise go back to 1.

Newton Method

[Input]   $H(\mathbf {x})$, an odd number $L\in \mathbb {Z}_{>0},\ \alpha ,\beta ,\gamma \in (0,1)$.

[Output] A (constrained) solution of $H(\mathbf {x})=\mathbf {0}$ with integer components.

• 1. Choose $\mathbf {x}_0\in [-(L-1)/2,(L-1)/2]^{\,n}$ in the range of real numbers randomly.

• 2. Repeat (2-1)–(2-6):

  • 2-1. Compute $\mathbf {e}=-H(\mathbf {x}_0)J_H(\mathbf {x}_0)$.

  • 2-2. Compute the Hessian matrix $S=\nabla ^2\theta (\mathbf {x}_0)$.

  • 2-3. Solve the linear equation $\mathbf {x}\, S=\mathbf {e}$ in the range of real numbers, its solution is denoted by $\mathbf {d}_0$.

  • 2-4. Compute the minimal non-negative integer l satisfying the following condition, and set $t_0=\beta ^l$.

    $$\begin{aligned} \theta (\mathbf {x}_0+\beta ^l\mathbf {d}_0)-\theta (\mathbf {x}_0)\le -\alpha \beta ^l\mathbf {e}\,\mathbf {d}_0^{\mathsf {T}}. \end{aligned}$$

  • 2-5.$\mathbf {x}_0\leftarrow \mathbf {x}_0+t_0\mathbf {d}_0$.

  • 2-6. If $\Vert t_0\mathbf {d}_0\Vert _{\infty }<\gamma$ then finish the loop, and move to 3.

• 3.$\tilde{\mathbf {x}}_0\leftarrow \text {round}(\mathbf {x}_0)$.

• 4. If $H(\tilde{\mathbf {x}}_0)=\mathbf {0}$ then output $\tilde{\mathbf {x}}_0$, otherwise go back to 1.