# Sieve Method for Polynomial Linear Equivalence

Authors: Baocang Wang; Yupu Hu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We consider the polynomial linear equivalence (PLE) problem arising from the multivariate public key cryptography, which is defined as to find an invertible linear transformationℒ satisfying 𝒫=𝒮∘ℒ for given nonlinear polynomial maps 𝒫 and 𝒮 over a finite field 𝔽q. Some cryptographic and algebraic properties of PLE are discussed, and from the properties we derive three sieves called multiplicative, differential, and additive sieves. By combining the three sieves, we propose a sieve method for the PLE problem. As an application of our sieve method, we show that it is infeasible to construct public key encryption schemes from the PLE problem.


---

## Body

## 1. Introduction

With the rapid development of information technology, privacy and authentication have become two important issues that we must resolve in communication networks. Public key cryptography is undoubtedly one of the most important tools to resolve both problems in the area of information and network security engineering. Tremendous efforts had been made to achieve more practical and efficient public key ciphers in the cryptographic literature [1]. However, we should note that only a small number of them survived the serious security scrutiny, amongst which are the two widelyused cryptosystems RSA based on the integer factorization problem [1] and ECC based on the discrete logarithm problem on elliptic curves over finite fields [1, 2]. However, there exist polynomial-time algorithms for factoring large integers and solving the discrete logarithm problems on any finite cyclic group [3, 4]. Therefore, RSA and ECC are at the risk of being totally broken by quantum algorithms if practical quantum computing devices are available. Based on the considerations, cryptographers began to construct some alternative postquantum (i.e., quantum-resistant) public key cryptosystems from other mathematically intractable problems, especially those proven NP-complete or NP-hard problems.Multivariate public key cryptography (MPKC) is an important kind of postquantum public key ciphers [5]. The security of MPKC resides in the proven fact that it is NP-hard to solve a random system of nonlinear equations over finite fields [6]. MPKC was once considered very attractive and interesting also due to its high speed in key generation, encryption, and decryption, easy implementation on both hardware and software, and its simple mathematical description [5]. In a multivariate public key cryptosystem, we first define a nonlinear easy-to-invert map 𝒮 called central map, then we randomly choose two invertible affine transformations ℒ1 and ℒ2, and finally we publish the nonlinear map 𝒫=ℒ2∘𝒮∘ℒ1 as the public key and keep ℒ1, ℒ2, and 𝒮 as the secret key. Sometimes the central map 𝒮 may have a very special structure, which makes it useless to keep the central map 𝒮 secret. One important problem in MPKC is the problem of isomorphism of polynomials (IP) [7–15]; namely, given nonlinear maps 𝒮 and 𝒫, find two invertible linear transformations ℒ1 and ℒ2 such that 𝒫=ℒ2∘𝒮∘ℒ1. The IP problem lies at the core of MPKC in which many multivariate cryptosystems were constructed based on the assumed intractability of IP problem [16–22]. The IP problem is widely believed as an intractable problem, and known algorithms for the IP problem achieve exponential complexity [7–15].In the IP problem, ifℒ2 is known or equal to the identity transformation, the IP problem turns out to be the isomorphism of polynomials with one secret (IP1s) problem [7, 8, 12, 13, 15, 23–25], which had been used in MPKC [7, 17, 26–28]. The IP1s problem was shown to be at least as difficult as the graph isomorphism problem [8, 29]. The graph isomorphism problem had been extensively studied for about half century, and no efficient algorithm was known for it, so the IP1s problem was also widely believed to be an intractability problem. When we restrict the invertible affine transformation ℒ1 to be a linear one, the special IP1s problem was renamed as polynomial linear equivalence (PLE) problem in [24]. In [24], it was shown that the PLE problem is not a restriction on IP1s, and in fact PLE and IP1s are polynomial-time equivalent. In [23], an algorithm was developed to solve the IP1s problem used in the construction of the identification scheme in [7], and the algorithm breaks some challenges of the scheme in [7]. In [24], the differential properties of PLE were fully explored to derive an algorithm for PLE, which transforms the PLE problem into a linear algebraic problem. Some other algorithms were also developed to solve the IP1s problem [12, 13, 15, 25]. These algorithms perform efficiently in some special cases of the IP1s problem.Previous results about the IP and IP1s problems were established by considering the underlying problems as mathematical problems. However, some cryptographic properties of the cryptographic IP1s problem are maybe overlooked. For example, the central map used in MPKC is required to be easy-to-invertible, and the cryptographic property may help us establish some other algorithms for solving the IP1s problem. In this paper, we utilize the cryptographic property to develop an algorithm for solving the PLE problem and hence the IP1s problem. We fully explore the multiplicative, differential, and additive cryptographic properties existing in the PLE problem. Based on the three properties, we provide a sieve algorithm for the PLE problem. Assume that the central map only has polynomially bounded pre-images; the proposed sieve algorithm is a polynomial-time algorithm. Apart from previously known algorithms based on differential analysis, Gröbner basis, exhaustive search, and linear algebraic methods, we provide a new type of algorithm. The sieve method may be of independent interests and may provide some new insights into the IP-like problems.The rest of the paper is organized as follows. In Section2, we formalize the notations, review MPKC in a conceptual level, and define IP-like problems. In Section 3, we elaborate on the proposed sieve method for the PLE problem. Section 4 provides some concluding remarks.


## 2. Preliminaries

### 2.1. Notations

Throughout this paper, the following notations will be used. We use𝔽q to denote a finite field with order q being a prime power. In this paper, we only consider the PLE problem over 𝔽q with q>2. We use bold lowercase letters for vectors and bold capital letters for matrices. The generalized linear group over 𝔽q is denoted as GL(𝔽q,n) which consists of all n-dimensional invertible matrices over 𝔽q. For two sets A and B, we define A+B={a+b:a∈A,b∈B} and A-B={a-b:a∈A,b∈B}. For a set S⊂𝔽qn and a nonzero element a∈𝔽q, we define aS={as:s∈S} and S/a={a-1s:s∈S}, where a-1 stands for the inverse of a in 𝔽q. For a map 𝒮:𝔽qn→𝔽qm and a vector s∈𝔽qm, we use the symbol 𝒮-1(s) to denote the preimages set of s under the map 𝒮; namely, 𝒮-1(s)={x∈𝔽qn:𝒮(x)=s}.


### 2.2. Multivariate Public Key Cryptosystems

