Luk Bettale
email: l.bettale@oberthur.com

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Ludovic Perret
email: ludovic.perret@lip6.fr

Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic

Keywords: Hidden Field Equations, MinRank, Gröbner bases

We investigate in this paper the security of HFE and Multi-HFE schemes as well as their minus and embedding variants. Multi-HFE is a generalization of the well-known HFE schemes. The idea is to use a multivariate quadratic system -instead of a univariate polynomial in HFE -over an extension field as a private key. According to the authors, this should make the classical direct algebraic (message-recovery) attack proposed by Faugère and Joux on HFE no longer efficient against Multi-HFE. We consider here the hardness of the key-recovery in Multi-HFE and its variants, but also in HFE (both for odd and even characteristic). We first improve and generalize the basic key recovery proposed by Kipnis and Shamir on HFE. To do so, we express this attack as matrix/vector operations. In one hand, this permits to improve the basic Kipnis-Shamir (KS) attack on HFE. On the other hand, this allows to generalize the attack on Multi-HFE. Due to its structure, we prove that a Multi-HFE scheme has much more equivalent keys than a basic HFE. This induces a structural weakness which can be exploited to adapt the KS attack against classical modifiers of multivariate schemes such as minus and embedding. Along the way, we discovered that the KS attack as initially described cannot be applied against HFE in characteristic 2. We have then strongly revised KS in characteristic 2 to make it work. In all cases, the cost of our attacks is related to the complexity of solving MinRank. Thanks to recent complexity results on this problem, we prove that our attack is polynomial in the degree of the extension field for all possible practical settings used in HFE and Multi-HFE. This makes then Multi-HFE less secure than basic HFE for equally-sized keys. As a proof of concept, we have been able to practically break the most conservative proposed parameters of multi-HFE in few days (256 bits security broken in 9 days).

Introduction

The problem of finding a low rank linear combination of matrices is a basic linear algebra problem [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] known as MinRank in cryptography [START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]. This problem is NP-hard [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] and was used to design a zero-knowledge authentication scheme [START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]. More generally, it appears that MinRank is underlying the security of several cryptographic schemes [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF][START_REF] Courtois | Cryptanalysis of the TTM cryptosystem[END_REF]. A well known example is the key recovery attack of the multivariate scheme HFE [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF] (Hidden Field Equations) proposed by Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] who showed that the security of HFE can be reduced to the difficulty of MinRank. Their technique is usually called Kipnis-Shamir's attack, or KS attack. They also proposed a general algorithm to solve MinRank. The idea is to map an instance of MinRank to an algebraic system. They then proposed an "ad-hoc" technique to solve such polynomial systems.

Later, Faugère, Levy-dit-Vehel and Perret [START_REF] Faugère | Cryptanalysis of MinRank[END_REF] improve Kipnis-Shamir's attack by using Gröbner bases [START_REF] Buchberger | Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal[END_REF][START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF][START_REF] Buchberger | Comments on the translation of my phd thesis[END_REF] techniques. In particular, they noticed that the system arising in Kipnis-Shamir's attack has a very specific structure: it is "bilinear". This means that each equation of the system is the product of linear forms with distinct variables. Soon after, Faugère, Safey El Din and Spaenlehauer [START_REF] Faugère | Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity[END_REF] presented a detailed study of the complexity of solving bilinear systems with Gröbner bases. In particular, [START_REF] Faugère | Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity[END_REF] proved that (generic or random) bilinear systems are much easier to solve than (generic) algebraic systems of the same size.

However, it seems reasonable to believe that polynomial systems occurring in cryptographic applications (such as in MinRank) are likely not generic; motivating then a dedicated analysis for important cases. In [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF], MinRank instances occurring in authentication schemes have been further studied. In this paper, we consider instances of MinRank occurring in the cryptanalysis of multivariate public-key schemes.

Multivariate Public-Key Cryptography (MPKC) is the set of asymmetric schemes using the NP-hardness of solving a quadratic system of multivariate algebraic equations [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Multivariate schemes are often considered as possible "low-cost" alternatives [START_REF] Nguyen | New trends in cryptology, european project "stork: Strategic roadmap for advances in cryptology -crypto[END_REF] to number theory based public key schemes. Their encryption/decryption procedures are very efficient and can be done in constrained environments [START_REF] Bogdanov | Time-area optimized public-key engines: MQcryptosystems as replacement for elliptic curves?[END_REF]13]. The main drawback is that the public key is rather large. Indeed, the one-way function is defined by a set of m quadratic polynomials (g 1 (x 1 , . . . , x n ), . . . , g m (x 1 , . . . , x n )) ∈ K[x 1 , . . . , x n ] m . Namely, the public operation is the application

G : (v 1 , . . . , v n ) ∈ K n → (g 1 (v 1 , . . . , v n ), . . . , g m (v 1 , . . . , v n )) ∈ K m .
To introduce a trapdoor, we choose a transformation F given by a system of algebraic equations ( f 1 , . . . , f m ) ∈ K[x 1 , . . . , x n ] m . Thanks to a well chosen structure, the system is easy to solve. Let GL n (K) be the group of invertible linear transformations and let Aff n (K) ≃ GL n (K) × K n be the group of invertible affine transformations. This structure is hidden by two affine transformations S ∈ Aff n (K) and T ∈ Aff m (K) represented by matrices S and T. The public key is then:

G = T • F • S (g 1 , .
. . , g m ) = ( f 1 ((x 1 , . . . , x n ) S) , . . . , f m ((x 1 , . . . , x n ) S)) T.

In such schemes, the transformations S , T and (usually) F are kept secret and G is made public.

To encrypt a message m = (m 1 , . . . , m n ) ∈ K n , we compute:

c = (c 1 , . . . , c m ) = (g 1 (m 1 , . . . , m n ), . . . , g m (m 1 , . . . , m n )) ∈ K m .
To decrypt, the owner of the secret key inverts separately each component. As S , T and F are easy to invert, this is done efficiently. The first multivariate scheme C* was introduced by Matsumoto and Imai [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[END_REF] and broken by Patarin [START_REF] Patarin | Cryptoanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88[END_REF]. After that, several trapdoor functions were proposed in this framework [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF][START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF][START_REF] Moh | A public key system with signature and master key functions[END_REF][START_REF] Wang | Tractable rational map signature[END_REF]. HFE probably remains the most famous one. In this paper we focus on the HFE and Multi-HFE structure introduced in [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF][START_REF] Billet | Analysis of Intermediate Field Systems[END_REF][START_REF] Chen | Odd-char multivariate Hidden Field Equations[END_REF].

In the original HFE [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF], the secret inner system is the representation of a univariate polynomial over some extension of degree n ∈ N of a finite field F q . This polynomial is chosen to be easy to solve (low degree) and has a special structure that allows to have only quadratic polynomials in its (multivariate) small field representation. A practical message recovery attack [START_REF] Faugère | Algebraic cryptanalysis of HFE using Gröbner bases[END_REF][START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF] and a theoretical key recovery [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] undermined the security of this scheme. To tackle these attacks, a generalization of HFE that uses a system of N equations in N variables (instead of one univariate polynomial) in an extension field of degree d has been proposed in [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF] and in [13]. In this paper, we call this construction Multi-HFE. The basic HFE scheme is then an instantiation of Multi-HFE with N = 1, d = n.

Main results

First, we propose an improved key recovery attack against HFE in odd-characteristic. To do so, we have improved and adapted the "classical" Kipnis-Shamir (KS) attack [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF]. The KS attack reduces to a MinRank over F q n related to the public key. In contrast to the KS attack, we show that the MinRank can be expressed in the small field and directly on the quadratic forms of the public key (g 1 , . . . , g n ) ∈ F q [x 1 , . . . , x n ] n . This allows to considerably speed up the solving step (for instance we have a speedup factor of 424 for q = 31 and n = 19) and also simplifies the KS attack. Due to its simpler description, we are able to generalize our attack to Multi-HFE (N > 1) in oddcharacteristic. These results were first published in [START_REF] Bettale | Cryptanalysis of multivariate and odd-characteristic hfe variants[END_REF] and concern only odd-characteristic fields. In characteristic 2, there is no symmetric quadratic form representing a quadratic polynomial, and contrary to what was stated in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF], the KS attack does not work as initially described (more specifically the second part of the attack given in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF]). Using the specificity of the problem in characteristic 2 and the possibility to add the field equations, we give two methods for adapting our attack in characteristic 2 depending on the parity of the target rank of the MinRank. Note that our adaptation applies to both for HFE and Multi-HFE.

The MinRank problems which occur here are very specific. First, a certain degree of freedom is left for its solving. This is related to a large amount of equivalent keys in HFE/Multi-HFE. We isolated two kind of transformations allowing to build equivalent keys. These transformations generalize those given in [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF]47] for HFE. We show that an equivalent key has a canonical representation in terms of these transformations. As a direct consequence, we give a lower bound on the number of equivalent keys for Multi-HFE, more precise than the one given in [START_REF] Bettale | Cryptanalysis of multivariate and odd-characteristic hfe variants[END_REF]. Second, the MinRank considered are greatly over-determined. Thanks to recent results on Min-Rank [START_REF] Faugère | Cryptanalysis of MinRank[END_REF][START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF], bilinear systems [START_REF] Faugère | Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity[END_REF] and a new expression of the Hilbert function using orthogonal polynomials, we provide a precise complexity analysis of our attack. For all proposed parameter sets, we prove that the attack is polynomial in d, the degree of the extension and linear in log(q), just as we conjectured in [START_REF] Bettale | Cryptanalysis of multivariate and odd-characteristic hfe variants[END_REF].

Another consequence of equivalent keys is the possibility to attack two variants of Multi-HFE, namely Multi-HFE -and Multi-HFE with embedding. In Multi-HFE -, several polynomials are removed from the public keys. We show that only (n -N) matrices are needed to solve the MinRank problem instead of n. These N degrees of freedom in the MinRank problem allow to perform our key recovery with no additional cost as the rank property still holds as long as the number of removed equations does not exceed N. For the embedding variant, the public polynomials have less variables leading to matrices with fewer rows and columns. However, a low rank linear combination of the quadratic forms can still be found. In this case, the matrix S (corresponding to the change of variable) recovered is rectangular. In order to make it invertible, we need to extend this matrix in a special way to keep the shape of F unchanged.

All in all, for the same size of keys, the Multi-HFE family seems to be less secure than the original HFE (N = 1). As a proof of concept, we provide a practical key recovery on the most conservative parameters (256-bit security) proposed in [START_REF] Chen | Odd-char multivariate Hidden Field Equations[END_REF] in less than 10 days.

Organization of the Paper

The paper is organized as follows. After this introduction, we present in Sect. 2 the necessary material regarding the MinRank problem and the algorithmic tools to solve it. We also review previous known attacks against HFE, and more particularly the KS attack on which ours is based. Section 3 is devoted to the presentation of our key recovery attack on both HFE and Multi-HFE. Equivalent keys are an important feature for our attack. They are discussed in Sect. [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] and the consequences are presented in Sect. 5. We use the degrees of freedom induced by equivalent keys to enhance the solving step by fixing some variables. After that, we unroll our attack on an example in Sect. [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF]. In this section, we also describe how to adapt our attack in characteristic 2. The complexity analysis of our attack is given in Sect. 7, and in Sect. 8 we devise how to extend our attack for the minus and the embedding variants of HFE/Multi-HFE. Finally, as a conclusion we show in Sect. 9 that Multi-HFE is less secure than HFE.

Preliminaries

Let K be a field. Throughout this paper, we use the following conventions: an underlined letter denotes a vector, e.g. v = (v 1 , . . . , v n ) ∈ K n . A capital bold font letter denotes a matrix, e.g. M ∈ M n×n (K) where M n×n (K) denotes the set of n × n matrices whose entries lie in K. We also write M = [m i, j ] to denote that the (i, j)-th coefficient of the matrix M is m i, j ∈ K for 0 i, j < n. We will also indifferently use ker (M) to denote the left kernel of M or (more often) a matrix whose rows form a basis of its left kernel. A calligraphic capital letter denotes a general mapping, e.g. F . The set of invertible matrices of M n×n (K) is denoted by GL n (K). The group of affine invertible transformations is denoted by Aff n (K) ≃ GL n (K) × K n .

Multi-HFE

The parameters considered are (q, N, d, D) ∈ N 4 . Here, q denotes the size of the ground field F q , d is the degree of the extension field F q d , N is the number of variables and equations of the secret polynomials in the ring F q d [X 1 , . . . , X N ], and D their degree. In the rest of the paper, we use capital letters for elements relative to the extension F q d (a.k.a. "big field" in this paper), e.g.

V i ∈ F q d , F i ∈ F q d [X 1 , . . . , X N ],
and small letters for elements relative to F q (a.k.a. "small field"), e.g. v i ∈ F q , f i ∈ F q [x 1 , . . . , x n ]. To build the trapdoor function F , we use the following transformation over the big field

F * : (V 1 , . . . ,V N ) ∈ (F q d ) N → (F 1 (V 1 , . . . ,V N ), . . . , F N (V 1 , . . . ,V N )) ∈ (F q d ) N with F k ∈ F q d [X 1 , . . . , X N ],
∀k, 1 k N, and deg (F i ) D. In addition, the polynomials F 1 , . . . , F N are constructed in a specific way. For all k, 1 k N:

F k = ∑ 1 i j N ∑ 0 u,v<d q u +q v D A k,i,u, j,v X q u i X q v j + ∑ 1 i N ∑ 0 u<d q u D B k,i,u X q u i +C k , where A k,i,u, j,v , B k,i,u ,C k ∈ F q d , ∀i, j, 1 i, j N, ∀u, v, 0 u, v < d.
From now on, we say that such systems have (multi-)HFE-shape. For convenience, we denote n = N d. Let ϕ N be a morphism from (F q d ) N to F n q . The transformation F uses the small field representation of the secret polynomials,

F = ϕ N • F * • ϕ -1 N with F : (v 1 , . . . , v n ) ∈ F n q → (h 1 (v 1 , . . . , v n ), . . . , h n (v 1 , . . . , v n )) ∈ F n q .
Due to the HFE-shape, each polynomial h i , for i, 1 i n has total degree 2.

The original HFE scheme [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF] is mostly used over F 2 and always with a single univariate polynomial as a secret map. It is then an instantiation of multi-HFE with q = 2 and N = 1. The construction PHFE [START_REF] Ding | Algebraic attack on HFE revisited[END_REF] (for projected HFE) is an odd characteristic univariate HFE that uses the embedding modifier (see Sect. 8.2). The scheme IFS [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF] (for Intermediate Field System) is a multi-HFE in characteristic 2 and THFE [START_REF] Chen | Odd-char multivariate Hidden Field Equations[END_REF] is a multi-HFE in odd characteristic (possibly with embedding modifier). To make the decryption efficient, all instances of multi-HFE with N > 1 use quadratic polynomials as internal secret transformations. In Table 1, we provide sample of parameters from the literature. We briefly review known attacks against HFE/multi-HFE.

Direct Algebraic Attack

Let (c 1 , . . . , c n ) ∈ F n q be a ciphertext. A message-recovery attack in a multivariate scheme reduces to solving a system of quadratic equations, i.e. {g 1c 1 = 0, . . . , g nc n = 0}, where the g i 's are the public polynomials. A classical way to solve algebraic systems is to compute a Gröbner basis [START_REF] Buchberger | Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal[END_REF][START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF][START_REF] Buchberger | Comments on the translation of my phd thesis[END_REF][START_REF] Adams | An Introduction to Gröbner Bases[END_REF][START_REF] Cox | A probabilistic remark on algebraic program testing[END_REF]. The historical method for computing such bases has been proposed by Buchberger in his PhD thesis [START_REF] Buchberger | Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal[END_REF]. The algorithms F 4 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF] and F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] by Faugère permit to improve the basic Buchberger's algorithm. A good measure of the complexity for Gröbner bases is the so-called "degree of regularity" of a system. This can be viewed as the maximum degree of the polynomials appearing during the computation (see [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semiregular polynomial systems[END_REF]).

It appeared [START_REF] Faugère | Algebraic cryptanalysis of HFE using Gröbner bases[END_REF][START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF] that inverting the public key of the original HFE is much easier than expected (i.e. in comparison to a random system of the same size). For original HFE, the degree of regularity has been experimentally shown to be roughly log q (D) (see [START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF]). This makes the attack sub-exponential in the number of variables. Further analysis [33] confirmed this result. Note that the field equations (i.e. x q 1x 1 = . . . = x q nx n = 0) are mandatory to achieve this complexity. Their role is to force the solutions to be only in the base field F q . To prevent a direct algebraic attack, it has been proposed [START_REF] Ding | Algebraic attack on HFE revisited[END_REF] to use a field with a bigger characteristic. During the Gröbner basis computation, field equations only intervene in degree at least q. Note that the hybrid approach described in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] has been especially designed to solve such systems (for "intermediate" fields). As an example, for n = 28 and q = 31 the complexity of the hybrid approach is 2 82 . It is better than a direct solving (2 115 ) but the attack remains impractical.

More specifically, a HFE system with q > n is very hard to solve with a direct approach such as in [START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF] (for n sufficiently big). This intuition has been recently confirmed in [START_REF] Dubois | The degree of regularity of HFE systems[END_REF] where the authors extend the analysis of [33] for all fields. After this, [START_REF] Ding | Inverting hfe systems is quasi-polynomial for all fields[END_REF] produces an explicit bound on the degree of regularity which is

