## 2 Related Work
Formally, the IP problem is stated as follows:  
Definition 1: Consider two vector spaces \(\mathbb{F}^{m}\) and \(\mathbb{F}^{n}\) of dimensions \(m\) and \(n\), respectively, over a finite field \(\mathbb{F}\) and two quadratic transformations \(F=(f_{1},\ldots f_{m})\), \(\overline{F}=(g_{1},\ldots,g_{m})\). Each \(f_{i},g_{i}\) is a quadratic polynomial. \(F\) and \(\overline{F}\) are isomorphic if there are \(S:\mathbb{F}^{m}\to\mathbb{F}^{m}\) and \(T:\mathbb{F}^{n}\to\mathbb{F}^{n}\) such that \(\overline{F}=S\circ F\circ T\). The composition of affine transformations is itself an affine transformation. Thus, the composition of isomorphisms can be defined as straightforward. The original scheme considers two affine transformations \(S,T\), but a simplification which consists of discarding one of them (or equivalently, setting a transformation as the identity) leads to defining the IP on one or two secrets (IP1s and IP2s correspondingly). The proposed authentication scheme is very similar to that defined for GI. Both IP1s and IP2s have been considered for a new brand of cryptographic primitives known as multivariate cryptography [15; 16]. Theses primitives are based on the \(\mathcal{MQ}\) problem, which consists of finding a common solution of a set of polynomials in several variables in a given vector space (commonly, over a finite field \(\mathbb{F}_{q}\)). A traditional procedure for key generation in multivariate public key cryptography (MPKC) involves two major phases:  
* Private key generation. A set of polynomials \(F=\{f_{1},\ldots,f_{m}\}\) is generated in such a way that the problem of finding a common root for every \(f_{i}\) is easy. * Public keys derivation. From the private key polynomial set \(F\), we generate a new polynomial set \(\overline{F}=\{\overline{f}_{1},\ldots,\overline{f}_{n}\}\). For this set, the problem of finding a common root must be computationally difficult. Otherwise, a malicious entity would be able to perform sensitive operations, like deciphering and digital signing. The most common construction techniques base their security in the intractability of IP; for this, the affine transformations \(S\) and \(T\) must be kept in secrecy since the recovery of the private polynomial set with knowledge of the affine transforms is a computationally easy task. Further methods for private key generation can be found in [17]. The origins of MPKC can be traced back to the scheme proposed by [PERSON] and [PERSON] in [15; 16]. The proposed cryptosystem (known as the Matsumoto-Imai (IM) cryptosystem) was broken a few years later [18]. Since then, many other families of schemes have been proposed, including the unbalanced oil-vinegar (UOV) [19], the hidden field equations (HFE) [14], and the Rainbow [20] schemes. Currently, the National Institute of Standards and Technology is working on the development of quantum-resistant cryptographic standards, many of them based on MPKC [21]. The rapid development of MPKC has also caused advances in algorithms for solving multivariate systems. These provide very useful cryptanalytic attacks that, according to the target, can be classified into two main groups:  
* Ciphertext decryption. In this case the primary goal is to get the original plaintext from the captured ciphertext. These attacks make use of polynomial system solvers such as the Buchberger algorithm [22] to compute Groebner bases. On each new ciphertext obtained, the algorithm must be executed. * Private key recovery. The private key consists of the private set \(F\) and the transformations \(S_{1},S_{2}\). If this information is disclosed, every ciphertext ciphered with the disclosed key is vulnerable. Examples of these algorithms are: high rank, MinRank, and separation of oil and vinegar [23], VI.5.4. Up till now, the most reliable algorithms for solving general polynomial systems have been those based on the Buchberger algorithm, which has an exponential running time [22], even for the average case.