The multivariate public key cryptosystems almost always follow the following designs [5]; namely, first define an easy-to-invert central map and then disguise the central map as a seeminglyhard nonlinear map via two invertible affine transformations.Key Generation. Let 𝔽q be a finite field with order q being a prime power. Firstly, define a nonlinear central map 𝒮:𝔽qn→𝔽qm; namely, for x∈𝔽qn, 𝒮(x)=(s1(x),…,sm(x)). In case of a public key encryption scheme, we require that for any b∈𝔽qm, all the solutions x∈𝔽qn (if the solutions exist) to the system of nonlinear equations 𝒮(x)=b can be efficiently determined; namely, 𝒮-1(b)={x∈𝔽qn:𝒮(x)=b}. In case of a digital signature scheme, we require that for any b∈𝔽qm, we can efficiently find one solution x∈𝒮-1(b) (if the solutions exist) to the system of nonlinear equations 𝒮(x)=b. Secondly, randomly choose two invertible affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm; namely, choose invertible matrices M1 (M2, resp.) uniformly and at random from GL(𝔽q,n) (GL(𝔽q,m), resp.) and two vectors v1 (v2, resp.) uniformly and at random from 𝔽qn (𝔽qm, resp.), and define the two affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm as for x∈𝔽qn, ℒ1(x)=xM1+v1, and for y∈𝔽qm, ℒ2(y)=yM2+v2. Thirdly, compute the inverses ℒ1-1 and ℒ2-1 of ℒ1 and ℒ2; namely, for x∈𝔽qn, ℒ1-1(x)=(x-v1)M1-1, and for y∈𝔽qm, ℒ2-1(y)=(y-v2)M2-1. Finally, compute 𝒫=ℒ2∘𝒮∘ℒ1:𝔽qn→𝔽qm; namely, for x∈𝔽qn, 𝒫(x)=ℒ2∘𝒮∘ℒ1(x)=𝒮(xM1+v1)M2+v2. The public key is the nonlinear map 𝒫, and the secret key consists of 𝒮, ℒ1-1, and ℒ2-1.Encryption. For a plaintext m∈𝔽qn, the corresponding ciphertext is computed via c=𝒫(m)∈𝔽qm.Decryption. Given a ciphertext c∈𝔽qm, we firstly compute y=ℒ2-1(c)=(c-v2)M2-1. Secondly, compute all the preimages of y∈𝔽qm under the nonlinear map 𝒮; namely, 𝒮-1(y)={x∈𝔽qn:𝒮(x)=y}. Thirdly, for all the vectors x∈𝒮-1(y), we compute m=ℒ1-1(x)=(x-v1)M1-1 to obtain a set of candidate plaintexts. Finally, we use some redundant information to exactly pick out the plaintext m.The design also applies to digital signature schemes.Signature. To sign a message m∈𝔽qm, we firstly compute z=ℒ2-1(m) then invert 𝒮 to get a pre-image y∈𝒮-1(z) and finally compute x=ℒ1-1(y). The vector x∈𝔽qn is the signature on the message m.Verification. The verifier decides whether m=𝒫(x) or not. If the equations are satisfied, the verifier accepts x as the valid signature of m. Otherwise, the verifier refuses to accept x as the valid signature of m.Remarks. The central map 𝒮 always has a special structure in that it allows us to efficiently find the pre-images. So in some cases, it is useless to keep the central map secret. For example, the MI [16] central map is 𝒮(X)=Xqθ+1, which makes it meaningless to keep 𝒮 secret. Several paddings were suggested on the basic construction of MPKC in order to obtain a higher level of security [30], for example, the plus method [30], the minus method [30], and so on.


### 2.3. Definitions

The following definitions are closely related to the key recovery attacks on multivariate public key cryptosystems.Definition 1 (IP [7]).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find two invertible affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm such that 𝒫=ℒ2∘𝒮∘ℒ1. Equivalently, find two invertible matrices M1∈GL(𝔽q,n) and M2∈GL(𝔽q,m) and two vectors v1∈𝔽qn and v2∈𝔽qm such that 𝒫(x)=𝒮(xM1+v1)M2+v2.Whenℒ2 is known or equal to the identity transformation, we get the definition of the IP1s problem [8, 23].Definition 2 (IP1s).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find an invertible affine transformation ℒ:𝔽qn→𝔽qn such that 𝒫=𝒮∘ℒ. Equivalently, find an invertible matrix M∈GL(𝔽q,n) and a vector v∈𝔽qn such that 𝒫(x)=𝒮(xM+v).It was shown in [24] that the IP1s problem and the PLE problem are polynomial-time equivalent. So we only need to discuss the following PLE problem in order to discuss the IP1s problem.Definition 3 (PLE).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find an invertible linear transformation ℒ:𝔽qn→𝔽qn such that 𝒫=𝒮∘ℒ. Equivalently, find an invertible matrix M∈GL(𝔽q,n) such that 𝒫(x)=𝒮(xM).


## 2.1. Notations

Throughout this paper, the following notations will be used. We use𝔽q to denote a finite field with order q being a prime power. In this paper, we only consider the PLE problem over 𝔽q with q>2. We use bold lowercase letters for vectors and bold capital letters for matrices. The generalized linear group over 𝔽q is denoted as GL(𝔽q,n) which consists of all n-dimensional invertible matrices over 𝔽q. For two sets A and B, we define A+B={a+b:a∈A,b∈B} and A-B={a-b:a∈A,b∈B}. For a set S⊂𝔽qn and a nonzero element a∈𝔽q, we define aS={as:s∈S} and S/a={a-1s:s∈S}, where a-1 stands for the inverse of a in 𝔽q. For a map 𝒮:𝔽qn→𝔽qm and a vector s∈𝔽qm, we use the symbol 𝒮-1(s) to denote the preimages set of s under the map 𝒮; namely, 𝒮-1(s)={x∈𝔽qn:𝒮(x)=s}.


## 2.2. Multivariate Public Key Cryptosystems

The multivariate public key cryptosystems almost always follow the following designs [5]; namely, first define an easy-to-invert central map and then disguise the central map as a seeminglyhard nonlinear map via two invertible affine transformations.Key Generation. Let 𝔽q be a finite field with order q being a prime power. Firstly, define a nonlinear central map 𝒮:𝔽qn→𝔽qm; namely, for x∈𝔽qn, 𝒮(x)=(s1(x),…,sm(x)). In case of a public key encryption scheme, we require that for any b∈𝔽qm, all the solutions x∈𝔽qn (if the solutions exist) to the system of nonlinear equations 𝒮(x)=b can be efficiently determined; namely, 𝒮-1(b)={x∈𝔽qn:𝒮(x)=b}. In case of a digital signature scheme, we require that for any b∈𝔽qm, we can efficiently find one solution x∈𝒮-1(b) (if the solutions exist) to the system of nonlinear equations 𝒮(x)=b. Secondly, randomly choose two invertible affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm; namely, choose invertible matrices M1 (M2, resp.) uniformly and at random from GL(𝔽q,n) (GL(𝔽q,m), resp.) and two vectors v1 (v2, resp.) uniformly and at random from 𝔽qn (𝔽qm, resp.), and define the two affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm as for x∈𝔽qn, ℒ1(x)=xM1+v1, and for y∈𝔽qm, ℒ2(y)=yM2+v2. Thirdly, compute the inverses ℒ1-1 and ℒ2-1 of ℒ1 and ℒ2; namely, for x∈𝔽qn, ℒ1-1(x)=(x-v1)M1-1, and for y∈𝔽qm, ℒ2-1(y)=(y-v2)M2-1. Finally, compute 𝒫=ℒ2∘𝒮∘ℒ1:𝔽qn→𝔽qm; namely, for x∈𝔽qn, 𝒫(x)=ℒ2∘𝒮∘ℒ1(x)=𝒮(xM1+v1)M2+v2. The public key is the nonlinear map 𝒫, and the secret key consists of 𝒮, ℒ1-1, and ℒ2-1.Encryption. For a plaintext m∈𝔽qn, the corresponding ciphertext is computed via c=𝒫(m)∈𝔽qm.Decryption. Given a ciphertext c∈𝔽qm, we firstly compute y=ℒ2-1(c)=(c-v2)M2-1. Secondly, compute all the preimages of y∈𝔽qm under the nonlinear map 𝒮; namely, 𝒮-1(y)={x∈𝔽qn:𝒮(x)=y}. Thirdly, for all the vectors x∈𝒮-1(y), we compute m=ℒ1-1(x)=(x-v1)M1-1 to obtain a set of candidate plaintexts. Finally, we use some redundant information to exactly pick out the plaintext m.The design also applies to digital signature schemes.Signature. To sign a message m∈𝔽qm, we firstly compute z=ℒ2-1(m) then invert 𝒮 to get a pre-image y∈𝒮-1(z) and finally compute x=ℒ1-1(y). The vector x∈𝔽qn is the signature on the message m.Verification. The verifier decides whether m=𝒫(x) or not. If the equations are satisfied, the verifier accepts x as the valid signature of m. Otherwise, the verifier refuses to accept x as the valid signature of m.Remarks. The central map 𝒮 always has a special structure in that it allows us to efficiently find the pre-images. So in some cases, it is useless to keep the central map secret. For example, the MI [16] central map is 𝒮(X)=Xqθ+1, which makes it meaningless to keep 𝒮 secret. Several paddings were suggested on the basic construction of MPKC in order to obtain a higher level of security [30], for example, the plus method [30], the minus method [30], and so on.