(q -1)⌈log (D)⌉ 2 + 2.
We remark that this bound is linear in q. This makes the cost of a direct Gröbner basis computation exponential in q and then useless for a big enough field. For example, HFE with parameters q = 23, D = 1058 and n = 120, the (upper) bound on the degree of regularity according to [START_REF] Ding | Inverting hfe systems is quasi-polynomial for all fields[END_REF] is 35. The corresponding cost for mounting a direct message-recovery attack is then 2 242 operations. For a comparison, the key-recovery attack presented in this paper will need 2 28 operations for the same parameters.

For multi-HFE, there are less results. In characteristic 2, multi-HFE can still be attacked similarly to HFE as pointed in [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF]. This confirms that the algebraic attack is somehow "optimal" over F 2 . However, as for basic HFE, the direct algebraic attack does not affect instantiations of multi-HFE with bigger odd characteristic.

Original Kipnis-Shamir Attack

We now describe the key recovery attack proposed in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] against the original HFE scheme (N = 1, n = d). The starting idea is to remark that the polynomials of the public key -as well as the transformations S , T -can be viewed as mappings G * , S * , T * : F q n → F q n and represented by the univariate polynomials G, S, T ∈ F q n [X] respectively. The public key relation then becomes [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] proposed interpolation to recover a univariate representation of the public key. We present a more efficient and simpler way in Sect. 3 to perform this step.

G = G * (X) = T * (F * (S * (X))).

Kipnis and Shamir

Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] also showed that the univariate polynomials can be written as "non-standard quadratic forms". For instance, we have:

G = n-1 ∑ i=0 n-1
∑ j=0 g i, j X q i +q j = XGX t , where X = (X, X q , . . . , X q n-1 ) and G = [g i, j ] ∈ M n×n (F q n ). Note that this representation does not work in characteristic 2. In this section and in Sect. 3, we assume then that q is odd. The characteristic 2 case is addressed in Sect. 6.3. Similarly, we define F = [ f i, j ] ∈ M n×n (F q n ) as the symmetric matrix representation of the secret univariate polynomial.

The Kipnis-Shamir attack is based on the remark that the rank of F is bounded, namely Rank F log q (D). Indeed, the degree of the secret polynomial is smaller than D and the entries f i, j in F are non-zero only if i, j log q (D). In addition, we write T * -1 (X) = ∑ n-1 k=0 t k X q k and S * (X) = ∑ n-1 k=0 s k X q k . The equation G * (X) = T * (F * (S * (X))) implies the so-called "Fundamental Equation" (see [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] for the proof):

n-1 ∑ k=0 t k G * k = G ′ = WF W t , (1)
where W = [ w i, j ] ∈ M n×n (F q n ) is a specified invertible matrix such that w i, j = s q i ( j-i) mod n , for all i, j, 0 i, j < n. Finally, for a given k, 0 k < n, G * k is the matrix whose (i, j)-th entry is g q k (i-k) mod n,( j-k) mod n , for all i, j, 0 i, j < n. As the rank of F is bounded, so is the rank of G ′ . Recovering the t k 's reduces to solve a MinRank problem.

Once the t k 's of (1) are known, the s k 's are recovered by solving a linear system. From (1), we see that ker(G ′ ) = ker( WF) and thus ker(G ′ ) W = ker(F). Let ℓ = ⌈log q (D)⌉, we recall that only the upper left ℓ × ℓ submatrix of F has non-zero coefficients. Thus, any (n -ℓ) × n matrix K whose first ℓ columns are 0 ensures KF = 0. Furthermore, if Rank(F) = ℓ and the rows of K are chosen linearly independent, then their rows form a basis of ker(F).

In any case, this is enough to ensure that the ℓ first columns of ker(G ′ ) W are zero. This gives rise to a linear system over F q n of ℓ (n -ℓ) equations in the n 2 coefficients of W. In addition, W has the following shape:

W =           
w 0,0 w 0,1 . . . . . . w 0,n-2 w 0,n-1 w q 0,n-1 w q 0,0 w q 0,1 . . . . . . w q n-2 0,n-2 w q n-2 0,n-1 w q n-2 0,0

w q n-2 0,1 w q n-1 0,1 . . . . . . w q n-1 0,n-2 w q n-1 0,n-1 w q n-1 0,0           
. This is due to the fact that w i+1, j+1 = s q i+1 ( j+1)-(i+1) = s q i ( j-i) q = w q i, j . Thus, Kipnis and Shamir proposed to reinterpret the equations over F q . This gives n ℓ (n -ℓ) equations in only n 2 variables over F q . Solving this overdetermined system completes the key recovery. The main (and more difficult) part of the attack is to solve the so-called MinRank problem. In the next section, we present the problem as well as the tools to solve it.

The MinRank Problem

The (square) MinRank problem over a finite field K is defined as follows:

MinRank (MR) Input: n, r, k ∈ N and M 0 , M 1 , . . . , M k ∈ M n×n (K). Question: Find -if any -a k-tuple (λ 1 , . . . , λ k ) ∈ K k such that: Rank k ∑ i=1 λ i M i -M 0 r.
We review below known algebraic techniques to solve this problem.

Kipnis-Shamir Modeling

Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] proposed to formulate MinRank as a multivariate polynomial system of equations. With the previous notations, solving MinRank over a finite field K is equivalent to solving the algebraic system of n (nr) equations in r (nr) + k variables given by the entries of the matrix   

1 x 1,1 . . . x 1,r . . . . . . . . . 1 x n-r,1 . . . x n-r,r    • k ∑ i=1 λ i M i -M 0 .
Solving this system is equivalent to find a left kernel (in echelon form) of ∑ k i=1 λ i M i -M 0 . This left kernel can be written in such a systematic form with high probability over a finite field. Initially, relinearization [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] has been used to solve this algebraic system. The authors of [START_REF] Faugère | Cryptanalysis of MinRank[END_REF] proposed instead to use Gröbner bases tools to solve this system. In addition, [START_REF] Faugère | Cryptanalysis of MinRank[END_REF] noticed that the system has a specific structure: it is formed by bilinear equations [START_REF] Faugère | Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity[END_REF].

Minors Modeling

Alternatively, MinRank is equivalent to finding a vector (λ 1 , . . . , λ k ) ∈ K k vanishing on all the minors of size r + 1 of the matrix ∑ k i=1 λ i M i -M 0 are zero. We have then to solve a multivariate polynomial system of n r+1 2 equations in k variables as pointed in [START_REF] Faugère | Cryptanalysis of MinRank[END_REF][START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF]. The system has more equations and less variables than the Kipnis-Shamir modeling but the degree of the equations is r. However, it seems that this approach is more efficient [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] (at least for MinRank instances used in the authentication scheme [START_REF] Courtois | Efficient zero-knowledge authentication based on a linear algebra problem MinRank[END_REF]). In addition, precise complexity bounds can be derived for this modeling [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF].

Complexity.

We recall the complexity of the F 5 algorithm as given in [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semiregular polynomial systems[END_REF].

Theorem 1

The complexity of computing a Gröbner basis of a zero-dimensional (i.e. with a finite number of solutions in the algebraic closure of the coefficient field) polynomial system of m equations in n variables with F 5 is

O n + d reg d reg ω ,
where d reg is the degree of regularity of the ideal and 2 ω 3 the linear algebra constant.

Informally, d reg is the maximum degree reached during a Gröbner basis computation. For random instances of square (m = n) quadratic systems, it holds that d reg = n + 1 (see [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]). It has to be noticed that if the degree of regularity does not depend on the number of variables, the complexity then becomes polynomial in n.

We consider now MinRank systems obtained by the minors modeling. Corollary 3 of [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] gives a bound on the degree of regularity of these particular systems.

Proposition 1 (Faugère, Safey El Din, Spaenlehauer [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF]) Let (n, r, k) be the parameters of a MinRank instance. Let A(t) = [a i, j (t)] be the (r × r)-matrix defined by a i, j (t) = ∑ n-max(i, j) ℓ=0

n-i ℓ n-j ℓ t ℓ .
The degree of regularity of MinRank polynomial systems is bounded from above by 1 + deg (HS(t)) where HS(t) is the polynomial obtained from the first positive terms of the series

(1 -t) (n-r) 2 -k det A(t) t ( r 2 )
.

As explained in [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF], the proof is valid under the assumption that a variant of the Fröberg conjecture [31] is true. More recently [START_REF] Faugère | On the complexity of the generalized minrank problem, preprint 31[END_REF], the same result was proved when k ≥ (nr) 2 without using any variant of Fröberg's conjecture. However, in the overdetermined case (that is to say when k < (nr) 2 ) the conjecture is still needed.

The Fröberg conjecture states that some property (the rank of some linear map is maximal) holds on a Zariski open subset O when the characteristic of K is 0. Hence, we can find a polynomial h(a) in Z[a] which does not depend on the field K such that h(a) = 0 ⇒ a ∈ O. When K is a finite field the notion of Zariski open set is meaningless but the following lemma can be used:

Lemma 1 (Schwartz, Zippel, DeMillo, Lipton [18, 48, 42]) Let K be a field and P ∈ K[x 1 , . . . , x n ] be a nonzero polynomial. Select r 1 , . . . , r n uniformly at random from a finite subset X of K. Then, the probability that P(r 1 , . . . , r n ) = 0 is less than deg(P)/|X |.

The lemma states that if we choose uniformly at random in F q the coefficient of the polynomials occuring in the Fröberg conjecture then the probability that h(a) = 0 is upper bounded by deg(h)/q and therefore tends to 0 when q goes to infinity. This means that if the Fröberg conjecture is true in characteristic 0 then it is also true over F q with a good probability when q is big enough. In addition, the Fröberg conjecture (even over F 2 ) is well supported by computer experiments. Note that the bound given by Proposition 1 is also an upper bound for the degree of regularity of the Kipnis-Shamir modeling [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF]. In Sect. 7, we will see that Proposition 1 is useful to bound the complexity of MinRank problems coming from HFE/multi-HFE.

Improvement and Generalization of the MinRank Attack

To generalize the MinRank attack proposed by Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF], it is convenient to interpret it as matrix/vector operations. In what follows, we denote by Frob k the function raising all the components of a vector (or a matrix) to the power q k in any field K of characteristic q. For example, for a vector

v = (v 1 , . . . , v m ) ∈ K m , we have Frob k (v) = (v q k 1 , . . . , v q k m ) ∈ K m . For a matrix A = [a i, j ] ∈ M n×n (K), we have Frob k (A) = [a q k i, j ] ∈ M n×n (K).
In this section, we will suppose that the characteristic of the field F q is different than two. This particular case is addressed in Sect. 6.3.

Improving the Univariate Case

To express the KS attack as matrix/vector operation, we introduce the following change of basis matrix.

Proposition 2 Let (θ 1 , . . . , θ n ) ∈ (F q n ) n be a vector basis of F q n over F q and M n ∈ M n×n (F q n ) be the matrix whose columns are the Frobenius powers of the basis elements, i.e.:

M n =        θ 1 θ q 1 . . . θ q n-1 1 θ 2 θ q 2 . . . . . . . . . . . . θ n θ q n . . . θ q n-1 n       
.

We can express the morphism ϕ 1 : F q n → F n q as V → (V,V q , . . . ,V q n-1 ) M -1 n and its inverse ϕ -1 1 : [START_REF] Adams | An Introduction to Gröbner Bases[END_REF] denoting the first component of the vector (v 1 , . . . , v n ) M n . More generally, we have

F n q → F q n as (v 1 , . . . , v n ) → (v 1 , . . . , v n ) M n [1], (v 1 , . . . , v n ) M n
(v 1 , . . . , v n ) M n = (V,V q , . . . ,V q n-1 ). Proof Let (v 1 , . . . , v n ) ∈ F n q be the decomposition of V ∈ F q n as a vector in F n q . That is, V = ∑ n i=1 v i θ i ∈ F q n . By construction: (v 1 , . . . , v n ) M n = n ∑ i=1 v i θ q 0 i , . . . , n ∑ i=1 v i θ q n-1 i =   n ∑ i=1 v i θ i q 0 , . . . , n ∑ i=1 v i θ i q n-1   = V q 0 , . . . ,V q n-1 .
As a consequence:

ϕ -1 1 (v 1 , . . . , v n ) = (v 1 , . . . , v n ) M n [1] = V.
M n being invertible, we have for ϕ 1 :

V q 0 , . . . ,V q n-1 = (v 1 , . . . , v n ) M n V q 0 , . . . ,V q n-1 M -1 n = (v 1 , . . . , v n ) = ϕ 1 (V ).

⊓ ⊔

The matrix M n allows to go back and forth from the big field F q n to the vector-space F n q . It can be used to compute the univariate representation of the public key in a simpler way than in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF]. Namely, we replace interpolation by a matrix multiplication. For the sake of simplicity, we consider from now on only linear transformations and homogeneous polynomials. This is not a restriction since what follows can easily be adapted to the affine case (as already pointed in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF]).

Let F * k ∈ M n×n F q d be the matrix whose (i, j)-th entry is f q k i-k, j-k (indexes are modulo n). The matrix F * k is in fact the "matrix representation" of the q k -th power of the univariate polynomial F. Indeed, since F = ∑ n-1 i=0 ∑ n-1 j=0 f i, j X q i +q j , we have

F q k = n-1 ∑ i=0 n-1 ∑ j=0 f i, j X q i +q j q k = n-1 ∑ i=0 n-1 ∑ j=0 f q k i, j X q i+k +q j+k = n-1+k ∑ i=k n-1+k ∑ j=k f q k i-k, j-k X q i +q j .
The sums can be divided as follows:

F q k = n-1 ∑ i=k n-1+k ∑ j=k f q k i-k, j-k X q i +q j + n-1+k ∑ i=n-1+1 n-1+k ∑ j=k f q k i-k, j-k X q i +q j F q k = n-1 ∑ i=k n-1 ∑ j=k f q k i-k, j-k X q i +q j + n-1+k ∑ j=n-1+1 f q k i-k, j-k X q i +q j + n-1+k ∑ i=n-1+1 n-1 ∑ j=k f q k i-k, j-k X q i +q j + n-1+k ∑ j=n-1+1 f q k i-k, j-k X q i +q j F q k = n-1 ∑ i=k n-1 ∑ j=k f q k i-k, j-k X q i +q j + k-1 ∑ j=0 f q k i-k,n+ j-k X q i +q n+ j + k-1 ∑ i=0 n-1 ∑ j=k f q k n+i-k, j-k X q n+i +q j + k-1 ∑ j=0 f q k n+i-k,n+ j-k X q n+i +q n+ j .
Remark that X q n = X. By reducing the indexes of f i, j modulo n, we get:

F q k = n-1 ∑ i=k n-1 ∑ j=k f q k i-k, j-k X q i +q j + k-1 ∑ j=0 f q k i-k, j-k X q i +q j + k-1 ∑ i=0 n-1 ∑ j=k f q k i-k, j-k X q i +q j + k-1 ∑ j=0 f q k i-k, j-k X q i +q j .
Grouping the sums back together, we obtain

F q k = n-1 ∑ i=0 n-1 ∑ j=0 f q k i-k, j-k X q i +q j = XF * k X t . (2)
Thanks to Proposition 2, we deduce a useful property on these matrices.

Lemma 2 Let M n ∈ M n×n (F q n ) be the matrix defined in Proposition 2. We consider also the symmetric matrices (H 1 , . . . , H n ) ∈ (M n×n (F q )) n associated to the secret quadratic polynomials in the small field (h 1 , . . . , h n ) ∈ F q [x 1 , . . . , x n ] n , i.e. h i = xH i x t for all i, 1 i n. It holds that:

(H 1 , . . . , H n ) = M n F * 0 M t n , . . . , M n F * n-1 M t n M -1 n .
Proof By construction, for all v = (v 1 , . . . , v n ) ∈ F n q :

(h 1 (v) , . . . ,

h n (v)) = ϕ 1 F ϕ -1 1 (v) .
Using the matrix definition of ϕ 1 , we express this relation as follows:

(h 1 (v) , . . . , h n (v)) = ϕ 1 (F (v M n )) = F q 0 (v M n ) , . . . , F q n-1 (v M n ) M -1 n .
We recall that the matrix representation of

F q k is F * k . Thus for all v ∈ F n q : v H 1 v t , . . . , v H n v t = v M n F * 0 M n t v t , . . . , v M n F * n-1 M t n v t M -1 n (H 1 , . . . , H n ) = M n F * 0 M n t , . . . , M n F * n-1 M t n M -1 n .

⊓ ⊔

We consider now the symmetric matrices (G 1 , . . . , G n ) ∈ (M n×n (F q )) n associated to the public polynomials (g 1 , . . . , g n ) ∈ F q [x 1 , . . . , x n ] n , i.e. g i = xG i x t for all i, 1 i n. We want to bind the public matrices G i in the small field to the secret matrix F in the big field. To do that, the equation G = T • F • S can also be interpreted as matrix/vector operations. Thanks to Lemma 2:

G (x) = T • F • S (x) (g 1 (x), . . . , g n (x)) = h 1 (x
(G 1 , . . . , G n ) = S M n F * 0 M t n S t , . . . , S M n F * n-1 M t n S t M -1 n T.
As T and M n are invertible, we have

(G 1 , . . . , G n ) T -1 M n = (SM n F * 0 M t n S t , . . . , SM n F * n-1 M t n S t ). (3)
In other words, we have a direct relation between the polynomials of the public key written as quadratic forms and the secret polynomial F or more precisely its matrices F * i , for all i, 0 i < n.

Notice that Equation (3) involves left products of a matrix with M n . This product has an interesting property.

Proposition 3 Let A = [a i, j ] ∈ M n×n (F q ), and B = [b i, j ] = A M n ∈ M n×n (F q n ). We have: b i, j = b q i, j-1
, for all i, j, 0 i, j < n. That is, each column is obtained from the previous one using a Frobenius application. As a consequence, the whole matrix B = [b i, j ] = A M n can be defined with any of its columns.

Proof Due to the definition of M n in Proposition 2, b i, j = ∑ n-1 k=0 a i,k θ q j k+1 , for all i, j, 0 i, j < n. Consequently:

b q i, j-1 = n-1 ∑ k=0 a i,k θ q j-1 k+1 q .
As a i, j ∈ F q (i.e. a q i, j = a i, j ) and since the Frobenius is linear, we get:

b q i, j-1 = n-1 ∑ k=0 a q i,k θ q j-1 k+1 q = n-1 ∑ k=0 a i,k θ q j k+1 = b i, j .

⊓ ⊔

From now on, we will write

T -1 M n = U = [u i, j ] ∈ M n×n (F q n ) and S M n = W = [w i, j ] ∈ M n×n (F q n ).
We then rewrite (3) as follows:

(G 1 , . . . , G n ) U = (WF * 0 W t , . . . , WF * n-1 W t ). (4
) According to Proposition 3, u i, j+1 = u q i, j and w i, j+1 = w q i, j , for all i, j, 0 i, j < n. Thus, we only need to know one column of U (resp. W) to recover the whole matrix. Let then (u 0,0 , . . . , u n-1,0 ) ∈ (F q n ) n be the components of the first column of U. We have:

n-1 ∑ k=0 u k,0 G k+1 = WF * 0 W t = WFW t . ( 5
)
The equation is similar to (1), but we have not used the univariate representation of G . Here again, as the rank of F is log q (D), so is the rank of WFW t . In contrast to the initial attack, the G i 's are the public matrices and not matrices whose coefficients are in the big field. In the other hand, the solution of such MinRank lies in (F q n ) n . This leads to the following theorem.

Theorem 2 For HFE, recovering

U = T -1 M n ∈ M n×n (F q n ) reduces to solve a MinRank with k = n and r = ⌈log q (D)⌉ on the public matrices (G 1 , . . . , G n ) ∈ M n×n (F q ) n
whose entries are in F q . The solutions (i.e. the linear combinations) of this MinRank are in

(F q n ) n .
Computing a Gröbner basis of a polynomial system whose coefficients are over a smaller field (F q instead of F q n ) is faster as the cost of arithmetic operations is decreased. The expected gain is a factor M(n) (the cost of the multiplication of two univariate polynomials of degree n) over the KS attack.

In Table 2, we compare the original KS MinRank attack and the new MinRank attack on HFE (N = 1) with parameters q = 31, D = 31 2 + 31 = 992.

Our attack allows a considerable speedup over the original KS attack. It makes it practical for a wide range of parameter whereas the original KS attack was considered theoretical. Another advantage of this new formulation is that it can be easily extended to Multi-HFE.

Table 2 Comparison between the original KS attack and the new attack on HFE (N = 1) with parameters q = 31, D = 31 2 + 31 = 992 using MAGMA [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.17-1) on a 2.93 GHz Intel R Xeon R CPU. The gain (ratio) is expected to be between n log n and n 2 .

n

Generalization to Multi-HFE

The Kipnis-Shamir attack uses the univariate representation of the public key. In multi-HFE, the degree of the univariate representation of the secret key is not bounded. This was in fact the initial motivation for the design of IFS [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF]. As a consequence, there is no linear combination of the G * k (notation as in ( 2)) leading to a small rank, making the MinRank attack impossible at first glance. The hidden field structure exists but it can only be unveiled by working in the right field. To have the correct analogy with the univariate case, we introduce a new change of basis between the "small" field vector space F n q and the "big" field vector space (F q d ) N . The whole idea of our generalization is to "expand" the concepts of Sect. 3.1 to N variables. We recall that n = N d. Hence, a n dimensional vector over the small field can be divided in N blocks of size d. Each such block represents an element in the big field (i.e F q d ) and has to be processed as in Sect. 3.1. The process is applied N times, once for each block. This leads to consider N different solutions of a MinRank problem. To this end, the matrix defined in Proposition 2 has to be expanded. Precisely, we consider block diagonal matrices as in the next proposition.

Proposition 4 Let (θ 1 , . . . , θ d ) ∈ (F q d ) d be a vector basis of F q d over F q . Let M d ∈ M d×d F q d be the matrix as defined in Proposition 2. We construct the matrix M N,d = Diag(M d , . . . , M d N ) ∈ M n×n (F q n ), namely M N,d =                        θ 1 θ q 1 . . . θ q d-1 1 θ 2 θ q 2 . . . θ q d-1 2 . . . . . . . . . . . . 0 θ d θ q d . . . θ q d-1 d . . . . . . . . . . . . . . . . . . θ 1 θ q 1 . . . θ q d-1 1 θ 2 θ q 2 . . . θ q d-1 2 0 . . . . . . . . . . . . θ d θ q d . . . θ q d-1 d                        .
We can express the morphism ϕ N :

(F q d ) N → F n q as (V 1 , . . . ,V N ) → (V 1 ,V q 1 , . . . ,V q d-1 1 , . . . . . . . . . ,V N ,V q N , . . . ,V q d-1 N ) M -1 N,d
and its inverse ϕ -1

N : F n q → (F q d ) N as (v 1 , . . . , v n ) → (W 1 ,W d+1 , . . . ,W d(N-1)+1 ) where (W 1 , . . . ,W n ) = (v 1 , . . . , v n ) M N,d .
Proof Once again, we recall that n = N d. Hence, a n dimensional vector (v 1 , . . . , v n ) ∈ F n q can be divided in N blocks of size d. Due to the construction of M N,d , each block of d elements in (v 1 , . . . , v n ) is multiplied by the matrix M d . Eventually, the matrix acts just as if we apply Proposition 2 to each of the N blocks of d elements. This is then a multi-dimensional extension of Proposition 2.

More formally, we define

V k = ∑ d i=1 v (k-1)d+i θ i for all k, 1 k N. That is, the k-th block of d components in (v 1 , . . . , v n ) ∈ F n q represents the k-th component of (V 1 , . . . ,V N ) ∈ (F q d ) N , for all k, 1 k N, i.e. ϕ N (V 1 , . . . ,V N ) = (ϕ 1 (V 1 ), . . . , ϕ 1 (V N )) = (v 1 , . . . , v n ). Let (W 1 , . . . ,W n ) = (v 1 , . . . , v n ) M N,d . We point out that the k-th block of d components of the vector (W 1 , . . . ,W n ) resp. (v 1 , . . . , v n )) is (W (k-1)d+1 , . . . ,W kd resp. (v (k-1)d+1 , . . . , v kd ) . Then, by construction of M N,d : (W (k-1)d+1 , . . . ,W kd ) = (v (k-1)d+1 , . . . , v kd ) M d , ∀k, 1 k N. From Proposition 2: (v (k-1)d+1 , . . . , v kd ) M d = (V q 0 k , . . . ,V q d-1 k ), ∀k, 1 k N.
By gathering all N blocks:

(W 1 , . . . ,W n ) = (V q 0 1 , . . . ,V q d-1 1 , . . . ,V q 0 N , . . . ,V q d-1 N ) (v 1 , . . . , v n ) M N,d = (V q 0 1 , . . . ,V q d-1 1 , . . . ,V q 0 N , . . . ,V q d-1 N
) .

This proves the proposition for ϕ -1 N . As M N,d is invertible, it also holds that

(V q 0 1 , . . . ,V q d-1 1 , . . . ,V q 0 N , . . . ,V q d-1 N ) M -1 N,d = (v 1 , . . . , v n ), which proves the proposition for ϕ N . ⊓ ⊔ Note that Proposition 4 indeed generalizes Proposition 2 since M 1,d = M d .
Using this definition for ϕ N , a non- standard representation of the secret polynomials -similar to the one of Kipnis-Shamir -can be introduced. For a multi-HFE shaped polynomial

F ∈ F q d [X 1 , . . . , X N ], this corresponds to the matrix F ∈ M n×n F q d such that F = XF X t where X = (X 1 , X q 1 , . . . , X q d-1 1 , . . . , X N , X q N , . . . , X q d-1 N
). We need now to generalize the F * k matrices used in Sect. 2.3.

Definition 1 Let F = [ f i, j ] ∈ M n×n F q d be the non-standard matrix representation of a HFE-shaped polynomial F ∈ F q d [X 1 , . . . , X N ].
We have n = Nd, and the matrix F can be divided in N × N blocks of size d × d. We denote then by F * d,k ∈ M n×n F q d the matrix obtained from F by rotating the rows and columns of each d × d blocks from k positions and raising each components to the power q k . That is, if we denote by F i, j the d × d block of F located at position (i, j), 0 i, j < N, we have:

F * d,k =    F * k 0,0 . . . F * k 0,N-1 . . . . . . F * k N-1,0 . . . F * k N-1,N-1    .
The definition generalizes the one of F * k . As in the univariate case the matrix F * d,k indeed represents the q k -th power of a polynomial in

F q d [X 1 , . . . , X N ]. Proposition 5 Let F ∈ F q d [X 1 , . . . , X N ] be a HFE-shaped polynomial and F = [ f i, j ] ∈ M n×n F q d be its non- standard matrix representation. F * d,k is the non-standard matrix representation of F q k .
To prove Proposition 5, one can remark that the block F i, j of the matrix F operates only on the variables X i+1 and X j+1 . To apply the Frobenius action to the whole polynomial F, it has to be applied to each of these blocks, leading to the shape of F * d,k . The precise proof can be found in Appendix B. Thanks to Proposition 5, equation ( 4) can be generalized for multi-HFE. To this end, we propose a multivariate version of Lemma 2. Namely:

Lemma 3 Let M N,d ∈ M n×n F q d be
the matrix defined in Proposition 4. Let F 1 , . . . , F N be the non-standard symmetric matrices representing the secret polynomials F 1 , . . . , F N , and F i * d,k be the matrices defined in Definition 1. Finally, we consider the symmetric matrices (H 1 , . . . , H n ) ∈ M n×n (F q )

n associated to the secret quadratic polynomials in the small field (h 1 , . . . ,

h n ) ∈ F q [x 1 , . . . , x n ] n , i.e. h i = xH i x t for all i, 1 i n. It holds that: (H 1 , . . . , H n ) = M N,d F 1 * d,0 M t N,d , . . . , M N,d F 1 * d,d-1 M t N,d , . . . . . . , M N,d F N * d,0 M t N,d , . . . , M N,d F N * d,d-1 M t N,d M -1 N,d .
Proof The proof is very similar to the proof of Lemma 2. We start from the definition of the small field polynomials

h 1 , . . . , h n . For all v ∈ F n q , (h 1 (v) , . . . , h n (v)) = ϕ N F 1 ϕ -1 N (v) , . . . , F N ϕ -1 N (v) .
Similarly, we need to express the above equation by matrix operations. We use then the definition of ϕ N and its inverse using the matrix M N,d of Proposition 4, (h

1 (v) , . . . , h n (v)) = F q 0 1 v M N,d , . . . , F q d-1 1 v M N,d , . . . , F q 0 N v M N,d , . . . , F q d-1 N v M N,d M -1 N,d .
Recall from Proposition 5 that F i * d, j is the matrix representation of F q j i , ∀i, 1 i N and ∀ j, 0 j < d. We replace the polynomials by their matrix expression and we get for all v ∈ F n q :

(v

H 1 v t , . . . , v H n v t ) = v M N,d F 1 * d,0 M t N,d v t , . . . , v M N,d F 1 * d,d-1 M t N,d v t , . . . . . . , v M N,d F N * d,0 M t N,d v t , . . . , v M N,d F N * d,d-1 M t N,d v t M -1 N,d , which concludes the proof. ⊓ ⊔ Now, let U = T -1 M N,d ∈ M n×n F q d , W = S M N,d ∈ M n×n F q d and F i ( j) = WF i * d, j W t , with i, 1 i N,
and j, 0 j < d. We have the relation:

G (x) = T • F • S (x), (g 1 (x), . . . , g n (x)) = h 1 (x S), . . . , h n (x S) T, x G 1 x t , . . . , x G n x t = x S H 1 S t x t , . . . , x S H n S t x t T, (G 1 , . . . , G n ) = S H 1 S t , . . . , S H n S t T.
Using Lemma 3:

(G 1 , . . . , G n ) = S M N,d F 1 * d,0 M t N,d S t , . . . , S M N,d F 1 * d,d-1 M t N,d S t , . . . . . . , S M N,d F N * d,0 M t N,d S t , . . . , S M N,d F N * d,d-1 M t N,d S t M -1 N,d T. ( 6
)
Matrices T and M N,d being invertible, we obtain:

(G 1 , . . . , G n ) T -1 M N,d = (F 1 (0) , . . . , F 1 (d-1) , . . . . . . , F N (0) , . . . , F N (d-1) ), (G 1 , . . . , G n ) U = (F 1 (0) , . . . , F 1 (d-1) , . . . . . . , F N (0) , . . . , F N (d-1) ). (7)
As in the univariate case, matrices U and W have a useful property.

Proposition 6 Let A = [a i, j ] ∈ M n×n (F q ), and B = [b i, j ] = A M N,d ∈ M n×n F q d . For all i, 0 i < n, k, 0 k < N and j, 0 j < d, we have: b i,k d+ j = b q i,k d+(( j-1) mod d) .

That is, for each group of d columns, one column is obtained from the previous one using a Frobenius application. Each group of d columns is defined by one of them, and consequently, the whole matrix is defined by N columns, one in each group.

The proof of Proposition 6 is similar to the proof of Proposition 3. The property comes from the fact that each group of d columns is processed by a matrix M d leading to a similar property as Proposition 3 for each group. The precise proof can be found in Appendix B.

To get the analogy with the MinRank in the univariate case, we remark that F i * d,0 = F i . By considering the (i d)-th columns of U for all i, 0 i < N we have

n-1 ∑ k=0 u k,0 G k+1 = WF 1 W t , . . . , n-1 ∑ k=0 u k,(N-1) d G k+1 = WF N W t . (8)
The following lemma allows to bind (8) to a MinRank problem.

Lemma 4 Let (F 1 , . . . , F N ) ∈ (F q d [X 1 , . . . , X N ]
) N be polynomials having Multi-HFE shape. For all k, 1 k N, let F k ∈ M n×n F q d be their non-standard symmetric matrix representation. Let D be the degree of each polynomial F k and ℓ = ⌈log q D⌉. For all k, 1 k N Rank (F k ) Nℓ.

Furthermore, let

K N,d,ℓ =       0 d-ℓ,ℓ I d-ℓ 0 d-ℓ,d . . . 0 d-ℓ,d 0 d-ℓ,d . . . . . . . . . . . . . . . . . . 0 d-ℓ,d 0 d-ℓ,d . . . 0 d-ℓ,d 0 d-ℓ,ℓ I d-ℓ       ∈ M n-Nℓ,n F q d where 0 d-ℓ,ℓ (resp. 0 d-ℓ,
F k =    A k 0,0 . . . A k 0,N-1 . . . . . . A k N-1,0 . . . A k N-1,N-1    where each block A k i, j is a d × d matrix A k i, j =              A i, j k,0,0 . . . A i,
            
for i, j, 0 i, j < N. As the consequence, the rank of such matrix F k is at most Nℓ.

From the construction of

K N,d,ℓ , it is clear that K N,d,ℓ F k = 0. As K N,d,ℓ has exactly N (d -ℓ) = (n -Nℓ) linearly independent rows, if Rank(F k ) is exactly Nℓ, which is the case with high probability, then K N,d,ℓ is a basis of the left kernel of F k . ⊓ ⊔
As in the univariate case, the problem of finding correct values for U turns out to be a MinRank problem.

Theorem 3 For multi-HFE, recovering

U = T -1 M N,d ∈ M n×n (F q n ) reduces to solve N times a MinRank problem with k = n and r = N log q (D) on the public matrices (G 1 , . . . , G n ) ∈ M n×n (F q ) n .
On the other hand, the solutions (i.e. the linear combinations) of each MinRank are in

F q d .
Proof The N MinRank solutions come from [START_REF] Bosma | The Magma algebra system I: The user language[END_REF]. From Lemma 4, the rank of F k is bounded by r = N⌈log q (D)⌉.

Since W is invertible, the rank of WF k W t is equal to the rank of F k for all k, 1 k N. From Proposition 6, knowing one column in each of the N sequences of d columns in U is enough to recover the whole matrix U. This allows to conclude the proof.

⊓ ⊔

Recovering the transformation T reduces to solving a MinRank problem. Recovering the other parts of a secret key reduces to solving linear systems. This will be discussed in Sect. [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF]. Before that, we study the effects of equivalent keys. This allows to better understand the MinRank arising in HFE/Multi-HFE as well as the other parts of the attack.

About Equivalent Keys and Induced Degrees of Freedom

Two secret keys are equivalent if they lead to the the same public key. The subject has already been treated for the original HFE [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF][START_REF] Wolf | Equivalent keys in HFE, C * , and variations[END_REF]47]. It has been shown that n q 2n (q n -1) 2 equivalent keys exist for HFE. This phenomena is even amplified for multi-HFE. In this section, we exploit this fact.

Definition 2 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 . We say that the key (F * ′ , S ′ , T ′ ) is an equivalent key if and only if F * ′ has HFE-shape, and

T ′ • ϕ N • F * ′ • ϕ -1 N • S ′ = G = T • ϕ N • F * • ϕ -1 N • S (same public key).
Wolf and Preneel [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF]47] introduced the notion of sustaining transformations which is a couple of affine transformations (A * , B * ) such that B * • F * • A * preserves the "shape" of F * . For HFE, the "big sustainer" (multiplication in the big field), the "additive sustainer" and the "Frobenius sustainer" keep the HFE-shape unchanged. In multi-HFE, multiplication keeps the HFE-shape. But, we also have any affine transformation on the N variables. Thus, the two first sustainers can be generalized as follows.