## 2.3. Definitions

The following definitions are closely related to the key recovery attacks on multivariate public key cryptosystems.Definition 1 (IP [7]).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find two invertible affine transformations ℒ1:𝔽qn→𝔽qn and ℒ2:𝔽qm→𝔽qm such that 𝒫=ℒ2∘𝒮∘ℒ1. Equivalently, find two invertible matrices M1∈GL(𝔽q,n) and M2∈GL(𝔽q,m) and two vectors v1∈𝔽qn and v2∈𝔽qm such that 𝒫(x)=𝒮(xM1+v1)M2+v2.Whenℒ2 is known or equal to the identity transformation, we get the definition of the IP1s problem [8, 23].Definition 2 (IP1s).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find an invertible affine transformation ℒ:𝔽qn→𝔽qn such that 𝒫=𝒮∘ℒ. Equivalently, find an invertible matrix M∈GL(𝔽q,n) and a vector v∈𝔽qn such that 𝒫(x)=𝒮(xM+v).It was shown in [24] that the IP1s problem and the PLE problem are polynomial-time equivalent. So we only need to discuss the following PLE problem in order to discuss the IP1s problem.Definition 3 (PLE).
Given two nonlinear polynomial maps𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm, find an invertible linear transformation ℒ:𝔽qn→𝔽qn such that 𝒫=𝒮∘ℒ. Equivalently, find an invertible matrix M∈GL(𝔽q,n) such that 𝒫(x)=𝒮(xM).


## 3. The Proposed Sieve Method for PLE

We pay our attention to a special case of the PLE problem: the preimages of the central map𝒮 are easy to determine. Namely, we are given two nonlinear polynomial maps 𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm and an efficient algorithm 𝒜 to solve the preimages of the central map 𝒮. We want to find an invertible matrix M∈GL(𝔽q,n) such that
(1)(p1(x),…,pm(x))=𝒫(x)=𝒮(xM)=(s1(xM),…,sm(xM)).


### 3.1. Case of𝒮 Being Injective

If𝒮 is an easy-to-invert injective polynomial map, the PLE problem turns out to be very easy. We randomly choose n linearly dependent row vectors x1,…,xn∈𝔽qn and denote the matrix consisting of the n vectors as
(2)X=(x1⋮xn).
For i=1,…,n, we compute 𝒫(xi)=(p1(xi),…,pm(xi)). Note that 𝒫(xi)=𝒮(xiM)=(s1(xiM),…,sm(xiM)), so yi=xiM is a solution to the system of equations 𝒮(y)=𝒫(xi). Further noting that 𝒮 is an easy-to-invert injective polynomial map, we conclude that yi=xiM is the unique solution to the system of equations 𝒮(y)=𝒫(xi). So we can apply the algorithm 𝒜 to determine the unique solution yi to the system of equations 𝒮(y)=𝒫(xi). We denote the matrix consisting of the n row vectors y1,…,yn∈𝔽qn as
(3)Y=(y1⋮yn).
We rewrite the equations yi=xiM for i=1,…,n in terms of matrix, so we have Y=XM, from which we immediately get M=X-1Y.


### 3.2.  General Case

We consider a more general case; namely,𝒮 is an easy-to-invertible noninjective polynomial map.


#### 3.2.1. Basic Idea

The basic idea for the sieve method to solve the PLE problem is to firstly randomly choosen linearly dependent row vectors x1,…,xn∈𝔽qn, and then for i=1,…,n, compute 𝒫(xi). Note that the system of nonlinear equations 𝒮(y)=𝒫(xi) must have at least a solution yi=xiM in that 𝒮(yi)=𝒮(xiM)=𝒫(xi). Secondly, we apply the algorithm 𝒜 to get the nonempty set of the solutions to 𝒮(y)=𝒫(xi); namely,
(4)𝒮-1(𝒫(xi))={y∈𝔽qn:𝒮(y)=𝒫(xi)}.
However, the noninjectivity of the central polynomial map 𝒮 says that the solutions set 𝒮-1(𝒫(xi)) may include some other solutions except yi=xiM. We are only interested in the targeted solution yi=xiM and want to develop a method to pick out the vector yi=xiM from all the solutions in 𝒮-1(𝒫(xi)). If for i=1,…,n we can determine the corresponding yi=xiM, we just denote the matrices consisting of the row vectors xi and yi as X and Y, respectively. Similarly to the discussions in Section 3.1, we can solve the PLE problem just by computing M=X-1Y.In what follows, we will design three types of sieves called multiplicative sieve, differential sieve, and additive sieve, respectively. When we apply the three sieves to𝒮-1(𝒫(xi)), we hope that the targeted solution yi=xiM can pass the sieves, and other useless solutions in 𝒮-1(𝒫(xi)) are distilled out as many as possible. Now we discuss some properties of the PLE problem.


#### 3.2.2. Sieve Strategies