Proposition 7 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D). For any invertible affine transformations

(A * , B * ) ∈ Aff N (F q d ) × Aff N (F q d ), we set A = ϕ N • A * • ϕ -1 N and B = ϕ N • B * • ϕ -1 N . Then B * • F * • A * , A -1 • S , T • B -1
is an equivalent key.

Proof First, we show that B * • F * • A * has HFE-shape. This is due to the fact that the only exponents occurring in a variable X i is a power of q. The transformation A * mixes the variables X 1 , . . . , X N by affine combinations. By linearity of the Frobenius, no other exponents can appear and the system keeps its HFE-shape. Trivially, as B * only performs affine combinations of the polynomials F 1 , . . . , F N the shape is also unchanged. To conclude, we notice that

G = T • ϕ N • F * • ϕ -1 N • S G = T • ϕ N • B * -1 • ϕ -1 N • ϕ N • (B * • F * • A * ) • ϕ -1 N • ϕ N • A * -1 • ϕ -1 N • S G = T • B -1 • ϕ N • (B * • F * • A * ) • ϕ -1 N • A -1 • S .

⊓ ⊔

The following proposition provides the structure of a transformation used in Proposition 7 in the linear case (it has to be slightly adapted in the affine case).

Proposition 8 Let A * = [a i, j ] ∈ M N×N F q d be the matrix associated to a linear transformation A * over (F q d ) N . The transformation A * can be represented in the field F q as:

A = M N,d A * M -1 N,d ∈ M n×n (F q ) ,
where M N,d ∈ M n×n F q d is the matrix of Proposition 4 and A * ∈ M n×n F q d is a matrix composed of N × N blocks of Frobenius powers of elements of A * , i.e.

A * =                   a 0,0 a q 0,0 . . . a q d-1 0,0 . . . a 0,N-1 a q 0,N-1 . . . a q d-1 0,N-1 . . . . . . a N-1,0 a q N-1,0 . . . a q d-1 N-1,0 . . . a N-1,N-1 a q N-1,N-1 . . . a q d-1 N-1,N-1                   Proof Let (V 1 , . . . ,V N ) ∈ (F q d ) N . We set: (Z 1 , . . . , Z N ) = A * (V 1 , . . . ,V N ) = N-1 ∑ i=0 a i,0 V i+1 , . . . , N-1 ∑ i=0 a i,N-1 V i+1 .
According to Proposition 4, we need to compute the Frobenius images of (Z 1 , . . . , Z N ) to split it to the small field. For all k, 0 k < d, we have:

(Z q k 1 , . . . , Z q k N ) = N-1 ∑ i=0 a q k i,0 V q k i+1 , . . . , N-1 ∑ i=0 a q k i,N-1 V q k i+1 .
We notice that Z q k i is obtained only from the V q k j 's for j, 1 j N. This explains intuitively the shape of A * We constructed the matrix A * such that:

(V 1 ,V q 1 , . . . ,V q d-1 1 , . . . ,V N ,V q N , . . . ,V q d-1 N ) A * = (Z 1 , Z q 1 , . . . , Z q d-1 1 , . . . , Z N , Z q N , . . . , Z q d-1 N ). (9)
Let A ∈ M n×n (F q ) be the small field representation of A * , we now prove that

A = M N,d A * M -1 N,d . First, let (v 1 , . . . , v n ) ∈ F n q resp. (z 1 , . . . , z n ) ∈ F n q be the small field representation of (V 1 , . . . ,V N ) (resp. (Z 1 , . . . , Z N )). It holds that (v 1 , . . . , v n )A = (z 1 , . . . , z n ).
From Proposition 4, we know that

(v 1 , . . . , v n ) M N,d = (V 1 ,V q 1 , . . . ,V q d-1 1 , . . . ,V N ,V q N , . . . ,V q d-1 N ), (z 1 , . . . , z n ) M N,d = (Z 1 , Z q 1 , . . . , Z q d-1 1 , . . . , Z N , Z q N , . . . , Z q d-1 N ).
By replacing in (9), we get

(v 1 , . . . , v m ) M N,d A * = (z 1 , . . . , z m )M N,d (v 1 , . . . , v m ) M N,d A * M -1 N,d = (z 1 , . . . , z m ). Then, A = M N,d A * M -1 N,d is the small field representation of A * . ⊓ ⊔
We consider now the Frobenius transformation.

Proposition 9 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 . For all k, 0 k < d:

Frob k •F * • Frob d-k , ϕ N • Frob k •ϕ -1 N • S , T • ϕ N • Frob d-k •ϕ -1
N is an equivalent key.

Proof For any k, 0 k < d, the polynomials of

(Frob k •F * • Frob d-k )(X 1 , . . . , X N ) = F * (X q d-k 1 , . . . , X q d-k N ) q k
have the same monomials as F * (X 1 , . . . , X N ) but their coefficients are raised to the power of q k . This is explained in [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]. As a consequence, if F * (X 1 , . . . , X N ) has HFE-shape, so is

(Frob k •F * • Frob d-k )(X 1 , . . . , X N ).
In addition:

G = T • ϕ N • F * • ϕ -1 N • S G = T • ϕ N • Frob d-k •ϕ -1 N • ϕ N • Frob k •F * • Frob d-k •ϕ -1 N • ϕ N • Frob k •ϕ -1 N • S .
As the Frobenius application is linear in F q , the transformations

T • ϕ N • Frob d-k •ϕ -1 N and ϕ N • Frob k •ϕ -1 N • S remain affine. Finally, Frob k •F * • Frob d-k has HFE-shape, proving Proposition 9.
⊓ ⊔

We introduce also the matrix representation of a Frobenius application.

Proposition 10 Let Frob k ∈ M n×n (F q ) be the matrix representing the linear transformation ϕ

N • Frob k •ϕ -1 N over F q . Then Frob k = M N,d P N,d,k M -1 N,d
where

P N,d,k = Diag(R d,k , . . . , R d,k N ) and R d,k is the d × d matrix of a k positions left-rotation, that is R d,k = 0 k,d-k I k I d-k 0 d-k,k . Proof Let (V 1 , . . . ,V N ) ∈ (F q d ) N . We set Frob k (V 1 , . . . ,V N ) = (V q k 1 , . . . ,V q k N ) = (Z 1 , . . . , Z N ).
In the big field, a left k-rotation of (V,V q , . . . ,V q d-1 ) is the application of Frob k to such vector. Indeed, Frob k (V,V q , . . . ,V q d-1 ) = (V q k , . . . ,V q d-1 ,V, . . . ,V q k-1 ). More generally, the matrix P N,d,k makes this rotation on each N components in the big field. That is

(V q 0 1 , . . . ,V q d-1 1 , . . . ,V q 0 N , . . . ,V q d-1 N ) P N,d,k = (V q k 1 , . . . ,V q d-1 1 ,V q 0 1 , . . . ,V q k-1 1 , . . . ,V q k N , . . . ,V q d-1 N ,V q 0 N , . . . ,V q k-1 N
) .

We have then:

(V q 0 1 , . . . ,V q d-1 1 , . . . ,V q 0 N , . . . ,V q d-1 N ) P N,d,k = (Z q 0 1 , . . . , Z q d-1 1 , . . . , Z q k N , . . . , Z q d-1 N ) . (10)
As in the proof of Proposition 8, let

(v 1 , . . . , v n ) ∈ F n q resp. (z 1 , . . . , z n ) ∈ F n q be the small field representation of (V 1 , . . . ,V N ) (resp. (Z 1 , . . . , Z N )). According to Proposition 4, it holds that (v 1 , . . . , v n ) M N,d = (V 1 ,V q 1 , . . . ,V q d-1 1 , . . . ,V N ,V q N , . . . ,V q d-1 N ), (z 1 , . . . , z n ) M N,d = (Z 1 , Z q 1 , . . . , Z q d-1 1 , . . . , Z N , Z q N , . . . , Z q d-1 N ).
By replacing in [START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF]:

(v 1 , . . . , v m ) M N,d P N,d,k = (z 1 , . . . , z m )M N,d (v 1 , . . . , v m ) M N,d P N,d,k M -1 N,d = (z 1 , . . . , z m ).
Then, M N,d P N,d,k M -1 N,d is indeed the small field representation of Frob k .

⊓ ⊔

According to Proposition 9, we can derive (d -1) other equivalent keys from any valid private key. This refers to the so-called Frobenius sustainer of [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF]47]. To count the number of equivalent keys introduced by Proposition 7 and 9, we need to know how many different keys they generate. To do that, we will show that any equivalent key obtained from the Frobenius and affine sustainers has a unique representation.

Lemma 5 Let A * ∈ Aff N (F q d ). For all k, 0 k < d, there exists A * ′ ∈ Aff N (F q d ) such that Frob k •A * = A * ′ • Frob k . Proof As Frob d-k • Frob k is the identity, it holds that Frob k •A * = Frob k •A * • Frob d-k • Frob k .

Now we prove that

A * ′ = Frob k •A * • Frob d-k is an affine transformation. Let (X 1 , . . . , X N ) ∈ (F q d ) N : A * ′ (X 1 , . . . , X N ) = Frob k •A * • Frob d-k (X 1 , . . . , X N ) = Frob k •A * X q d-k 1 , . . . , X q d-k N A * ′ (X 1 , . . . , X N ) = Frob k ∑ N-1 i=0 A i,0 X q d-k i+1 + A 0 , . . . , ∑ N-1 i=0 A i,N-1 X q d-k i+1 + A N A * ′ (X 1 , . . . , X N ) = ∑ N-1 i=0 A i,0 X q d-k i+1 + A 0 q k , . . . , ∑ N-1 i=0 A i,N-1 X q d-k i+1 + A N q k A * ′ (X 1 , . . . , X N ) = ∑ N-1 i=0 A q k i,0 X q d i+1 + A q k N , . . . , ∑ N-1 i=0 A q k i,N-1 X q d i+1 + A q k N A * ′ (X 1 , . . . , X N ) = ∑ N-1 i=0 A q k i,0 X i+1 + A q k N , . . . , ∑ N-1 i=0 A q k i,N-1 X i+1 + A q k N .
The transformation A * ′ is indeed an affine transformation with the same coefficients as A * raised to the power q k . ⊓ ⊔

Lemma 5 shows that the Frobenius and the affine transformation somehow commute. This will be useful to write uniquely an equivalent key.

Lemma 6 Let (A * , A * ′ ) ∈ Aff N (F q d ) × Aff N (F q d ) be two invertible affine transformations. If Frob k •A * = Frob k ′ •A * ′ , for k, k ′ , 0 k, k ′ < d, then A * ′ = A * and k ′ = k. Proof First, it is straightforward to see that if k = k ′ , then Frob k •A * = Frob k •A * ′ ⇔ Frob d-k • Frob k •A * = Frob d-k • Frob k •A * ′ ⇔ A * = A * ′ .
Then, we have only to prove that Frob k

•A * = Frob k ′ •A * ′ ⇒ k = k ′ .
Assume for a contradiction that there exists k and k ′ such that Frob k •A * = Frob k ′ •A * ′ and k ′ = k. Then, we can write k ′ = k + ℓ, with ℓ = 0:

Frob k •A * = Frob k ′ •A * ′ Frob k •A * • Frob d-k = Frob k+ℓ •A * ′ • Frob d-k Frob k •A * • Frob d-k = Frob ℓ • Frob k •A * ′ • Frob d-k . According to Lemma 5, A * = Frob k •A • Frob d-k and A * ′ = Frob k •A * ′ • Frob d-k
are also affine transformations. We write:

A * = Frob ℓ • A * ′ . As ℓ = 0, the transformation Frob ℓ • A * ′ has degree q ℓ . That is, each polynomial in the representation of Frob ℓ • A * ′ has the form ∑ N i=1 A q ℓ i X q ℓ i + A q ℓ 0 , with A i ∈ F q d . As A * ′ is invertible, at least one term of degree q ℓ is non-zero. Thus, Frob ℓ • A * ′ cannot be equal to A * which is an affine transformation and has maximal degree 1. This proves that Frob k

•A * = Frob k ′ •A * ′ ⇒ k = k ′ and A * = A * ′ .
⊓ ⊔

Together with Lemma 5, Lemma 6 is used to derive a canonical representation of equivalent keys.

Theorem 4 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D)

∈ N 4 . Let A * , B * ∈ Aff N (F q d )
be affine transformations in the big field and k, 0 k < d be an integer. Each Multi-HFE equivalent key (F ′ , S ′ , T ′ ) obtained using Proposition 7 and 9 can be written uniquely

F ′ = Frob k •B * • F * • A * • Frob d-k S ′ = ϕ N • Frob k •A * -1 • ϕ -1 N • S T ′ = T • ϕ N • B * -1 • Frob d-k •ϕ -1
N . Proof Let (F ′ , S ′ , T ′ ) and (F , S , T ) be equivalent keys. By hypothesis, a equivalent key has been obtained by composition of several Frobenius and affine transformations. According to Lemma 5, the transformations can be reordered. Hence, any equivalent key can then be written as

F ′ = Frob k 1 • • • • • Frob k r •B * 1 • • • • • B * n b • F * • A * n a • • • • • A * 1 • Frob d-k r • • • • • Frob d-k 1 S ′ = ϕ N • Frob k 1 • • • • • Frob k r •A * -1 1 • • • • • A * -1 n a • ϕ -1 N • S T ′ = T • ϕ N • B * -1 n b • • • • • B * -1 1 • Frob d-k r • • • • • Frob d-k 1 •ϕ -1 N .
The composition of two affine transformations is an affine transformation, and the composition of two Frobenius transformations is a Frobenius transformation. This can then be simplified as

F ′ = Frob k •B * • F * • A * • Frob d-k S ′ = ϕ N • Frob k •A * -1 • ϕ -1 N • S T ′ = T • ϕ N • B * -1 • Frob d-k •ϕ -1 N .
To show the uniqueness of this representation, suppose that there exists A * ′ , B * ′ ∈ Aff N (F q d ) and k ′ ∈ N, 0 k < d leading to the same equivalent key. Then, by considering S ′ , we get:

ϕ N • Frob k •A * -1 • ϕ -1 N • S = ϕ N • Frob k ′ •A * ′-1 • ϕ -1 N • S Frob k •A * -1 = Frob k ′ •A * ′-1 .
According to Lemma 6, this implies that k ′ = k and A * ′-1 = A * -1 . Similarly for T ′ , we show that B * ′-1 = B * -1 , i.e. the representation is unique, proving the theorem.

⊓ ⊔

We are finally able to count the total number of equivalent keys coming from Proposition 7 and Proposition 9.

Theorem 5 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 . There are exactly

d q dN N-1 ∏ i=0 (q dN -q d i ) 2
equivalent keys coming from affine transformations and Frobenius transformations.

Proof According to Theorem 4, each equivalent key is uniquely defined by two invertible affine transformations

(A * , B * ) ∈ Aff N (F q d ) × Aff N (F q d
) and an integer k, 0 k < d. The number of equivalent keys is the number of elements in

GL N (F q d ) × (F q d ) N × GL N (F q d ) × (F q d ) N × Z/d Z.
There are exactly ∏ N-1 i=0 (q d ) N -(q d ) i invertible matrices in M N×N F q d . Thus, we obtain the expected number of keys.

⊓ ⊔

Weaknesses of HFE/multi-HFE Induced by Equivalent Keys

We show here that the high number of equivalent keys turns out to be a weakness for HFE/Multi-HFE schemes. For example, an interesting property of the MinRank arising in HFE/Multi-HFE is that the kernel of the matrices in ( 8) is independent of the equivalent key used up to Frobenius transforms. To show this result (Theorem 6), we first need to prove the property for a single private key.

Lemma 7 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 . We denote by (G 1 , . . . , G n ) ∈ (M n×n (F q )) n the matrices associated to the public key

G = T • F • S . Let S ∈ M n×n (F q ) and T ∈ M n×n (F q )
be the matrix representation of S and T , respectively. Finally, let

U = T -1 M N,d = [u i, j ] ∈ M n×n F q d ,
and

K = ker(∑ n-1 i=0 u i,0 G i+1 ). Then ∀t, k, 0 t < N, 0 k < d, ker n-1 ∑ i=0 u i,t d+k G i+1 = Frob k (K) .
Proof Let t, 0 t < N and k, 0 k < d be two integers. Using equation ( 6) it holds that

∑ n-1 i=0 u i,t d+k G i+1 = SM N,d F t * d,k M t N,d S t .
As S and M N,d are invertible, we have that

ker n-1 ∑ i=0 u i,t d+k G i+1 = ker SM N,d F t * d,k ker n-1 ∑ i=0 u i,t d+k G i+1 S M N,d = ker F t * d,k ker n-1 ∑ i=0 u i,t d+k G i+1 = ker F t * d,k M -1 N,d S -1 .
Recall that ℓ = ⌈log q (D)⌉. With high probability, ker Lemma 4). From Definition 1, the non-zero columns of F t * d,k are the ones of F t after rotating the columns of each d × d blocks from k positions. Then, rotating accordingly the columns of K N,d,Nℓ leads to a basis of ker(F t * d,k ). This rotation is exactly the one performed by the matrix P N,d,-k defined in Proposition 10. Then, ker(F t * d,k ) = K N,d,Nℓ P N,d,-k . As P N,d,-k is a permutation matrix, its inverse is simply P N,d,k (the rotation is done the other way). Finally we obtain

(F t ) = ker (F 1 ) = K N,d,Nℓ , ∀t, 1 t N (see
ker ∑ n-1 i=0 u i,t d+k G i+1 = K N,d,Nℓ P N,d,-k M -1 N,d S -1 ker ∑ n-1 i=0 u i,t d+k G i+1 = K N,d,Nℓ M N,d P -1 N,d,-k -1 S -1 ker ∑ n-1 i=0 u i,t d+k G i+1 = K N,d,Nℓ M N,d P N,d,k -1 S -1 .
The matrix M N,d P N,d,k is obtained from M N,d by rotating the columns of each d × d block to the left. Due to the construction of M N,d , this is equal to Frob k (M N,d ). Then:

ker ∑ n-1 i=0 u i,t d+k G i+1 = K N,d,Nℓ Frob k M N,d -1 S -1 ker ∑ n-1 i=0 u i,t d+k G i+1 = K N,d,Nℓ Frob k M -1 N,d S -1 .
As the coefficients of S and K N,d,Nℓ lie in the field F q , this is equal to

ker n-1 ∑ i=0 u i,t d+k G i+1 = Frob k K N,d,Nℓ M -1 N,d S -1 .
Finally, as K N,d,Nℓ = ker(F 1 ) = ker(F 1 * d,0 ), we conclude:

ker n-1 ∑ i=0 u i,t d+k G i+1 = Frob k ker(F 1 * d,0 )M -1 N,d S -1 = Frob k ker n-1 ∑ i=0 u i,0 G i+1 = Frob k (K) .
This proves the lemma.

⊓ ⊔

In other words, the kernel is unique up to Frobenius transformation. This property is used to prove the following theorem for any equivalent key.

Theorem 6 Let (F * , S , T ) and (F * ′ , S ′ , T ′ ) be equivalent multi-HFE private keys and (G 1 , . . . , G n ) ∈ (M n×n (F q )) n be the matrices of their associated public key. Let (S, T) ∈ M n×n (F q ) × M n×n (F q ), and (S ′ , T ′ ) ∈ M n×n (F q ) × M n×n (F q ) be the matrix representation of (S , T ), and

(S ′ , T ′ ) respectively. Let U = T -1 M N,d = [u i, j ] ∈ M n×n F q d , and K = ker(∑ n-1 i=0 u i,0 G i+1 ). Similarly, let U ′ = T ′-1 M N,d = [u ′ i, j ] ∈ M n×n F q d and K ′ = ker(∑ n-1 i=0 u ′ i,0 G i+1 ). Then ∃k, 0 k < d, such that: K ′ = Frob k (K) .
Proof From Theorem 4, we can write

T ′ = T • ϕ N • A * -1 • Frob d-k •ϕ -1 N .
Each of these application has a matrix representation (see Proposition 4, 8 and 10). The matrix corresponding to T ′ is then

T ′ = M N,d P N,d,d-k A * -1 M -1
N,d T, where A * has the shape of Proposition 8. Its inverse is the matrix

T ′-1 = T -1 M N,d A * P -1 N,d,d-k M -1 N,d .
We have

U ′ = T ′-1 M N,d = T -1 M N,d A * P -1 N,d,d-k M -1 N,d M N,d = U A * P N,d,k .
Let A * P N,d,k = [a i, j ] ∈ M n×n F q d , we have:

u ′ i, j = n-1 ∑ t=0 u i,t a t, j , ∀i, j, 0 i, j < n.
Due to the shape of A * and P N,d,k , a t, j is non-zero if and only if t ≡ j -k mod d. Then, we have u ′ i, j = ∑ N-1 t=0 u i,t d+( j-k mod d) a t d+( j-k mo for all i, j, 0 i, j < n. Therefore

n-1 ∑ i=0 u ′ i,0 G i+1 = n-1 ∑ i=0 N-1 ∑ t=0 u i,t d+(-k mod d) a t d+(-k mod d),0 G i+1 = N-1 ∑ t=0 a t d+(-k mod d),0 n-1 ∑ i=0 u i,t d+(-k mod d) G i+1 .
We denote by t,-k the matrix ∑ n-1 i=0 u i,t d+(-k mod d) G i+1 . One can see that the kernel of this matrix is the same for all t, 0 t < N. Indeed, according to Lemma 7:

ker t,-k = Frob t d+(-k mod d) mod d (K) = Frob -k mod d (K) ∀t, 0 t < N. As n-1 ∑ i=0 u ′ i,0 G i+1 = N-1 ∑ t=0 a t d+(-k mod d),0 t,-k
is a linear combination of t,-k for t, 0 t < N, then ker t,-k ⊆ ker ∑ n-1 i=0 u ′ i,0 G i+1 . As U ′ is an equivalent key, there exists -according to (8) -a matrix W ′ such that

n-1 ∑ i=0 u ′ i,0 G i+1 = W ′ F 1 W ′t , so that the rank of ∑ n-1 i=0 u ′ i,0 G i+1 is Rank (F 1 ). Similarly from (7), we get t,-k = ∑ n-1 i=0 u i,t d+(-k mod d) G i+1 = W F t+1 * d,-k W t ,
where W is invertible. As rotating rows and columns of a matrix does not change its rank, it holds that

Rank t,-k = Rank F t+1 * d,-k = Rank (F t+1 ) = Rank (F 1 ) = Rank n-1 ∑ i=0 u ′ i,0 G i+1 .
Thus, we get ker t,-k = ker

∑ n-1 i=0 u ′ i,0 G i+1 = K ′ . Finally, K ′ = Frob -k mod d (K), proving the theorem. ⊓ ⊔
With Theorem 6, we know that the matrices of ( 8) have the same kernel (up to Frobenius transform), independently on the equivalent key chosen. Equivalent keys allow also to further slightly improve the MinRank attack. We consider an instance of HFE with parameters (q, N, d, D) ∈ N 4 , and ℓ = ⌈log D⌉. We have to solve the MinRank problem on the (n × n)-matrices G 1 , . . . , G n whose entries lie in F q with target rank Nℓ. Using the Kipnis-Shamir modeling described in [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF][START_REF] Faugère | Cryptanalysis of MinRank[END_REF][START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF], we have to solve the algebraic system of the (n (n -Nℓ)) quadratic equations in (Nℓ (n -Nℓ) + n) variables given by the entries of the matrix   

1 x 1,1 . . . x 1,Nℓ . . . . . . . . . 1 x n-Nℓ,1 . . . x n-Nℓ,Nℓ    • n ∑ i=1 λ i G i . (11)
Note that we are looking for solutions in F q d rather than in F q . From now on, and similarly to [START_REF] Faugère | Cryptanalysis of MinRank[END_REF], these equations are called the KS (Kipnis-Shamir) equations. We denote by

I KS ∈ F q [{x i, j } 1≤ j≤Nℓ 1≤i≤n-Nℓ , λ 1 , . . . , λ n ]
the ideal generated by the KS equations and V KS ⊂ F q d Nℓ (n-Nℓ)+n the corresponding variety.

Theorem 7

The MinRank problem associated to HFE (resp. multi-HFE) can be solved by fixing one (resp. N) coefficient(s) to a random non-zero value (resp. to random non all zero values) in F q d . That is, the variety V KS has at least q d -1 (resp. q dN -1) solutions.

Proof We know that the first column of

U = T -1 M N,d ∈ M n×n F q d is in V KS .
Let A * ∈ M n×n F q d be an invertible matrix as described in Proposition 8 and A * ∈ GL N (F q d ) be the induced transformation. According to Proposition 7, A * can be used to build an equivalent key. Let then (F * ′ , S ′ , T ′ ) be an equivalent key such that

T ′-1 = A • T -1 with A = ϕ N • A * • ϕ -1 N . Consider now the matrix representation T ′-1 of T ′-1 . It holds that T ′-1 = T -1 M N,d A * M -1 N,d . Being an equivalent key, the first column of U ′ = T ′ M N,d ∈ M n×n F q d is also in V KS . Using the construction of T -1 , U ′ = T -1 M N,d A * M -1 N,d M N,d = U A * .
Each column of A * can have at most N non-zero entries. The N non-zero entries of the first column of A * are a 0,0 , a d,0 , . . . , a (N-1) d,0 . The first column of U A * is then

λ = (λ 1 , . . . , λ n ) = n-1 ∑ k=0 u 0,k a k,0 , . . . n-1 ∑ k=0 u n-1,k a k,0 λ = N-1 ∑ k=0 u 0,k d a k d,0 , . . . n-1 ∑ k=0 u n-1,k d a k d,0 .
Consider the first N components of λ . This gives rise to a linear system of N equations:

λ 1 = N-1 ∑ k=0 u 0,k d a k d,0 , . . . , λ N = N-1 ∑ k=0 u N,k d a k d,0 .
For any fixed λ 1 , . . . , λ N not all zero, this linear system has then one solution for a 0,0 , . . . , a (N-1) d,0 with high probability. This allows to choose N coefficients λ i arbitrarily and still obtain a valid solution (equivalent key). The variety V KS has then at least q dN -1 solutions.

⊓ ⊔

This means that for valid values {x i, j } 1≤ j≤Nℓ 1≤i≤n-Nℓ in [START_REF] Buchberger | Comments on the translation of my phd thesis[END_REF], there are (q d ) N vectors (λ 1 , . . . , λ n ) such that the kernel of ∑ n i=1 λ i G i is the one induced by the x i, j 's. Therefore, the values of N components (say λ 1 , . . . , λ N ) can be randomly chosen. The new system still has (n (n -Nℓ)) equations but only (Nℓ (n -Nℓ) + n -N) variables.

As described in Sect. 3.1, the coefficients of the polynomial system are in the small field F q . To keep this property, we fix variables with values over the small field. Experimentally, fixing one variable to 1 (or any value from F q ) and the (N -1) others to 0 gives the best results. After N variables (λ 1 , . . . , λ N ) have been fixed, V KS has at least d elements. This property already noticed in [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF] for HFE is a direct consequence of Theorem 6, i.e. Frobenius images of the kernel are also valid.

The MinRank allows to recover a kernel that is central to our attack. Once K = ker (∑ n k=1 λ k G k ), it is used to recover the different parts of the private key as described in the next section.

Full Key Recovery

In this part, we detail all the steps of a key-recovery attack against multi-HFE.

Roadmap of the attack

Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 (as defined in Sect. 2.1). The attack is divided in 3 steps.

Recovering the Transformation on the Polynomials

This part of the key-recovery corresponds to the MinRank problem described in Sect. 3. Solving the MinRanks of (8) allow to recover a kernel matrix K related to the private key and consequently the transformation T . There are N MinRanks to be solved but we show that this has to be done only once to recover T .

Theorem 8 For multi-HFE, recovering

U = [u i, j ] = T -1 M N,d ∈ M n×n F q d reduces
to solving N -1 linear systems of (n (n -Nℓ)) equations in (n -N) variables in F q d once one column of U is known. Proof Assume w.l.o.g. that the first column of U is known i.e. after solving one of the MinRank of [START_REF] Bosma | The Magma algebra system I: The user language[END_REF]. We can compute the matrix K = ker ∑ n-1 i=0 u i,0 G i+1 . According to Lemma 7, we also have that K = ker ∑ n-1 i=0 u i,t d+0 G i+1 , ∀t, 0 t < N. Thus, for all t, 0 t < N, it holds that

K • ∑ n-1 i=0 u i,t d+0 G i+1 = 0.
This is a linear system where the u i,t d+0 's are unknown. Solving this system gives another column of the matrix U. This has to be done N -1 times in order to recover N -1 other columns of U. According to Proposition 6, this is enough to recover the entire matrix U. ⊓ ⊔

Recovering the Transformation on the Variables

Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] originally proposed a method for recovering the transformation on the variables by solving an overdetermined system of (n ℓ (n -ℓ)) linear equations in n 2 variables over F q with ℓ = ⌈log q (D)⌉. Applied to multi-HFE, this would give (n ℓ (n -Nℓ)) equations in n 2 variables over F q . We propose here an alternative method which reduces the number of variables and equations by a factor d. On the other hand, it operates on the big field.

Theorem 9 For multi-HFE, recovering W = [w i, j ] = S M N,d ∈ M n×n F q d reduces to solve a linear system of

(Nℓ (n -Nℓ)) equations in (N n) variables in F q d once U = T -1 M N,d ∈ M n×n F q d is known.
Proof Let K = ker ∑ n-1 k=0 u k,0 G k+1 . To find the coefficients w i, j of W, it is enough to remark that according to [START_REF] Bosma | The Magma algebra system I: The user language[END_REF], KW = ker (F i ) for all i, 1 i n. According to Lemma 4, we know that ker (F i ) has Nℓ columns set to zero. Moreover, we know that only N columns are needed to build the whole matrix W (see Proposition 6). We construct the corresponding linear system of N (n -Nℓ) equations in N n variables. However, If ℓ > 1, the system is underdetermined. To circumvent this issue, we will use Lemma 7: Frob j (K) = ker ∑ n-1 k=0 u k,i d+ j G k+1 = ker WF i * d, j W t = ker WF i * d, j . Finally:

ker F i * d, j = Frob j (K)W . ( 12
)
For all j, 0 j < d, ker(F i * d, j ) has Nℓ columns set to zero (see Lemma 4). Moreover, for j, (d -ℓ + 1) j < d, each matrix ker(F i * d, j ) has N common zero-columns with ker(F i * d,0 ). We may then add the N (n -Nℓ) equations induced by [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF] for each j, (d -ℓ + 1) j < d. All in all, the system has Nℓ (n -Nℓ) linear equations. This allows to recover W and thus S .

⊓ ⊔

Recovering S amounts then to solve the linear system given by the entries of

Frob (d-ℓ+1) (K)W ′ (N) = • • • = Frob (d-1) (K)W ′ (N) = K W ′ (N) = 0 , ( 13
)
where W ′ is unknown and W ′ (N) denotes the N columns submatrix of W corresponding to the common zero columns of ker F i * d,0 , . . . , ker F i * d,d-1 for any i, 1 i N.

Recovering the Inner Polynomial System

As soon as the matrices T = M N,d U -1 and S = WM -1 N,d are recovered, we only need to reconstruct a private (inner) transformation. This is done simply by computing

F * = ϕ -1 N • T -1 • G • S -1 • ϕ N .
By construction of its components, the transformation F * respects the HFE-shape (as defined in Sect. 2.1).

A Step by Step Example

To illustrate our attack, we consider a small odd characteristic example. For the sake of simplicity, we use homogeneous polynomials and linear transformations. Once again, our attack can be adapted to the affine case as explained in Sect. 6.2.

We consider the parameters q = 7, N = 2, d = 4, and D = 14. We denote n = Nd = 8, and ℓ = ⌈log q (D)⌉ = 2. We consider F 7 4 = F 7 [x]/ < x 4 + 5 x 2 + 4 x + 3 >. Finally, let θ be a primitive root of the defining irreducible polynomial.

Key Generation. We choose N random polynomials having a "multi-HFE shape" of degree less than or equal to D as well as two invertible (n × n) matrices S and T. To visualize the rank property, we give in Fig. 1 the symmetric matrices F i associated to the polynomials F i , i.e.:

F i = XF i X t where X = (X 1 , X q 1 , . . . , X q d-1 1 , . . . , X N , X q N , . . . , X q d-1 N
).

The public key of this multi-HFE instance is a set of n quadratic polynomials (g 1 , . . . , g n ). We give in Fig. 2 the symmetric matrix representation G i of each g i , i.e.:

g i = (x 1 , . . . , x n ) G i (x 1 , . . . , x n ) t .
Fig. 1 Private key of the Multi-HFE example with q = 7, N = 2, d = 4, and D = 14. Recovering an Equivalent T . The first step is to solve a MinRank problem. By construction, there exists a non-

G 1 =            3
           , G 2 =            3
           , G 3 =            3
           , G 4 =            1
           , G 5 =            4
           , G 6 =            2
           , G 7 =            6
           , G 8 =            6
zero vector (λ 1 , . . . , λ n ) ∈ F q d n such that Rank(∑ n i=1 λ i G i ) = Nℓ (Theorem 3
). According to Sect. 5, we can randomly fix N variables to have a zero-dimensional ideal.

We fix for instance λ 1 = 1 and λ 2 = 0. Using the notations of Sect. 2.4, we have to solve a MinRank with

(M 0 = -G 1 , M 1 , . . . , M 6 = G 3 , . . . , G 8 ) with n = Nd = 8, k = n -N = 6, r = Nℓ = 4.
We have d = 4 solutions given by the vector λ (1) = (1, 0, θ 110 , θ 2215 , θ 830 , θ 1958 , θ 1889 , θ 2363 ) as well as its Frobenius images Frob j (λ (1) ) for all j, 0 j < d. This is a direct consequence of Proposition 9 from Sect. 4. The kernel K of (∑ n i=1 λ

(1)

i G i ) can be computed, and we get the matrix

K =    
1 0 0 0 θ 828 θ 1612 θ 530 θ 1086 0 1 0 0 θ 502 θ 134 θ 1450 θ 566 0 0 1 0 θ 1981 θ 1755 θ 1660 θ 2059 0 0 0 1 θ 870 θ 963 θ 2276 θ 425     .

This matrix is then used to recover N columns of U ′ = T ′-1 M N,d according to Theorem 8. In our example, we need only one more column as N = 2. This amounts to solve the linear system K (∑ n i=1 λ i G i ) = 0. As pointed again in Theorem 8, this is enough to recover the whole matrix U. To have independent columns, we fix λ 1 = 0 and λ 2 = 1. Solving this linear system gives λ (2) = (0, 1, θ 1587 , θ 2150 , θ 59 , θ 1111 , θ 1093 , θ 1656 ).

The matrix U ′ is finally reconstructed by taking the Frobenius of these vectors λ (1) and λ (2) :

U ′ =             1 1 1 1 0 0 0 0 0 0 0 0 1
            .
The secret matrix T ′ = M N,d U ′-1 has been recovered at this step:

T ′ =            
1 0 0 0 0 0 0 0 5 5 5 0 3 3 3 1 6 2 0 5 0 0 5 5 0 5 6 1 1 2 4 5 0 1 0 0 0 0 0 0 1 3 2 4 4 2 6 4 3 0 1 3 3 5 2 6 1 6 6 3 5 2 0 3

            .
Recovering an Equivalent S . We follow the method explained in Sect. 6.1.2 to recover a valid matrix W ′ = S ′ M N,d . Even if the matrices F 1 and F 2 of the private key are unknown, we know due to the HFE-shape that in echelon form we have for all i, 1 i N:

ker (F i ) =     0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1     , ker F i * d,(d-1) =     0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0     .
These two matrices have both their (i d)-th columns set to zero for 0 i < N (i.e. columns 0 and 4). We now construct a linear system of N (n -Nℓ) equations in the N n variables γ 1,1 , . . . , γ 1,n , . . . , γ N,1 , . . . , γ N,n from

K •    γ 1,1 γ 2,1 . . . . . . γ 1,n γ 2,n    = 0, Frob d-1 (K) •    γ 1,1 γ 2,1 . . . . . . γ 1,n γ 2,n    = 0.
The system has (q d ) N solutions. This is again a consequence of equivalent keys explained in Sect. 4. We then randomly set N variables in each one of the N columns to arbitrary values. For this example, we take γ 1,1 = 1, γ 1,2 = 0, γ 2,1 = 0, γ 2,2 = 1 (the columns have to be linearly independent). This linear system has one solution providing two vectors:

w (1) = (1, 0, θ 75 , θ 66 , θ 314 , θ 132 , θ 1308 , θ 2017 ), w (2) = (0, 1, θ 505 , θ 1673 , θ 1960 , θ 1947 , θ 733 , θ 1788 ).

As for U ′ , the rest of the matrix is built by raising the first columns to the power of q j , for all j, 0 < j < d.

W ′ =             1 1 1 1 0 0 0 0 0 0 0 0 1
            . The matrix S ′ = W ′ M -1 N,d
, which is part of a private key has been then recovered:

S ′ =            
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 4 1 6 5 2 2 0 1 6 5 0 5 3 3 0 0 4 3 0 6 3 5 0 3 3 5 4 2 3 1 4 2 0 6 4 0 4 0 3 6 3 1 2 4 3 0 6

           
.

Recovering an Equivalent F . To conclude the attack, we have to recover a valid inner transformation. From the knowledge of S ′ and T ′ , we compute:

F * ′ = ϕ -1 N • T ′-1 • G • S ′-1 • ϕ N .
In terms of matrix/vector operations, we first compute the small field representation of F * ′ :

F ′ = T ′-1 • G • S ′-1 (H 1 ′ , . . . , H n ′ ) = (S ′-1 G 1 S ′-t , . . . , S ′-1 G n S ′-t ) T ′-1 .
Then, we recover the transformation on the big field using the matrix M N,d of Proposition 4.

F * ′ = ϕ -1 N • F ′ • ϕ N (F 1 ′ , . . . , F N ′ ) = (P 1 , P d+1 , . . . , P d (N-1)+1 )
where (P 1 , . . . ,

P n ) = (M -1 N,d H 1 ′ M -t N,d , . . . , M -1 N,d H n ′ M -t N,d ) M N,d .
From the definitions of matrices U ′ and W ′ , it is equivalent (and simpler) to directly compute

F * ′ = ϕ -1 N • T ′-1 • G • S ′-1 • ϕ N . (F 1 ′ , . . . , F N ′ ) = (P 1 , P d+1 , . . . , P d (N-1)+1 )
where (P 1 , . . . ,

P n ) = (W ′-1 G 1 W ′-t , . . . , W ′-1 G n W ′-t ) U ′ .
With the matrices F 1 ′ , . . . , F N ′ , we recover a set of HFE-shaped polynomials. In our example, we obtain

F 1 ′ =            
θ 784 θ 1599 0 0 θ 173 θ 2089 0 0 θ 1599 θ 1581 0 0 θ 59 θ 709 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 θ 173 θ 59 0 0 θ 157 θ 1724 0 0 θ 2089 θ 709 0 0 θ 1724 θ 1791 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

            , F 2 ′ =            
θ 2277 θ 375 0 0 θ 321 θ 1681 0 0 θ 375 θ 749 0 0 θ 665 θ 227 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 θ 321 θ 665 0 0 θ 1384 θ 510 0 0 θ 1681 θ 227 0 0 θ 510 θ 1556 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

            . Thus F ′ 1 = θ 1581 X 14 1 + θ 2399 X 8 1 + θ 1509 X 7 1 X 7 2 + θ 859 X 7 1 X 2 + θ 784 X 2 1 + θ 489 X 1 X 7 2 + θ 973 X 1 X 2 + θ 1791 X 14 2 + θ 124 X 8 2 + θ 157 X 2 2 F ′ 2 = θ 749 X 14 1 + θ 1175 X 8 1 + θ 1027 X 7 1 X 7 2 + θ 1465 X 7 1 X 2 + θ 2277 X 2 1 + θ 81 X 1 X 7 2 + θ 1121 X 1 X 2 + θ 1556 X 14 2 + θ 1310 X 8 2 + θ 1384 X 2 2 .
The attack is now complete and a full valid private key has been recovered.

Affine Transformations

So far, we have only considered linear transformations and homogeneous polynomials. However, HFE or multi-HFE can use affine transformations and non-homogeneous polynomials. We describe here how to generalize our approach to the affine case.

Representation

The starting idea of our attack is to represent the polynomials in a matrix form. If the HFE-shaped polynomial F i ∈ F q d [X 1 , . . . , X N ] is not homogeneous, then there exists a matrix

F i ∈ M (n+1)×(n+1) F q d such that F i = XF i X t
where F i is symmetric and X = (X 1 , X q 1 , . . . , X q d-1 1 , . . . , X N , X q N , . . . , X q d-1 N , 1). Similarly, if a quadratic polynomial g i ∈ F q [x 1 , . . . , x n ] is not homogeneous, then we can write g i = xG i x t where G i ∈ M (n+1)×(n+1) (F q ) is symmetric and x = (x 1 , . . . , x n , 1).

The matrix M N,d -allowing to change basis -given in Proposition 4 simply becomes

   M N,d 0 . . . 0 • • • 1    .
The matrix representations of the secret polynomials F 1 , . . . , F N have however (n + 1) rows and columns instead of n. The rank of such matrices is (Nℓ + 1) (one row and column have been added). In our attack, we then try to find an affine combination of the public polynomials such that the rank of its corresponding matrix representation is (Nℓ + 1).

MinRank attack

To adapt the MinRank attack, we remark that it is possible to find a linear combination of the matrices instead of an affine combination. Thanks to equivalent keys (cf. Sect. 4) such linear combination exists. The problem is then to find (u 0,0 , . . . ,

u n-1,0 ) ∈ (F q d ) n such that Rank n-1 ∑ k=0 u k,0 G k+1 = Nℓ + 1.
We recover in this way a matrix U ∈ M n×n F q d as explained in 6.1. For the second step, the matrix K = ker ∑ n-1 k=0 u k,0 G k+1 has (n + 1) columns. To have an analogous property, the last column of K is set to zero i.e.

K =       1 0 . . . . . . 0 k 0,0 . . . k 0,N 0 0 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . 0 1 k n-N,0 . . . k n-N,N 0      
The first n columns of K can be used to perform the second step of the attack just as in Sect. 6. The method described above is the most straightforward and natural. However, there are at least two other ways of performing the MinRank attack.

Take the homogeneous part. The idea is to ignore the affine part. Namely, we perform the MinRank attack on the homogeneous part of the polynomials. That is, we try to find (u 0,0 , . . . ,

u n-1,0 ) ∈ (F d ) n such that Rank n-1 ∑ k=0 u k,0 G k+1 h = Nℓ
where G i h ∈ M n×n F q d is the matrix of the homogeneous part of g i (i.e. the matrix G i without the last row and column).

Since the rank of

∑ n-1 k=0 u k,0 G k+1 h is Nℓ, ∑ n-1 k=0 u k,0 G k+1 is of rank Nℓ + 1.
We added one more row and column. The attack is completed as we have found a linear combination such that the rank is Nℓ + 1. From a practical point of view, this method turns to be less efficient than the first one. This is probably due to the fact that the information coming from the non-homogeneous part is not used.

Add a constant polynomial. We consider a third strategy. We look for a private equivalent key such that F is homogeneous. This way, the rank of their matrices is Nℓ instead of (Nℓ + 1). We are then looking for an affine combination of the public polynomials. Namely, we compute (u 0,0 , . . . ,

u n,0 ) ∈ (F q d ) n+1 such that Rank n-1 ∑ k=0 u k,0 G k+1 + u n,0 I = Nℓ
where I is the matrix of the constant polynomial 1 (i.e. I[i, j] = 1 if i = j = n + 1 and 0 otherwise).

In this case, we try to cancel the affine part of ∑ n-1 k=0 u k,0 G k+1 such that its rank is Nℓ instead of Nℓ + 1. Note that in this method, we move the affine part of the inner polynomials to the matrix U and try to find an homogeneous internal transformation. Note that using only the first n components (u 0,0 , . . . , u n-1,0 ) of the solution leads back to the first method as the linear combination is of rank (Nℓ + 1) (only one entry is modified).

Experimentally, this method is the most efficient for the non-homogeneous case. This can be explained by the fact that the rank is lower and the affine part is taken into account.

Key Recovery in Characteristic 2

Our attack uses the matrix representation of the public and secret polynomials. This representation has to be symmetric in order to keep a canonical representation of the quadratic forms. Let A be a matrix representing some quadratic form. The symmetric representation is obtained by computing A+A t 2 . In characteristic 2, such a matrix would be zero.

In their original paper, Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] suggest to use instead A + A t . Whilst the first step of the attack (MinRank) works indeed similarly, it appears that the second step of the attack -recovering S -fails with the method described in Sect. 6.1. In characteristic 2, the two steps are not independent and cannot be treated separately. We now discuss how to adapt our attack in characteristic 2. For reasons which will be explained, our adaptation depends on the parity of the rank. Thus, the section is divided in two parts. From now on, we denote by r = Nℓ the target rank of the MinRank. A toy example of our attack is given in Appendix A.