Letx1,…,xn∈𝔽qn be n linearly dependent row vectors, the set of solutions to the equations 𝒮(y)=𝒫(xi) be 𝒮-1(𝒫(xi)), and yi=xiM∈𝒮-1(𝒫(xi)). We have the following results.Theorem 4 (multiplicative strategy).
For anya≠0,1 in 𝔽q, ayi is also a solution to the system of nonlinear equations 𝒮(y)=𝒫(axi); namely, ayi∈𝒮-1(𝒫(axi)), or equivalently, yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).Proof.
We first note thatyi=xiM, so ayi=axiM. Therefore, we have 𝒮(ayi)=𝒮(axiM)=𝒫(axi), namely, ayi∈𝒮-1(𝒫(axi)); or equivalently, yi∈𝒮-1(𝒫(axi))/a. Note that yi∈𝒮-1(𝒫(xi)), so we have yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).The theorem ofMultiplicative Strategy implies a method to sieve out some useless vectors from a set of vectors containing the targeted vector yi=xiM. More precisely, we let Si⊂𝒮-1(𝒫(xi)) such that the targeted vector yi=xiM∈Si. The multiplicative sieve algorithm  MulSieve given in Algorithm1 takes input as (𝔽q,𝒮,𝒫,xi,Si) and outputs a subset Si× of Si; namely, Si×=  MulSieve (𝔽q,𝒮,𝒫,xi,Si). From the proof of Multiplicative Strategy theorem, we know that the targeted vector yi=xiM can pass the multiplicative sieve. So the set Si× output by  MulSieve is not empty.Algorithm 1:Multiplicative sieve: MulSieve (𝔽q,𝒮,𝒫,xi,Si).
(1) Set the setSi×=Φ. //Φ  denotes an empty set.
(2) Choose an elementai≠0,1 uniformly and randomly from 𝔽q and compute 𝒫(aixi).
(3)for each vector y∈Si  do
(4)Compute 𝒮(aiy).
(5)if  𝒮(aiy)=𝒫(aixi)  then
(6)Add y to the set Si×.
(7)end if
(8)end for
(9)return  Si×.We note that if𝒮 and hence 𝒫 are homogeneous polynomials, all the preimages in Si can pass the multiplicative sieve. So in this case, we must have Si×=Si. In general cases, 𝒮 is not homogeneous, and the multiplicative sieve method can sieve out some preimages of Si.Theorem 5 (additive strategy).
For1≤i<j≤n, one must have that yi+yj is a solution to the system of equations 𝒮(y)=𝒫(xi+xj). That is, if one denotes the solutions set to the system of nonlinear equations 𝒮(y)=𝒫(xi+xj) as 𝒮-1(𝒫(xi+xj)), one must have
(5)yi+yj∈𝒮-1(𝒫(xi+xj))∩(𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj))).Proof.
It is obvious thatyi+yj∈𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj)). So we just need to verify yi+yj∈𝒮-1(𝒫(xi+xj)); namely, 𝒫(xi+xj)=𝒮(yi+yj). Recalling yi=xiM, yj=xjM, and 𝒫(x)=𝒮(xM), we immediately have 𝒮(yi+yj)=𝒮((xi+xj)M)=𝒫(xi+xj).The theorem ofAdditive Strategy implies another sieve method called additive sieve method  AddSieve in Algorithm 2. The input of the additive sieve algorithm  AddSieve consists of (𝔽q,𝒮,𝒫,xi,xj,Si,Sj), where 1≤i<j≤n, Si (Sj, resp.) is a subset of 𝒮-1(𝒫(xi)) (𝒮-1(𝒫(xj)), resp.), and yi∈Si (yj∈Sj, resp.). The output of  AddSieve is two nonempty sets Si+⊂Si and Sj+⊂Sj; namely,
(6)(Si+,Sj+)=AddSieve(𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
From the proof of Multiplicative Strategy theorem, we know that the targeted vectors yi=xiM and yj=xjM can pass the additive sieve. So the sets Si+ and Sj+ output by  AddSieve are not empty.Algorithm 2:Additive sieve: AddSieve (𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
(1)   Set the two setsSi+=Φ and Sj+=Φ.
(2)   Compute𝒫(xi+xj).
(3)for each y(i)∈Si  do
(4) for each y(j)∈Sj  do
(5) Compute 𝒮(y(i)+y(j)).
(6) if  𝒫(xi+xj)=S(y(i)+y(j))  then
(7)Add y(i) to Si+, and y(j) to Sj+, respectively.
(8) end if
(9) end for
(10)end for
(11)return  (Si+,Sj+).In lines 6–8 of Algorithm2, if y(i) or y(j) had been put into Si+ or Sj+, the algorithm does nothing.Theorem 6 (differential strategy).
For any nonzero vectorz∈𝔽qn and any element a≠0,1 in 𝔽q, let the set of the solutions to the system of nonlinear equations 𝒮(y)=𝒫(xi+z) and 𝒮(y)=𝒫(xi+az) be 𝒮-1(𝒫(xi+z)) and 𝒮-1(𝒫(xi+az)), respectively. One must have
(7)(a-1)yi∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)).Proof.
Note thatyi=xiM, so we have (xi+z)M=yi+zM. From 𝒫(x)=𝒮(xM), we get 𝒫(xi+z)=𝒮((xi+z)M)=𝒮(yi+zM). So we have yi+zM∈𝒮-1(𝒫(xi+z)); namely,
(8)a(yi+zM)∈a𝒮-1(𝒫(xi+z)).
We further notice that 𝒫(xi+az)=𝒮((xi+az)M)=𝒮(yi+azM), so we conclude that
(9)yi+azM∈𝒮-1(𝒫(xi+az)).
Combining (8) and (9) implies
(10)(a-1)yi=a(yi+zM)-(yi+azM)∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)),
from which we complete the proof.The theorem ofDifferential Strategy implies another sieve method called differential sieve method  DifSieve in Algorithm 3. The input of the differential sieve algorithm  DifSieve consists of (𝔽q,𝒮,𝒫,xi,Si), where Si is a subset of 𝒮-1(𝒫(xi)) and yi∈Si. The output of  DifSieve is a nonempty set Si-⊂Si; namely, Si-=  DifSieve  (𝔽q,𝒮,𝒫,xi,Si). From the proof of Differential Strategy theorem, we know that the targeted vectors yi=xiM can pass the differential sieve. So the set Si- output by the  DifSieve algorithm is nonempty.Algorithm 3:Differential sieve: DifSieve (𝔽q,𝒮,𝒫,xi,Si).
(1)   Set the setSi-=Φ.
(2)   Randomly choose an elementai≠0,1 from 𝔽q and a nonzero vector
zi∈𝔽qn.
(3)   Compute𝒫(xi+zi) and 𝒫(xi+aizi).
(4)   Compute the pre-images sets𝒮-1(𝒫(xi+zi)) and 𝒮-1(𝒫(xi+aizi)).
(5)for each y∈Si  do
(6)  if  (ai-1)y∈ai𝒮-1(𝒫(xi+zi))-𝒮-1(𝒫(xi+aizi))  then
(7)  Add y to Si-.
(8)  end if
(9)end for
(10)return  Si-


### 3.3. The Sieve Method

We elaborate on the novel sieve algorithmSieAlg for solving the PLE problem as in Algorithm 4. The input for the sieve algorithm contains the description of the finite field 𝔽q and two multivariate nonlinear polynomial maps 𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm. The output of the sieve algorithm is either an invertible matrix M∈GL(𝔽q,n) such that 𝒫(x)=𝒮(xM) or a failure symbol ⊥. We assume that the central map 𝒮 is easy to invert; namely, there exists an efficient algorithm 𝒜 to compute all the preimages of 𝒮. The proposed sieve algorithm runs as in Algorithm 4.Algorithm 4:The sieve algorithm for PLE: SieAlg (𝔽q,𝒮,𝒫).
(1)   Randomly choosen linearly independent vectors x1,…,xn∈𝔽qn. Store
the n row vectors xi as an invertible n-dimensional matrix X.
(2)for  i=1,…,n  do
(3)  Compute 𝒫(xi) and the pre-image set  𝒮-1(𝒫(xi)).
(4)  Store the set Si=𝒮-1(𝒫(xi)).
(5)end for  //Algorithm Initialization.
(6)for  i=1,…,n  do
(7)  Run MulSieve(𝔽q,𝒮,𝒫,xi,Si) and assign the output to Si.
(8)end for  //Multiplicative Sieve.
(9)for  i=1,…,n-1  do
(10)  for  j=i+1,…,n  do
(11)   RunAddSieve(𝔽q,𝒮,𝒫,xi,xj,Si,Sj) and assign the output to Si
and Sj.
(12)  end for
(13)end for  //Additive Sieve.
(14)for  i=1,…,n  do
(15)  Run DifSieve(𝔽q,𝒮,𝒫,xi,Si) and assign the output to Si.
(16)end for  //Differential Sieve.
(17)for  i=1,…,n  do
(18)  Randomly choose a vector from Si and assign the vector to yi.
(19)end for
(20) Denote the set of vectorsy1,…,yn  as a matrix Y.
(21) ComputeM=X-1Y.
(22)if  𝒫(x)=𝒮(xM)  then
(23)  return  M.
(24)else
(25)  return  ⊥.
(26)end if


### 3.4. Analysis

We analyze the computational complexity of the proposed sieve algorithm for the PLE problem. We denote the computational costs for determining the preimages set of the polynomial central map𝒮 as Δ. Note that we assume that the central map 𝒮 is easy to invert, so Δ is upper-bounded by a polynomial about the number n of the variables and the number m of the involved equations. We let the computational costs for computing 𝒮(x) for any x∈𝔽qn as δ. Note that 𝒫(x)=𝒮(xM), so for any x∈𝔽qn, it requires about the same computational costs δ to compute 𝒫(x). We denote the upper bound for the number of preimages of a vector b∈𝔽qm under the central map 𝒮 as l; namely, the preimages set 𝒮-1(b) has at most l vectors. Note that we assume that 𝒜 is a polynomial-time algorithm to find all the preimages for the central map 𝒮, so l is also polynomially bounded.In the algorithm initialization phase of the sieve algorithmSieAlg for the PLE problem, we need to compute 𝒫(xi) and the pre-image set 𝒮-1(𝒫(xi)) for each i=1,…,n. So in the algorithm initialization phase, the computational costs are measured as 𝒪(n(Δ+δ)).In the multiplicative sieve phase, for eachi=1,…,n, we need to compute 𝒫(aixi), which costs 𝒪(nδ). Then for each y∈𝒮-1(𝒫(xi)), we need to compute 𝒮(aiy), so the computational costs are 𝒪(nlδ). So the total costs in the multiplicative sieve phase are 𝒪(nδ+nlδ)=𝒪(nlδ).In the additive sieve phase, for1≤i<j≤n, we need to compute 𝒫(xi+xj), which costs 𝒪(n2δ). For 1≤i<j≤n, for each y(i)∈Si× and for each y(j)∈Sj×, we need to compute 𝒮(y(i)+y(j)), which cost 𝒪(n2l2δ). So the computational costs in the additive sieve phase are 𝒪(n2l2δ).In the differential sieve phase, for eachi=1,…,n, we need to compute 𝒫(xi+zi), 𝒫(xi+aizi), and the preimages sets 𝒮-1(𝒫(xi+zi)) and 𝒮-1(𝒫(xi+aizi)). In this step, the computational costs are 𝒪(nδ+nΔ). We also need to do exhaustive search for y∈Si+, which costs 𝒪(l). So during the differential sieve phase, we need to do 𝒪(nδ+nΔ+l) computations.Finally, the sieve method needs to computeM=X-1Y, which costs 𝒪(n3).To summarize, the computational costs for the sieve algorithm are the sum of the aforementioned computational costs. So the computational complexity of the sieve algorithm is𝒪(n2l2δ+nΔ+l+n3). Therefore, the proposed sieve algorithm is polynomial-time if there exists a polynomial-time algorithm 𝒜 to determine the preimages set of the central map 𝒮.We remark on the sieve algorithm as follows. In the sieve algorithm, we assume that the order of the underlying finite field𝔽q is q>2. If the PLE problem is defined over 𝔽2, we can consider the PLE problem over some extension field of 𝔽2 in order to make the proposed sieve algorithm applicable. The proposed sieve algorithm does not sieve out the yi satisfying yi=xiM. In other words, the proposed sieve algorithm does not sieve out the right answer for the PLE problem. When the algorithm quits and fails to output the right answer, we can reimplement the sieve algorithm one more time in order to increase the probability that we can solve the PLE problem.


## 3.1. Case of𝒮 Being Injective

If𝒮 is an easy-to-invert injective polynomial map, the PLE problem turns out to be very easy. We randomly choose n linearly dependent row vectors x1,…,xn∈𝔽qn and denote the matrix consisting of the n vectors as
(2)X=(x1⋮xn).
For i=1,…,n, we compute 𝒫(xi)=(p1(xi),…,pm(xi)). Note that 𝒫(xi)=𝒮(xiM)=(s1(xiM),…,sm(xiM)), so yi=xiM is a solution to the system of equations 𝒮(y)=𝒫(xi). Further noting that 𝒮 is an easy-to-invert injective polynomial map, we conclude that yi=xiM is the unique solution to the system of equations 𝒮(y)=𝒫(xi). So we can apply the algorithm 𝒜 to determine the unique solution yi to the system of equations 𝒮(y)=𝒫(xi). We denote the matrix consisting of the n row vectors y1,…,yn∈𝔽qn as
(3)Y=(y1⋮yn).
We rewrite the equations yi=xiM for i=1,…,n in terms of matrix, so we have Y=XM, from which we immediately get M=X-1Y.


## 3.2.  General Case

We consider a more general case; namely,𝒮 is an easy-to-invertible noninjective polynomial map.


### 3.2.1. Basic Idea

The basic idea for the sieve method to solve the PLE problem is to firstly randomly choosen linearly dependent row vectors x1,…,xn∈𝔽qn, and then for i=1,…,n, compute 𝒫(xi). Note that the system of nonlinear equations 𝒮(y)=𝒫(xi) must have at least a solution yi=xiM in that 𝒮(yi)=𝒮(xiM)=𝒫(xi). Secondly, we apply the algorithm 𝒜 to get the nonempty set of the solutions to 𝒮(y)=𝒫(xi); namely,
(4)𝒮-1(𝒫(xi))={y∈𝔽qn:𝒮(y)=𝒫(xi)}.
However, the noninjectivity of the central polynomial map 𝒮 says that the solutions set 𝒮-1(𝒫(xi)) may include some other solutions except yi=xiM. We are only interested in the targeted solution yi=xiM and want to develop a method to pick out the vector yi=xiM from all the solutions in 𝒮-1(𝒫(xi)). If for i=1,…,n we can determine the corresponding yi=xiM, we just denote the matrices consisting of the row vectors xi and yi as X and Y, respectively. Similarly to the discussions in Section 3.1, we can solve the PLE problem just by computing M=X-1Y.In what follows, we will design three types of sieves called multiplicative sieve, differential sieve, and additive sieve, respectively. When we apply the three sieves to𝒮-1(𝒫(xi)), we hope that the targeted solution yi=xiM can pass the sieves, and other useless solutions in 𝒮-1(𝒫(xi)) are distilled out as many as possible. Now we discuss some properties of the PLE problem.


### 3.2.2. Sieve Strategies