Even Rank.

The first part of the attack is to find a linear combination of the public matrices whose rank is r. For HFE, any solution (λ 1 , . . . , λ n ) ∈ (F q d ) n of the MinRank leads to another solution α(λ q i 1 , . . . , λ q i n ), for any α ∈ F * q d , and any i, 0 i < d. This is due to equivalent keys as detailed in Sect. 4.

In characteristic 2, it has been noticed [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF] that ∀(α, β ) ∈ F * q d ×F q d , a vector α(λ q i 1 , . . . , λ q i n )+β (λ q i+1 1 , . . . , λ q i+1 n ) is also solution if r is even. As a consequence, the ideal generated by the MinRank equations when r is even has dimension at least 1 (we can fix any value for β ).

Assume then that we fix a random value for λ 1 . Even after that, the MinRank problem has q d -1 solutions (and their Frobenius images). That is d (q d -1) in total. To decrease the number of solutions (i.e. to have only d solutions), we can try to fix one more variable as suggested in [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF]. A matrix T ′ can be computed, but there is an issue on the second step of the attack (recovering S ′ ). The linear system allowing to recover S ′ has no solution, which means that the T ′ computed is not valid. This suggests a relation between the different steps of the attack in characteristic 2.

The problem is that only solutions with β = 0 are actually equivalent keys. The solutions coming from β = 0 are not equivalent keys obtained from the affine and Frobenius transformations as described in Sect. 4. They appear to be spurious solutions. Thus, if we fix another variable as in [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF], it is very likely that the matrix T ′ that will be recovered does not lead to an equivalent secret key. In the other hand, not fixing another variable leads to an ideal of dimension at least 1 with an exponential number of solutions. As a consequence, the two parts of the attack cannot be treated separately. Recall that ℓ = ⌈log q (D)⌉. We need both

Rank (∑ n i=1 λ i G i ) = Nℓ and ker (∑ n i=1 λ i G i ) W ′ = ker (F 1
). Let K be the unknown kernel of (∑ n i=1 λ i G i ), and let W ′ (N) be the N columns matrix obtained from W ′ according to Sect 6.1.2. Thanks to (13), we have to solve:

K • (∑ n i=1 λ i G i ) = 0 and            Frob (d-ℓ+1) (K)W ′ (N) = 0, . . . Frob (d-1) (K)W ′ (N) = 0, K W ′ (N) = 0.
In our case K is unknown, thus the Frobenius transforms add equations of degree up to q d-1 . To avoid this, for any k, 0 k < d we use that

Frob d-k Frob k (K)W ′ (N) = Frob d-k (Frob k (K)) Frob d-k (W ′ (N) ) = K Frob d-k (W ′ (N) ). As Frob k (K)W ′ (N) = 0, we have K Frob d-k (W ′ (N) ) = Frob d-k (0) = 0.
Thus, we use instead the following equations:

K • (∑ n i=1 λ i G i ) = 0 and            K Frob ℓ-1 (W ′ (N) ) = 0, . . . K Frob 1 (W ′ (N) ) = 0, K W ′ (N) = 0.
We use also the representation of the entries of W ′ as a vector over F 2 using the mapping ϕ N . As

W ′ = S ′ M N,d , we have w ′ i, j = ∑ d-1 k=0 θ k (q j mod d ) s ′ i,d ⌊ j/d⌋+k with s ′ i, j ∈ F 2 for 0 i, j < n.
Since the Frobenius transform is linear over F 2 , the degree does not increase. The field equations s ′2 i, js ′ i, j = 0 can also be added. Finally, the system to be solved is the union of two overdetermined bi-linear systems [START_REF] Faugère | Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity[END_REF]. The system has r (nr) variables coming from K, n coming from the λ i 's, and d N n coming from S ′ . There are n (n -r) equations coming from K • (∑ n i=1 λ i G i ) = 0, ℓ N (n -r) coming from K Frob k (W ′ (N) ) = 0 and n 2 from the field equations. There is a total of n (nr) + ℓ N (nr) + n 2 equations in r (nr) + n + n 2 variables.

On various small examples, we observed that the degree of regularity of such systems is (Nℓ + 1) and does not depend on d when growing the size of d. This value matches the degree of regularity of the MinRank attack (see Sect. 7 for the complexity analysis). Hence, our variant seems to have asymptotically the same complexity as the attack in odd characteristic.

Odd Rank.

We now consider the case where the target rank r = Nℓ is odd. Here, the first step of the attack can be performed as expected and we recover the matrix T ′ (and consequently U ′ = T ′-1 M N,d ), as well as a kernel K. Thus, we can assume now that the matrices T ′ , U ′ and K are known.