Letx1,…,xn∈𝔽qn be n linearly dependent row vectors, the set of solutions to the equations 𝒮(y)=𝒫(xi) be 𝒮-1(𝒫(xi)), and yi=xiM∈𝒮-1(𝒫(xi)). We have the following results.Theorem 4 (multiplicative strategy).
For anya≠0,1 in 𝔽q, ayi is also a solution to the system of nonlinear equations 𝒮(y)=𝒫(axi); namely, ayi∈𝒮-1(𝒫(axi)), or equivalently, yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).Proof.
We first note thatyi=xiM, so ayi=axiM. Therefore, we have 𝒮(ayi)=𝒮(axiM)=𝒫(axi), namely, ayi∈𝒮-1(𝒫(axi)); or equivalently, yi∈𝒮-1(𝒫(axi))/a. Note that yi∈𝒮-1(𝒫(xi)), so we have yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).The theorem ofMultiplicative Strategy implies a method to sieve out some useless vectors from a set of vectors containing the targeted vector yi=xiM. More precisely, we let Si⊂𝒮-1(𝒫(xi)) such that the targeted vector yi=xiM∈Si. The multiplicative sieve algorithm  MulSieve given in Algorithm1 takes input as (𝔽q,𝒮,𝒫,xi,Si) and outputs a subset Si× of Si; namely, Si×=  MulSieve (𝔽q,𝒮,𝒫,xi,Si). From the proof of Multiplicative Strategy theorem, we know that the targeted vector yi=xiM can pass the multiplicative sieve. So the set Si× output by  MulSieve is not empty.Algorithm 1:Multiplicative sieve: MulSieve (𝔽q,𝒮,𝒫,xi,Si).
(1) Set the setSi×=Φ. //Φ  denotes an empty set.
(2) Choose an elementai≠0,1 uniformly and randomly from 𝔽q and compute 𝒫(aixi).
(3)for each vector y∈Si  do
(4)Compute 𝒮(aiy).
(5)if  𝒮(aiy)=𝒫(aixi)  then
(6)Add y to the set Si×.
(7)end if
(8)end for
(9)return  Si×.We note that if𝒮 and hence 𝒫 are homogeneous polynomials, all the preimages in Si can pass the multiplicative sieve. So in this case, we must have Si×=Si. In general cases, 𝒮 is not homogeneous, and the multiplicative sieve method can sieve out some preimages of Si.Theorem 5 (additive strategy).
For1≤i<j≤n, one must have that yi+yj is a solution to the system of equations 𝒮(y)=𝒫(xi+xj). That is, if one denotes the solutions set to the system of nonlinear equations 𝒮(y)=𝒫(xi+xj) as 𝒮-1(𝒫(xi+xj)), one must have
(5)yi+yj∈𝒮-1(𝒫(xi+xj))∩(𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj))).Proof.
It is obvious thatyi+yj∈𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj)). So we just need to verify yi+yj∈𝒮-1(𝒫(xi+xj)); namely, 𝒫(xi+xj)=𝒮(yi+yj). Recalling yi=xiM, yj=xjM, and 𝒫(x)=𝒮(xM), we immediately have 𝒮(yi+yj)=𝒮((xi+xj)M)=𝒫(xi+xj).The theorem ofAdditive Strategy implies another sieve method called additive sieve method  AddSieve in Algorithm 2. The input of the additive sieve algorithm  AddSieve consists of (𝔽q,𝒮,𝒫,xi,xj,Si,Sj), where 1≤i<j≤n, Si (Sj, resp.) is a subset of 𝒮-1(𝒫(xi)) (𝒮-1(𝒫(xj)), resp.), and yi∈Si (yj∈Sj, resp.). The output of  AddSieve is two nonempty sets Si+⊂Si and Sj+⊂Sj; namely,
(6)(Si+,Sj+)=AddSieve(𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
From the proof of Multiplicative Strategy theorem, we know that the targeted vectors yi=xiM and yj=xjM can pass the additive sieve. So the sets Si+ and Sj+ output by  AddSieve are not empty.Algorithm 2:Additive sieve: AddSieve (𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
(1)   Set the two setsSi+=Φ and Sj+=Φ.
(2)   Compute𝒫(xi+xj).
(3)for each y(i)∈Si  do
(4) for each y(j)∈Sj  do
(5) Compute 𝒮(y(i)+y(j)).
(6) if  𝒫(xi+xj)=S(y(i)+y(j))  then
(7)Add y(i) to Si+, and y(j) to Sj+, respectively.
(8) end if
(9) end for
(10)end for
(11)return  (Si+,Sj+).In lines 6–8 of Algorithm2, if y(i) or y(j) had been put into Si+ or Sj+, the algorithm does nothing.Theorem 6 (differential strategy).
For any nonzero vectorz∈𝔽qn and any element a≠0,1 in 𝔽q, let the set of the solutions to the system of nonlinear equations 𝒮(y)=𝒫(xi+z) and 𝒮(y)=𝒫(xi+az) be 𝒮-1(𝒫(xi+z)) and 𝒮-1(𝒫(xi+az)), respectively. One must have
(7)(a-1)yi∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)).Proof.
Note thatyi=xiM, so we have (xi+z)M=yi+zM. From 𝒫(x)=𝒮(xM), we get 𝒫(xi+z)=𝒮((xi+z)M)=𝒮(yi+zM). So we have yi+zM∈𝒮-1(𝒫(xi+z)); namely,
(8)a(yi+zM)∈a𝒮-1(𝒫(xi+z)).
We further notice that 𝒫(xi+az)=𝒮((xi+az)M)=𝒮(yi+azM), so we conclude that
(9)yi+azM∈𝒮-1(𝒫(xi+az)).
Combining (8) and (9) implies
(10)(a-1)yi=a(yi+zM)-(yi+azM)∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)),
from which we complete the proof.The theorem ofDifferential Strategy implies another sieve method called differential sieve method  DifSieve in Algorithm 3. The input of the differential sieve algorithm  DifSieve consists of (𝔽q,𝒮,𝒫,xi,Si), where Si is a subset of 𝒮-1(𝒫(xi)) and yi∈Si. The output of  DifSieve is a nonempty set Si-⊂Si; namely, Si-=  DifSieve  (𝔽q,𝒮,𝒫,xi,Si). From the proof of Differential Strategy theorem, we know that the targeted vectors yi=xiM can pass the differential sieve. So the set Si- output by the  DifSieve algorithm is nonempty.Algorithm 3:Differential sieve: DifSieve (𝔽q,𝒮,𝒫,xi,Si).
(1)   Set the setSi-=Φ.
(2)   Randomly choose an elementai≠0,1 from 𝔽q and a nonzero vector
zi∈𝔽qn.
(3)   Compute𝒫(xi+zi) and 𝒫(xi+aizi).
(4)   Compute the pre-images sets𝒮-1(𝒫(xi+zi)) and 𝒮-1(𝒫(xi+aizi)).
(5)for each y∈Si  do
(6)  if  (ai-1)y∈ai𝒮-1(𝒫(xi+zi))-𝒮-1(𝒫(xi+aizi))  then
(7)  Add y to Si-.
(8)  end if
(9)end for
(10)return  Si-


## 3.2.1. Basic Idea

The basic idea for the sieve method to solve the PLE problem is to firstly randomly choosen linearly dependent row vectors x1,…,xn∈𝔽qn, and then for i=1,…,n, compute 𝒫(xi). Note that the system of nonlinear equations 𝒮(y)=𝒫(xi) must have at least a solution yi=xiM in that 𝒮(yi)=𝒮(xiM)=𝒫(xi). Secondly, we apply the algorithm 𝒜 to get the nonempty set of the solutions to 𝒮(y)=𝒫(xi); namely,
(4)𝒮-1(𝒫(xi))={y∈𝔽qn:𝒮(y)=𝒫(xi)}.
However, the noninjectivity of the central polynomial map 𝒮 says that the solutions set 𝒮-1(𝒫(xi)) may include some other solutions except yi=xiM. We are only interested in the targeted solution yi=xiM and want to develop a method to pick out the vector yi=xiM from all the solutions in 𝒮-1(𝒫(xi)). If for i=1,…,n we can determine the corresponding yi=xiM, we just denote the matrices consisting of the row vectors xi and yi as X and Y, respectively. Similarly to the discussions in Section 3.1, we can solve the PLE problem just by computing M=X-1Y.In what follows, we will design three types of sieves called multiplicative sieve, differential sieve, and additive sieve, respectively. When we apply the three sieves to𝒮-1(𝒫(xi)), we hope that the targeted solution yi=xiM can pass the sieves, and other useless solutions in 𝒮-1(𝒫(xi)) are distilled out as many as possible. Now we discuss some properties of the PLE problem.