The second step of the attack is to recover S ′ . To do that in characteristic = 2, we had to solve the system K W ′ = ker (F i ), where W ′ ∈ M n×n F q d is unknown. The success of this step is based on the remark that ker (F i ) is independent of the actual value of F i and is equal to K N,d,ℓ as described in Lemma. 4. In characteristic 2, this property does not hold. Recall that the matrix F i should be a symmetric matrix of rank Nℓ. In characteristic 2, this matrix has zero entries in its diagonal by following Kipnis-Shamir. The rank of such symmetric matrix cannot be odd (see for instance [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF]. Thus, in characteristic 2, ker (F i ) = K N,d,ℓ and cannot be used for the second step of our attack. To fix our attack, one shall not consider the symmetric form of F i . Consider the relation between the components of an equivalent public/private key:

T ′ • ϕ N • F * ′ • ϕ -1 N • S ′ = G F * ′ • ϕ -1 N • S ′ = ϕ -1 N • T ′-1 • G .
Recall that W ′ = S ′ M N,d . When we consider the matrix representation, we obtain

W ′ F 1 ′ * d,0 W ′t , . . . , W ′ F 1 ′ * d,d-1 W ′t , . . . , W ′ F N ′ * d,d-1 W ′t , . . . , W ′ F N ′ * d,d-1 W ′t = (G 1 , . . . , G n ) U ′ .
The matrices G i for i, 1 i n are the public matrices and the matrix U ′ has been recovered during the first step of our attack. Hence, the right hand side of this equation is known. Even if we do not know the value of the matrices F i for i, 1 i N, we know the "shape" of these matrices. Indeed, only ⌈log (D)⌉ × ⌈log (D)⌉ elements are non-zero, and we know the positions of these elements (see proof of Lemma. 4 for instance). The key is to use the upper triangular matrix representing this quadratic form instead of a symmetric matrix. We will use this knowledge to recover both W ′ and F i ′ , for i, 0 i < N. Let u (1)t be the first column U. Recall that F 1 * d,0 = F 1 , we have for instance

W ′ F 1 ′ * d,0 W ′t = (G 1 , . . . , G n ) u (1)t F 1 ′ = W ′-1 (G 1 , . . . , G n ) u (1)t W ′-t .
Equivalently, this amounts to solving the equations F 1 ′ -W ′-1 (G 1 , . . . , G n ) u (1)t W ′-t = 0. As in the even rank attack, we interpret the entries of W ′-1 as elements in F 2 . By doing this, the field equations can be added.

If we gather the equations coming from F 1 , . . . , F N , solving this system (one set of equations for each entry) is enough to recover W ′ and F ′ i for i, 1 i N. Note that this system is quadratic. It features equations of degree 2 in the variables from W ′ and linear in the variables from F i ′ . In this case again, the observed degree of regularity is not more than the degree of regularity of the MinRank step. The overall complexity is still bounded by the MinRank step.

Complexity Analysis of the MinRank Attack

In this section, we study the peculiarities of the MinRank arising in our attack, i.e. coming from [START_REF] Bosma | The Magma algebra system I: The user language[END_REF]. In [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF], it is conjectured that the basic Kipnis-Shamir attack against HFE is sub-exponential. The authors remarked that the algebraic system to be solved is greatly overdetermined. Recent results on solving MinRank [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] allow to have a fresher look at the complexity of MinRank-"type" key-recovery attacks against HFE and multi-HFE. For instance, from our experiments (described in the next section), we have remarked that the degree of regularity observed seems to be constant when d grows (d being the degree of the extension field). We explain theoretically this behavior using the formula (recalled in Sect. 2.4) on the degree of regularity of MinRank instances given in [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF]. In our case, the MinRank arising involves n matrices of size n × n and a target rank r = N ⌈log q (D)⌉. Thus, the MinRank considered are limited to instances of parameters (n, r, n). In this particular overdetermined case, we can get a precise bound under some conditions. Proposition 11 If the variant of the Fröberg Conjecture as defined in [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] is true, then the degree of regularity of the MinRank problem (n, r, n) is exactly r + 1 when r < 4 and n 6.

Proof As in Proposition 1, we introduce the following polynomials:

a i, j (t) = n-max(i, j) ∑ ℓ=0 n -i ℓ n -j ℓ t ℓ
and the corresponding r × r matrix A r (t) = [a i, j (t)]. According to Proposition 1, the index of the first negative coefficient of the power series

(1 -t) (n-r) 2 -n det A r (t) t ( r 2 ) (14)
gives the degree of regularity. To show that the degree of regularity is r + 1, we need then to show that the coefficient of t r+1 in ( 14) is the first negative coefficient. Equivalently, we show that the coefficient of

t r+1+( r 2 ) is the first negative coefficient in H r (t) = (1 -t) (n-r) 2 -n det A r (t) . (15)
We denote by F n-i (t) the polynomial a i,i (t). It is straightforward to show that:

F k (t) = (1 -t) k L k 1 + t 1 -t
where L n (X) is the n-th Legendre polynomial [START_REF] Szegö | Orthogonal Polynomials[END_REF].

We can compute immediately det(A 1 (t)) = F n-1 (t) so that

H 1 (t) = 1 + nt - 1 4 n n 3 -2 n 2 -n -2 t 2 + O t 3 .
The coefficients of t 0 and t 1 are clearly positive and the coefficient of t 2 is of the opposite sign of n 3 -2 n 2n -2; this coefficient is thus < 0 as soon as n > 2.7.

To compute H 2 (t), we need to express a 1,2 (t)(= a 2,1 (t)) in terms of F n-1 .

a 2,1 (t) = ∑ n-2 ℓ=0 n-2 ℓ n-1 ℓ t ℓ = ∑ n-2 ℓ=0 n-1-ℓ n-1 n-1 ℓ 2 t ℓ = ∑ n-2 ℓ=0 n-1 ℓ 2 t ℓ -1 n-1 t ∑ n-2 ℓ=0 n-1 ℓ 2 ℓt ℓ-1 = (F n-1 (t) -t n-1 ) -t n-1 ∂ ∂t (F n-1 (t) -t n-1 ) = F n-1 (t) -t n-1 F ′ n-1 (t)
. Hence, we can compute:

det (A 2 (t)) = F n-1 F n-1 -t n-1 F ′ n-1 F n-1 -t n-1 F ′ n-1 F n-2 = F n-1 F n-2 -(F n-1 -t n-1 F ′ n-1 ) 2 = t + (n -2) 2 t 2 + 1/2 n 2 -4 n + 5 (n -2) 2 t 3 + 1/36 5 n 2 -16 n + 20 (n -2) 2 (n -3) 2 t 4 + O t 5 .
Hence:

H 2 (t) = t + nt 2 + 1/2 n (n + 1)t 3 -1/36 n n 5 -6 n 4 + 13 n 3 -18 n 2 -14 n -12 t 4 + O t 5 .
Clearly all the coefficients of t 1 ,t 2 ,t 3 are positive and the coefficient of t 4 is negative as soon as n > 4.2.

When r = 3, we have

a 2,3 (t) = F n-2 -t n-2 F ′ n-2 a 1,3 (t) = F n-1 + t 2 F ′′ n-1 +2(2-n)t F ′ n-1 (n-1)(n-2)
We can compute explicitly Again the coefficients of t 3 ,t 4 ,t 5 and t 6 are obviously positive. Since the biggest real root of the coefficient of t 7 is ≈ 5.59 then it is negative when n > 5 ⊓ ⊔

det (A 3 (t)) = t 3 + (n -3) 2 t
Instead of computing all the coefficients H r given by equation ( 15), we can simply compute the coefficient of t r+1+( r 2 ) in H r (t).

Proposition 12

If the variant of the Fröberg Conjecture as defined in [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] is true, then the degree of regularity of the MinRank Problem (n, r, n) is less than r + 1 when r 10 and n 6.

Proof Let C r (n) be the coefficient of t r+1+( r 2 ) in H r (t). We have: ⊓ ⊔

C 10 = -
From the previous propositions (Proposition 11 and 12) it is natural to make the following conjecture.

Conjecture 1 Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 and let ℓ = ⌈log q (D)⌉.

The degree of regularity of the associated MinRank instances is bounded from above by (Nℓ + 1) when d is big enough.

Note that, by Proposition 11 and 12, the conjecture is proved for all n > 15 when Nℓ < 11, this covers all possible practical settings for HFE and Multi-HFE. To further validate the conjecture, we have instantiated the theoretical bound of Proposition1 with HFE/multi-HFE parameters for values of N 20 and ℓ 10. When d is sufficiently bigger than ℓ, we always obtain a degree of regularity equals to (Nℓ + 1). This has been verified for n = N d up to 500. Interestingly enough, the parameter d is not involved. In our context the degree of regularity depends only on the number N of secret variables and the degree D of the secret polynomials. We have then the necessary material to evaluate the difficulty of the MinRank involved in HFE/multi-HFE.

Proposition 13 If the variant of the Fröberg Conjecture as defined in [START_REF] Faugère | Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology[END_REF] is true, when N ℓ < 11, for N and ℓ fixed, the complexity of solving the MinRank arising in Multi-HFE is O d (Nℓ+1) ω 2 ω < 3 being the linear algebra constant and thus polynomial in d. Moreover if Conjecture 1, the previous complexity estimate is valid for any value of N and ℓ.

Proof According to Proposition 12, the degree of regularity is not more than (Nℓ + 1) and thus independent of the degree of the extension d. When d grows to infinity and according to Theorem 1 the complexity of the Gröbner basis computation is

O Nd+Nℓ+1 Nℓ+1 ω ∼ O (Nd) (Nℓ+1) ω ∼ O d (Nℓ+1) ω . ⊓ ⊔
This complexity refers to the number of arithmetic operations (in F q ) needed. This makes the binary complexity logarithmic in q. As a comparison, the complexity of a message recovery attack on HFE according to [START_REF] Ding | Inverting hfe systems is quasi-polynomial for all fields[END_REF] is polynomial in ℓ but exponential in q.

8 Attacks on Multi-HFE Variants

Multivariate-HFE -

In this section, we study a classical variant of multivariate schemes, the so-called "minus" modifier. It consists in removing some polynomials from the public key. We recall that this construction is only suitable for signature as the decryption is not unique.

Description.

Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 as defined in Sect. 2.1. We introduce a new parameter s ∈ N and the projection π : (F q ) n → (F q ) n-s . The public key is the mapping

G = π • T • ϕ -1 N • F * • ϕ N • S viewed as (n -s) polynomials in n variables. To sign, s random values from F q are appended to a digest m = (m 1 , . . . , m n-s ) ∈ F n-s q .
The signature is generated by applying the basic decryption process to such element. To verify a signature, we evaluate it on G .

Attack.

The goal is to find a valid private key with only (ns) public polynomials. Usually the minus modification is enough to prevent classical attacks as some information is missing. In particular, this is the case for the basic HFE (N = 1). However we have shown in Sect. 5 that the problem has N degrees of freedom. As a consequence, only (n -N + 1) matrices are needed to recover the (secret) kernel. This means that if the number of equation removed s is (strictly) smaller than N, then the kernel matrix K can be found with no additional cost. Still, the last steps of the attack have to be adapted.

The first step is as follows. We know that there exists a vector (λ 1 , . . . , λ n ) ∈ (F q ) n and symmetric

(n × n)- matrices ( 1 , . . . , s ) such that ker n-s ∑ i=1 λ i G i + s ∑ i=1 λ n-s+i i = K.
The i 's are unknown matrices corresponding to the removed polynomials. According to Theorem 7, we can fix N values λ i and still having solutions to our polynomial system. For instance, let

(λ n-N+1 , . . . , λ n ) = (ℓ 1 , . . . , ℓ N ).
We write

K • n-N ∑ i=1 λ i G i + N-s ∑ i=1 ℓ i G n-N+i + s ∑ i=1 ℓ N-s+i i = 0. (16)
The resulting system has n (n -Nℓ) linear equations in (n -N) + s n (n+1) 2 variables. The system is greatly underdetermined and hence have many solutions. To find the entries of i , we use the following remark: Proposition 14 For any j, 0 j < d, we have Frob j (K) • ∑ n i=1 λ q j i G i = 0.

Proof By definition, Frob j K • (∑ n i=1 λ i G i ) = 0. By linearity of the Frobenius, this is equal to:

Frob j (K) • Frob j n ∑ i=1 λ i G i = Frob j (K) • n ∑ i=1 λ q j i Frob j (G i ) .
As each G i has its entries in F q , we also have that Frob j (G i ) = G i . ⊓ ⊔ Solving equations ( 16) together with their Frobenius images forces the entries of i to be in F q . In order to avoid equations of degree q j coming from λ q j i , we add (d -1)(n-N) new variables (λ

1 , . . . , λ

n-N , . . . , λ

(d-1) 1 , . . . , λ (d-1)
n-N ). From Proposition 14, we get that ∀ j, 0 j < d:

Frob j (K) • n-N ∑ i=1 λ ( j) i G i + N-s ∑ i=1 ℓ q j i G n-N+i + s ∑ i=1 ℓ q j N-s+i i = 0.
The resulting system is overdetermined and has a solution if (ℓ 1 , . . . , ℓ N ) = (0, . . . , 0). We have to solve N times this linear system with different values for (ℓ 1 , . . . , ℓ N ) to get a valid matrix U as explained in Theorem 8.

Experimental Results

We present experimental results for the attack. It has been implemented in MAGMA [START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.16-10). MinRank instances have been solved using the Kipnis-Shamir modeling. Our results are presented in Table 3. We mounted our attack on a basic multi-HFE and on multi-HFE -with the same parameters As predicted, the minus modifier does not change the time of the MinRank attack but recovering W is a bit slower. As a conclusion, the private key of a multi-HFE -can be recovered with this technique almost as efficiently as the standard construction if the number of withdrawn equations is less than (N -1).

Multivariate-HFE with Embedding

In [START_REF] Ding | Algebraic attack on HFE revisited[END_REF], it has been proposed to use a variant of HFE with embedding. This so-called PHFE construction consists in removing/fixing few variables of the public key. This scheme is claimed to resist Kipnis-Shamir's attack [START_REF] Ding | Algebraic attack on HFE revisited[END_REF]. The authors of [START_REF] Chen | Odd-char multivariate Hidden Field Equations[END_REF] use the same modification on multi-HFE and claim that it prevents a possible "big-field" based attack. Still, for both PHFE and its multivariate version a key recovery attack is possible.

Description.

Let (F * , S , T ) be a multi-HFE private key with parameters (q, N, d, D) ∈ N 4 as defined in Sect. 2.1. We define a new parameter r ∈ N and the embedding ρ : (F q ) n-r → (F q ) n which is part of the private key. The public key is the mapping

G = T • ϕ -1 N • F * • ϕ N • S • ρ.
To encrypt a plaintext, we still evaluate G . To decrypt, as in the standard scheme, one inverts each component separately. To simplify, we can assume w.lo.g. that the embedding is always ρ 0 : (x 1 , . . . , x n-r ) ∈ (F q ) n-r → (x 1 , . . . , x n-r , 0, . . . , 0) ∈ (F q ) n . Indeed, from any embedding ρ and any invertible transformation S , one can find an invertible transformation S ′ such that S • ρ = S ′ • ρ 0 ; this gives equivalent keys.

Attack.

The matrix representation G i of the public key polynomials have (nr) rows and columns. However, the rank of ∑ n-1 i=0 u i,0 G i+1 remains bounded by N log q (D) (i.e. removing rows or columns does not increase the rank).

Let K = ker ∑ n-1 i=0 u i,0 G i+1 . As usual a matrix U ′ can still be recovered by solving a MinRank. The problem appears when trying to recover the matrix W ′ = S ′ M N,d where S ′ is an equivalent matrix (for the private key). By following the method described in Sect. 6.1.2, we get a system having Nℓ (nr -Nℓ) equations with only N (nr -N) variables. Let W ′ be a matrix solution of this linear system. This matrix is as follows:

W ′ =    
w 0,0 w q 0,0 . . . w q d-1 0,0 . . . . . . w 0,N-1 w q 0,N-1 . . . w q d-1 w n-r,0 w q n-r,0 . . . w q d-1 n-r,0 . . . . . . w n-r,N-1 w q n-r,N-1 . . .

w q d-1 n-r,N-1     .
This matrix W ′ has (nr) rows and thus is not invertible. However, such W ′ needs to be inverted in order to compute a full private key. The first idea is to build a new invertible matrix W r by appending to

W ′ a (r × n)-matrix V = [v i, j ] such that v q i, j = v i, j+1 . The secret inner mapping is reconstructed by computing G i ′ = W r -1 G i W r -t . As the matrix W r -1
has non-zero coefficients in its r last rows, so is G ′ i . Recall that the MinRank was done over (nr × nr)matrices. Therefore, when we finally compute ∑ n i=0 u i,0 G i+1 ′ , monomials in the last variables (x n-r+1 , . . . , x n ) are mixed with the other monomials. This eventually leads to polynomials that are not in HFE-shape (and then hard to invert).

To circumvent this issue, we no longer append a "quasi" random matrix to W ′ . Instead, we construct an invertible matrix W z by appending vertically to W ′ the matrix From the way it is constructed, W z is indeed invertible. The variables (x n-r+1 , . . . , x n ) do not appear in G i ′ = W z -1 G i W z -t , and the rank property is preserved. The only difference is that the relation w q i, j = w i, j+1 only holds for all i, 0 i < nr. The consequence is that S ′ = W z M -1 N,d has coefficients in the big field F q d . But, this is not an issue; S ′ can be inverted and a mapping F * with HFE-shape can be recovered.

Experimental Results

Experimental results are given in Table . 4. We compare the different steps of the attack on a basic multi-HFE to the same attack running on multi-HFE with embedding. In practice, the MinRank occurring in multi-HFE with embedding takes more time to break. However, the degree of regularity remains the same. Thus, there is only a constant factor between the complexity of solving a regular MR occurring in multi-HFE and a MR occurring in multi-HFE with embedding. As a conclusion, the embedding modifier does not add more security to the basic HFE/multi-HFE construction.

To further point out this weakness, we practically broke a 256 bits Multi-HFE scheme using embedding whilst a classical HFE instance with n = 256 bits is still intractable. In Table 5, we show our results on the parameters proposed in [13] (multi-HFE with embedding r = 1). The degree of regularity experimentally observed is noted d reg . The theoretical degree of regularity is denoted by d theo reg . The proposed parameters are not secure since they are practically broken (9 days for the most conservative, i.e. 256 bits claimed security). One may get even better results using the minors modeling of MinRank and the F 5 implementation available in the FGb software [START_REF] Faugère | FGb: A Library for Computing Gröbner Bases[END_REF].

Weaknesses of Multi-HFE relative to HFE

In light of our results, we conclude the paper by evaluating the real security gain offered by the Multi-HFE construction (w.r.t. basic HFE). In order to compare instances of HFE/multi-HFE with each other, we introduce and formalize the notion of "similarity" between two instances of multi-HFE.

Definition 3 Two multi-HFE instances of respective parameters (q 1 , N 1 , d 1 , D 1 ) and (q 2 , N 2 , d 2 , D 2 ) are similar iff i) q 1 = q 2 (same base field) ii) N 1 d 1 = N 2 d 2 (same public key size) iii) N 1 log q 1 (D 1 ) = N 2 log q 2 (D 2 ) (same private key size)

This definition is motivated by the following fact.

Property 1 Two similar instances of multi-HFE share the same size of public key and (almost) the same size of private key.