## 3.2.2. Sieve Strategies

Letx1,…,xn∈𝔽qn be n linearly dependent row vectors, the set of solutions to the equations 𝒮(y)=𝒫(xi) be 𝒮-1(𝒫(xi)), and yi=xiM∈𝒮-1(𝒫(xi)). We have the following results.Theorem 4 (multiplicative strategy).
For anya≠0,1 in 𝔽q, ayi is also a solution to the system of nonlinear equations 𝒮(y)=𝒫(axi); namely, ayi∈𝒮-1(𝒫(axi)), or equivalently, yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).Proof.
We first note thatyi=xiM, so ayi=axiM. Therefore, we have 𝒮(ayi)=𝒮(axiM)=𝒫(axi), namely, ayi∈𝒮-1(𝒫(axi)); or equivalently, yi∈𝒮-1(𝒫(axi))/a. Note that yi∈𝒮-1(𝒫(xi)), so we have yi∈𝒮-1(𝒫(xi))∩(𝒮-1(𝒫(axi))/a).The theorem ofMultiplicative Strategy implies a method to sieve out some useless vectors from a set of vectors containing the targeted vector yi=xiM. More precisely, we let Si⊂𝒮-1(𝒫(xi)) such that the targeted vector yi=xiM∈Si. The multiplicative sieve algorithm  MulSieve given in Algorithm1 takes input as (𝔽q,𝒮,𝒫,xi,Si) and outputs a subset Si× of Si; namely, Si×=  MulSieve (𝔽q,𝒮,𝒫,xi,Si). From the proof of Multiplicative Strategy theorem, we know that the targeted vector yi=xiM can pass the multiplicative sieve. So the set Si× output by  MulSieve is not empty.Algorithm 1:Multiplicative sieve: MulSieve (𝔽q,𝒮,𝒫,xi,Si).
(1) Set the setSi×=Φ. //Φ  denotes an empty set.
(2) Choose an elementai≠0,1 uniformly and randomly from 𝔽q and compute 𝒫(aixi).
(3)for each vector y∈Si  do
(4)Compute 𝒮(aiy).
(5)if  𝒮(aiy)=𝒫(aixi)  then
(6)Add y to the set Si×.
(7)end if
(8)end for
(9)return  Si×.We note that if𝒮 and hence 𝒫 are homogeneous polynomials, all the preimages in Si can pass the multiplicative sieve. So in this case, we must have Si×=Si. In general cases, 𝒮 is not homogeneous, and the multiplicative sieve method can sieve out some preimages of Si.Theorem 5 (additive strategy).
For1≤i<j≤n, one must have that yi+yj is a solution to the system of equations 𝒮(y)=𝒫(xi+xj). That is, if one denotes the solutions set to the system of nonlinear equations 𝒮(y)=𝒫(xi+xj) as 𝒮-1(𝒫(xi+xj)), one must have
(5)yi+yj∈𝒮-1(𝒫(xi+xj))∩(𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj))).Proof.
It is obvious thatyi+yj∈𝒮-1(𝒫(xi))+𝒮-1(𝒫(xj)). So we just need to verify yi+yj∈𝒮-1(𝒫(xi+xj)); namely, 𝒫(xi+xj)=𝒮(yi+yj). Recalling yi=xiM, yj=xjM, and 𝒫(x)=𝒮(xM), we immediately have 𝒮(yi+yj)=𝒮((xi+xj)M)=𝒫(xi+xj).The theorem ofAdditive Strategy implies another sieve method called additive sieve method  AddSieve in Algorithm 2. The input of the additive sieve algorithm  AddSieve consists of (𝔽q,𝒮,𝒫,xi,xj,Si,Sj), where 1≤i<j≤n, Si (Sj, resp.) is a subset of 𝒮-1(𝒫(xi)) (𝒮-1(𝒫(xj)), resp.), and yi∈Si (yj∈Sj, resp.). The output of  AddSieve is two nonempty sets Si+⊂Si and Sj+⊂Sj; namely,
(6)(Si+,Sj+)=AddSieve(𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
From the proof of Multiplicative Strategy theorem, we know that the targeted vectors yi=xiM and yj=xjM can pass the additive sieve. So the sets Si+ and Sj+ output by  AddSieve are not empty.Algorithm 2:Additive sieve: AddSieve (𝔽q,𝒮,𝒫,xi,xj,Si,Sj).
(1)   Set the two setsSi+=Φ and Sj+=Φ.
(2)   Compute𝒫(xi+xj).
(3)for each y(i)∈Si  do
(4) for each y(j)∈Sj  do
(5) Compute 𝒮(y(i)+y(j)).
(6) if  𝒫(xi+xj)=S(y(i)+y(j))  then
(7)Add y(i) to Si+, and y(j) to Sj+, respectively.
(8) end if
(9) end for
(10)end for
(11)return  (Si+,Sj+).In lines 6–8 of Algorithm2, if y(i) or y(j) had been put into Si+ or Sj+, the algorithm does nothing.Theorem 6 (differential strategy).
For any nonzero vectorz∈𝔽qn and any element a≠0,1 in 𝔽q, let the set of the solutions to the system of nonlinear equations 𝒮(y)=𝒫(xi+z) and 𝒮(y)=𝒫(xi+az) be 𝒮-1(𝒫(xi+z)) and 𝒮-1(𝒫(xi+az)), respectively. One must have
(7)(a-1)yi∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)).Proof.
Note thatyi=xiM, so we have (xi+z)M=yi+zM. From 𝒫(x)=𝒮(xM), we get 𝒫(xi+z)=𝒮((xi+z)M)=𝒮(yi+zM). So we have yi+zM∈𝒮-1(𝒫(xi+z)); namely,
(8)a(yi+zM)∈a𝒮-1(𝒫(xi+z)).
We further notice that 𝒫(xi+az)=𝒮((xi+az)M)=𝒮(yi+azM), so we conclude that
(9)yi+azM∈𝒮-1(𝒫(xi+az)).
Combining (8) and (9) implies
(10)(a-1)yi=a(yi+zM)-(yi+azM)∈a𝒮-1(𝒫(xi+z))-𝒮-1(𝒫(xi+az)),
from which we complete the proof.The theorem ofDifferential Strategy implies another sieve method called differential sieve method  DifSieve in Algorithm 3. The input of the differential sieve algorithm  DifSieve consists of (𝔽q,𝒮,𝒫,xi,Si), where Si is a subset of 𝒮-1(𝒫(xi)) and yi∈Si. The output of  DifSieve is a nonempty set Si-⊂Si; namely, Si-=  DifSieve  (𝔽q,𝒮,𝒫,xi,Si). From the proof of Differential Strategy theorem, we know that the targeted vectors yi=xiM can pass the differential sieve. So the set Si- output by the  DifSieve algorithm is nonempty.Algorithm 3:Differential sieve: DifSieve (𝔽q,𝒮,𝒫,xi,Si).
(1)   Set the setSi-=Φ.
(2)   Randomly choose an elementai≠0,1 from 𝔽q and a nonzero vector
zi∈𝔽qn.
(3)   Compute𝒫(xi+zi) and 𝒫(xi+aizi).
(4)   Compute the pre-images sets𝒮-1(𝒫(xi+zi)) and 𝒮-1(𝒫(xi+aizi)).
(5)for each y∈Si  do
(6)  if  (ai-1)y∈ai𝒮-1(𝒫(xi+zi))-𝒮-1(𝒫(xi+aizi))  then
(7)  Add y to Si-.
(8)  end if
(9)end for
(10)return  Si-