Proof The transformations S and T have the same size for two similar multi-HFE instances. Each secret polynomial can be written as a non-standard quadratic form on the q-th powers of the variables. As the degree is bounded by D, we have at most (N log q (D) + 1)(N log q (D) + 2)/2 monomials in each polynomial. We then have to store N (N log q (D) + 1)(N log q (D) + 2)(d log 2 (q)) bits.

⊓ ⊔

This definition includes HFE as it is a particular case of Multi-HFE (N = 1) To illustrate the concept of equivalent keys, we provide in Table 6 two multi-HFE parameters proposed by [START_REF] Billet | Analysis of Intermediate Field Systems[END_REF] and [START_REF] Chen | Odd-char multivariate Hidden Field Equations[END_REF]. The table shows the correspondence between their similar univariate instance, as well as the complexity of solving the MinRank for each set of parameters.

Note that this definition takes into account the size of the private key. The speed of decryption can vary a lot between two similar instances as pointed in Table 6. A different notion of similarity with respect to the speed of decryption could also be considered. The KS equations of two similar instances have the same number of variables and equations as the target rank is the same N log q (D). According to the complexity of the MinRank given in Proposition 13, the bigger is d, the harder it is to mount our attack. In particular, the case N = 1 (original HFE) is the more resistant. This behavior has also been verified experimentally. For similar keys, choosing N = 1 seems to be the optimal value for security. With respect to our attack, multi-HFE is then less secure than HFE. We consider an instance of HFE with the following parameters: q = 2, N = 1, d = 6, D = (q + 1) = 3, r = N ⌈log q (d)⌉ = 2. The private key is given in Fig. 3 and the public key in Fig. 4.       1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

         , G 6 =         
1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

        
. Fig. 4 Public key for a (Multi-)HFE with parameters q = 2, N = 1, d = 6, and D = 3.

As explained in Sect. 6.1.4, we can fix λ 1 = 1. However, the MinRank problem has still d (q d -1) = 6 × 63 = 378 solutions. We can fix one more variable as suggested in [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF]. For example, we fix λ 2 = θ . We have now only d = 6 solutions, i.e.:

(1, θ , θ 15 , θ , θ 61 , θ 50 ), (1, θ , θ 17 , θ 41 , θ , θ 30 ), (1, θ , θ 22 , θ 43 , θ 51 , θ 38 ), (1, θ , θ 28 , θ 53 , θ 24 , θ 60 ), (1, θ , θ 42 , θ 11 , θ 9 , θ 17 ), (1, θ , θ 45 , θ 20 , θ 32 , θ ).

We build the corresponding matrices K and T ′ . In the second step -recovering S ′ -the linear system KW = ker (F i ) has no solution. The computed T ′ is then not valid.

Using the technique described in Sect. 6.3, we have to solve a system of 68 equations in 50 variables. After fixing λ 1 = 1 and w ′ 0,0 = 1, the system is of dimension 0 and the solution is: Finally, the matrix T ′ can be recovered

T ′ =       
0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0

           
0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

         , G 4 =         
1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

         , G 5 =         
0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

         , G 6 =         
1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

        
. Fig. 6 Public key of a (Multi-)HFE with parameters: q = 2, N = 1, d = 6, and D = 3.

After fixing λ 1 = 1, the MinRank problem has d solutions. The solution are:

λ (1) = (1, θ 7 , θ 52 , θ 4 , θ 33 , θ 36 ) and all its Frobenius images. The matrix T ′ can be recovered normally:

T ′ =       
0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1

      
.

The first step of the attack runs pretty well and we are able to compute K. Nevertheless, one can remark that the kernel matrix of F 1 is ker(F 1 ) =     0 1 θ 9 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

    .     
1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 1

      
The polynomial F ′ 1 = θ 61 X 5 1 + θ 26 X 4 1 + θ 23 X 3 1 + θ 41 X 2 1 has HFE-shape and it can be verified that the recovered components are a valid equivalent key.

B Proofs from Section 3.2

Proof (Proposition 5) Let F = ∑ N-1 r=0,s=0 ∑ d-1 u=0,v=0 A r,s,u,v X q u r+1 X q v s+1 be a HFE-shaped polynomial and X = (X 1 , X q 1 , . . . , X q d-1

1 , . . . , X N , X q N , . . . , X q d-1 N

).

From the definition of the non-standard matrix representation, we have that F = X F X t with F = [ f i, j ] ∈ M n×n F q d and then A r,s,u,v = f r d+u,s d+v . Assume that F ′ = X F * d,k X t , we will prove that F ′ = F q k . From Definition 1, each element of F * d,k can be expressed from the f i, j 's. By construction of F * d,k , it is straightforward to show that F * d,k = [ f q k d ⌊i/d⌋+(i-k mod d),d ⌊ j/d⌋+( j-k mod d) ]. Then, the polynomial F ′ is:

F ′ = n-1 ∑ i=0 n-1 ∑ j=0 f q k
d ⌊i/d⌋+(i-k mod d),d ⌊ j/d⌋+( j-k mod d) X q i mod d ⌊i/d⌋+1 X q j mod d ⌊ j/d⌋+1 .

We do the replacement i ← r d + u and j ← s d + v. s+1 .

We shift the indexes u and v by k (i.e. u ← u + k, v ← v + k). As in (2) -as the indexes being computed mod d -we have

F ′ = N-1 ∑ r,s=0 d-1 ∑ u,v=0 f q k
d r+(u mod d),d s+(v mod d) X q u+k mod d r+1 X q v+k mod d s+1

F ′ = N-1 ∑ r,s=0 d-1 ∑ u,v=0 f d r+u,d s+v X q u r+1 X q v s+1 q k F ′ = N-1 ∑ r,s=0 d-1 ∑ u,v=0 A r,s,u,v X q u r+1 X q v s+1 q k F ′ = F q k .
This proves the proposition. ⊓ ⊔

Proof (Proposition 6)

The proof is very similar to the proof of Proposition 3. For i, j, 0 i, j < n, let m i, j be the (i, j)-th element of M N,d .

According to the definition of M N,d in Proposition 4, m i, j = 0 if ⌊i/d⌋ = ⌊ j/d⌋. For all i, j, 0 i, j < n, an element b i, j of B is then As a i, j ∈ F q (i.e. a q i, j = a i, j ) and since the Frobenius is linear, we get:

b q i,k d+(( j-1) mod d) = d-1 ∑ ℓ=0 a q i,k+ℓ θ j-1 ℓ+1 q = d-1 ∑ ℓ=0 a i,k+ℓ θ j ℓ+1 = b i,k d+ j . ⊓ ⊔

Fig. 2

 2 Fig. 2 Public key (given as matrices) of the Multi-HFE example considered with q = 7, N = 2, d = 4, and D = 14.

A Example of Key Recovery in Characteristic 2 A. 1

 21 47. Wolf C, Preneel B (2011) Equivalent keys in multivariate quadratic public key systems. Journal of Mathematical Cryptology 4(4):375-415 48. Zippel R (1979) Probabilistic algorithms for sparse polynomials. In: Symbolic and algebraic computation (EUROSAM'79), Internat. Sympos., Springer Verlag, Lecture Notes in Computer Science, vol 72, pp 216-226 Example for Even Rank

λ = ( 1 ,

 1 θ 9 , θ 5 , θ 28 , θ 41 , θ 15 ), θ 29 θ 41 0 0 1 0 θ 12 θ 39 0 0 0 1 θ 38 θ 21

  r+(u-k mod d),d s+(v-k mod d) r+(u-k mod d),d s+(v-k mod d) X q u r+1 X q v

1 ∑

 1 ⌊ j/d⌋+ℓ m ⌊ j/d⌋+ℓ, j = d-ℓ=0 a i,⌊ j/d⌋+ℓ θ j mod d ℓ+1 . Thus: b i,k d+(( j-1) mod d) = ∑ d-1ℓ=0 a i,k+ℓ θ j-1 ℓ+1 . Consequently:b q i,k d+(( j-1) mod d) = d-1 ∑ ℓ=0 a i,k+ℓ θ j-1 ℓ+1 q .

Table 1

 1 Parameters of various Multi-HFE instances found in several papers.

		q	N	d	D	security
	HFE [41]	2	1	128	513	128
	PHFE [20]	7	1	67	56	201
	IFS [6]	2	8	16	2	128
	THFE [14]	31	3	10	2	150

  d ) is the zero matrix with (d -ℓ) rows and ℓ (resp. d) columns, and I d-ℓ is the identity matrix with (d -ℓ) rows and columns. Then, the rows of the matrix K N,d,ℓ are a basis of the left kernel of F k with high probability and does not depend on the entries of F k .

Proof Each polynomial F k has degree bounded by D, for k, 1 k N, thus each variable X i has at most degree D, for all i, 1 i N. The only non-zero entries of the matrix F k are the ones in the upper-left log q (D) square of each N × N block of size (d × d). Thus, F k has at most Nℓ non-zero rows and columns and has the following structure

  1 1 1 θ 110 θ 770 θ 590 θ 1730 θ 1587 θ 1509 θ 963 θ 1941 θ 2215 θ 1105 θ 535 θ 1345 θ 2150 θ 650 θ 2150 θ 650 θ 830 θ 1010 θ 2270 θ 1490 θ 59 θ 413 θ 491 θ 1037 θ 1958 θ 1706 θ 2342 θ 1994 θ 1111 θ 577 θ 1639 θ 1873 θ 1889 θ 1223 θ 1361 θ 2327 θ 1093 θ 451 θ 757 θ 499 θ 2363 θ 2141 θ 587 θ 1709 θ 1656 θ 1992 θ 1944 θ 1608

  1 1 1 θ 75 θ 525 θ 1275 θ 1725 θ 505 θ 1135 θ 745 θ 415 θ 66 θ 462 θ 834 θ 1038 θ 1673 θ 2111 θ 377 θ 239 θ 314 θ 2198 θ 986 θ 2102 θ 1960 θ 1720 θ 40 θ 280 θ 132 θ 924 θ 1668 θ 2076 θ 1947 θ 1629 θ 1803 θ 621 θ 1308 θ 1956 θ 1692 θ 2244 θ 733 θ 331 θ 2317 θ 1819 θ 2017 θ 2119 θ 433 θ 631 θ 1788 θ 516 θ 1212 θ 1284

  -242 n 3 + 1067 n 2 -2268 n + 1980 (n -3) 2 (n -4) 2 t 7 + O t 8 -12 n 6 + 58 n 5 -144 n 4 + 169 n 3 -276 n 2 -228 n -144 t 7 + O t 8 .

	4 + + + 1 2 576 n 2 -6 n + 10 (n -3) 2 t 5 1 6 n 2 -6 n + 10 n 2 -6 n + 11 (n -3) 2 t 6 1 n (n + 1)t 5 + 1 6 n (n + 2) (n + 1)t 6 23 n 4 and deduce that H 3 (t) = t 3 + nt 4 + 1 2 -1 576 n n 7

  1 1593350922240000 (n 21 -110 n 20 + 5665 n 19 -181500 n 18 + 4054446 n 17 -67075140 n 16 + 852003130 n 15 -8501266400 n 14 +67608163381 n 13 -432299636670 n 12 +2232012515445 n 11 -9309555172500 n 10 +31264617802396 n 9 -84016440120800 n 8 + 177471642248560 n 7 -299981580148800 n 6 + 330208359091776 n 5 -468532034657280 n 4 -130151988172800 n 3 -586220360140800 n 2 -411093107712000 n -144850083840000) n. C 9 = -1 13168189440000 (n 19 -90 n 18 +3765 n 17 -97200 n 16 +1733946 n 15 -22676220 n 14 +225084130 n 13 -1731961800 n 12 + 10460514381 n 11 -49893169050 n 10 + 188094067545 n 9 -558407719800 n 8 + 1288998059896 n 7 -2330497406880 n 6 + 2826910578960 n 5 -3910275907200 n 4 -721132948224 n 3 -5000541557760 n 2 -3593557094400 n -1316818944000) n. C 8 = -1 131681894400 (n 17 -72 n 16 +2388 n 15 -48384 n 14 +669606 n 13 -6704208 n 12 +50170300 n 11 -285855552 n 10 + 1251320145 n 9 -4215469608 n 8 +10855779816 n 7 -21379728384 n 6 +28864042768 n 5 -39461075712 n 4 -2881845504 n 3 -51701690880 n 2 -38140139520 n -14631321600) n. C 7 = -1 1625702400 (n 15 -56 n 14 + 1428 n 13 -21952 n 12 + 226982 n 11 -1667568 n 10 + 8962364 n 9 -35733376 n 8 +105954513 n 7 -233382296 n 6 +356137768 n 5 -490476672 n 4 +30217104 n 3 -661207680 n 2 -501500160 n-203212800) n. C 6 = -1 25401600 (n 13 -42 n 12 +791 n 11 -8820 n 10 +64743 n 9 -328986 n 8 +1184153 n 7 -3039960 n 6 +5376616 n 5 -7669872 n 4 + 1745856 n 3 -10725120 n 2 -8372160 n -3628800) n. C 5 = -1 518400 (n 11 -30 n 10 +395 n 9 -3000 n 8 +14523 n 7 -46710 n 6 +100085 n 5 -154500 n 4 +67876 n 3 -227760 n 2 -182880 n -86400) n. C 4 = -1 14400 n 9 -20 n 8 + 170 n 7 -800 n 6 + 2273 n 5 -4100 n 4 + 2980 n 3 -6600 n 2 -5424 n -2880 n. It is easy to check that the biggest real root of C 4 ,C 5 ,C 6 ,C 7 ,C 8 ,C 9 ,C 10 are approximately: 7.03, 8.45, 9.86, 11.3, 12.7, 14.1, 15.5 As a consequence, C 4 ,C 5 ,C 6 ,C 7 ,C 8 ,C 9 ,C 10 are all negative when n > 15.

Table 3

 3 Comparison of each step of our attack on minus variant on multi-HFE with parameters q = 31, N = 3, d = 8, D = 2 (≈ 120 bits security) using a MAGMA[START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.16-10) implementation on a 2.93 GHz Intel R Xeon R CPU.

		MR time	MR d reg	Finding U Finding W
	No variant (ref. time)	23.3 s	3	0.01 s	7.29 s
	Minus (s = 1)	23.2 s	3	0.01 s	16.71 s
	Minus (s = 2)	23.4 s	3	0.01 s	35.24 s
	Minus (s = 3)		Not possible

Table 4

 4 Comparison of each step of our attack on embedding variant on multi-HFE with parameters q = 31, N = 3, d = 8, D = 2 (≈ 120 bits security) using a MAGMA[START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.16-10) implementation on a 2.93 GHz Intel R Xeon R CPU.

		MR time	MR d reg	Finding U Finding W
	No variant (ref. time)	23.3 s	3	0.01 s	7.29 s
	Embedding (r = 1)	788 s	3	0.01 s	6.14 s
	Embedding (r = 2)	2811 s	3	0.01 s	5.25 s
	Embedding (r = 3)	401 s	3	0.01 s	4.44 s

Table 5

 5 MinRank attack on real-scale parameters from [13] using a MAGMA[START_REF] Bosma | The Magma algebra system I: The user language[END_REF] (V2.16-10) implementation of Kipnis-Shamir modeling and a FGb[START_REF] Faugère | FGb: A Library for Computing Gröbner Bases[END_REF] implementation of the minors modeling on a 2.93 GHz Intel R Xeon R CPU.

	q	N	d	D	security	d theo reg	Time MAGMA	Mem. MAGMA	Time FGb	d reg
	31	2	15	2	150 bits	3	2 min 27 s	434 MB	21.1 s	3
	31	3	10	2	150 bits	4	1 h 38 min	1.5 GB	24 min 56 s	3
	31	3	15	2	192 bits	4	2 days 1 h	12 GB		3
	31	3	18	2	256 bits	4	9 days 16 h	33 GB		3

Table 6

 6 Similar univariate HFE parameters for multi-HFE instances. The two sets of parameters in each line provide the same general security (key sizes and message space) but the decryption speed and the complexity of our attack vary a lot.

		q	N	d	D	msg space pub (bits)	priv (bits)	decr. time	MinRank comp.
	IFS HFE	2 2	8 1	16 128	2 192	128 bits 128 bits	2130048 2130048	39042 38018	0.610 s. 0.120 s.	16 9 ω = 2 36 ω 128 9 ω = 2 63 ω
	THFE 31 HFE 31	3 1	10 30	2 1922	150 bits 150 bits	144150 144150	11110 11110	< 0.001 s. ≈ 10 s.	10 3 ω ≈ 2 10 ω 30 3 ω ≈ 2 15 ω

Acknowledgments

We would like to thank C. Wolf for his comments on a preliminary version of this paper. We also would like to thank the referees for their meaningful comments. The work described in this paper has been supported in part by the European Commission through the ICT program under contract ICT-2007-216676 ECRYPT II. The authors were also supported in part by the french ANR under the Computer Algebra and Cryptography (CAC) project ANR-09-JCJCJ-0064-01.

Luk Bettale was partially supported by DGA/MRIS (french secretary of defense).

The matrix has 1 column set to zero instead of 3 leading to an underdetermined linear system when we consider KW = ker(F 1 ). We can try to fix more variables in such system. For instance:

is a possible solution to our system. However, when we use it as in Sect. 6.1.4 to build the matrix W ′ , W ′ is not invertible, making the full key recovery impossible. Another possible solution is w (1) = (1, θ 5 , θ 12 , θ 36 , θ 34 , θ 6 ).

In this case, W ′ is invertible. But, we have:

1 + θ 26 X 5 1 + θ 18 X 4 1 + θ 59 X 3 1 + θ 61 X 2