## 3.3. The Sieve Method

We elaborate on the novel sieve algorithmSieAlg for solving the PLE problem as in Algorithm 4. The input for the sieve algorithm contains the description of the finite field 𝔽q and two multivariate nonlinear polynomial maps 𝒮:𝔽qn→𝔽qm and 𝒫:𝔽qn→𝔽qm. The output of the sieve algorithm is either an invertible matrix M∈GL(𝔽q,n) such that 𝒫(x)=𝒮(xM) or a failure symbol ⊥. We assume that the central map 𝒮 is easy to invert; namely, there exists an efficient algorithm 𝒜 to compute all the preimages of 𝒮. The proposed sieve algorithm runs as in Algorithm 4.Algorithm 4:The sieve algorithm for PLE: SieAlg (𝔽q,𝒮,𝒫).
(1)   Randomly choosen linearly independent vectors x1,…,xn∈𝔽qn. Store
the n row vectors xi as an invertible n-dimensional matrix X.
(2)for  i=1,…,n  do
(3)  Compute 𝒫(xi) and the pre-image set  𝒮-1(𝒫(xi)).
(4)  Store the set Si=𝒮-1(𝒫(xi)).
(5)end for  //Algorithm Initialization.
(6)for  i=1,…,n  do
(7)  Run MulSieve(𝔽q,𝒮,𝒫,xi,Si) and assign the output to Si.
(8)end for  //Multiplicative Sieve.
(9)for  i=1,…,n-1  do
(10)  for  j=i+1,…,n  do
(11)   RunAddSieve(𝔽q,𝒮,𝒫,xi,xj,Si,Sj) and assign the output to Si
and Sj.
(12)  end for
(13)end for  //Additive Sieve.
(14)for  i=1,…,n  do
(15)  Run DifSieve(𝔽q,𝒮,𝒫,xi,Si) and assign the output to Si.
(16)end for  //Differential Sieve.
(17)for  i=1,…,n  do
(18)  Randomly choose a vector from Si and assign the vector to yi.
(19)end for
(20) Denote the set of vectorsy1,…,yn  as a matrix Y.
(21) ComputeM=X-1Y.
(22)if  𝒫(x)=𝒮(xM)  then
(23)  return  M.
(24)else
(25)  return  ⊥.
(26)end if


## 3.4. Analysis

We analyze the computational complexity of the proposed sieve algorithm for the PLE problem. We denote the computational costs for determining the preimages set of the polynomial central map𝒮 as Δ. Note that we assume that the central map 𝒮 is easy to invert, so Δ is upper-bounded by a polynomial about the number n of the variables and the number m of the involved equations. We let the computational costs for computing 𝒮(x) for any x∈𝔽qn as δ. Note that 𝒫(x)=𝒮(xM), so for any x∈𝔽qn, it requires about the same computational costs δ to compute 𝒫(x). We denote the upper bound for the number of preimages of a vector b∈𝔽qm under the central map 𝒮 as l; namely, the preimages set 𝒮-1(b) has at most l vectors. Note that we assume that 𝒜 is a polynomial-time algorithm to find all the preimages for the central map 𝒮, so l is also polynomially bounded.In the algorithm initialization phase of the sieve algorithmSieAlg for the PLE problem, we need to compute 𝒫(xi) and the pre-image set 𝒮-1(𝒫(xi)) for each i=1,…,n. So in the algorithm initialization phase, the computational costs are measured as 𝒪(n(Δ+δ)).In the multiplicative sieve phase, for eachi=1,…,n, we need to compute 𝒫(aixi), which costs 𝒪(nδ). Then for each y∈𝒮-1(𝒫(xi)), we need to compute 𝒮(aiy), so the computational costs are 𝒪(nlδ). So the total costs in the multiplicative sieve phase are 𝒪(nδ+nlδ)=𝒪(nlδ).In the additive sieve phase, for1≤i<j≤n, we need to compute 𝒫(xi+xj), which costs 𝒪(n2δ). For 1≤i<j≤n, for each y(i)∈Si× and for each y(j)∈Sj×, we need to compute 𝒮(y(i)+y(j)), which cost 𝒪(n2l2δ). So the computational costs in the additive sieve phase are 𝒪(n2l2δ).In the differential sieve phase, for eachi=1,…,n, we need to compute 𝒫(xi+zi), 𝒫(xi+aizi), and the preimages sets 𝒮-1(𝒫(xi+zi)) and 𝒮-1(𝒫(xi+aizi)). In this step, the computational costs are 𝒪(nδ+nΔ). We also need to do exhaustive search for y∈Si+, which costs 𝒪(l). So during the differential sieve phase, we need to do 𝒪(nδ+nΔ+l) computations.Finally, the sieve method needs to computeM=X-1Y, which costs 𝒪(n3).To summarize, the computational costs for the sieve algorithm are the sum of the aforementioned computational costs. So the computational complexity of the sieve algorithm is𝒪(n2l2δ+nΔ+l+n3). Therefore, the proposed sieve algorithm is polynomial-time if there exists a polynomial-time algorithm 𝒜 to determine the preimages set of the central map 𝒮.We remark on the sieve algorithm as follows. In the sieve algorithm, we assume that the order of the underlying finite field𝔽q is q>2. If the PLE problem is defined over 𝔽2, we can consider the PLE problem over some extension field of 𝔽2 in order to make the proposed sieve algorithm applicable. The proposed sieve algorithm does not sieve out the yi satisfying yi=xiM. In other words, the proposed sieve algorithm does not sieve out the right answer for the PLE problem. When the algorithm quits and fails to output the right answer, we can reimplement the sieve algorithm one more time in order to increase the probability that we can solve the PLE problem.


## 4. Conclusions

In this paper, we developed a new method for solving the IP1s problem. It is shown that if there exists a polynomial-time algorithm for determining all the preimages of the central map𝒮, the proposed sieve algorithm for the PLE problem is efficient. As an application of the proposed sieve algorithm for the IP1s problem, we can show that it is infeasible to construct multivariate public key encryption schemes from the IP1s problem due to the following reasons.(i)
Multivariate public key encryption schemes require that the central map must be easy-to-invert.(ii)
Multivariate public key encryption schemes require that ciphertext must be decipherable. So for any vectorb∈𝔽qn, it must be computationally feasible to determine all the preimages of b under the central map 𝒮. This means that the number of the preimages of the central map 𝒮 must be polynomially bounded. The above both things demonstrate that the proposed sieve algorithm is applicable to the IP1s problem used in multivariate public key encryption schemes.As a new method for solving the IP-like problems, the proposed sieve method is far from perfect. So further discussions on the new method belong to our future work.



---

*Source: 872962-2013-12-10.xml*