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

Danilo Gligoroski
email: danilog@item.ntno.no

Ludovic Perret
email: ludovic.perret@lip6.fr

Simona Samardjiska
email: simonas@item.ntno.no

Enrico Thomae
email: enrico.thomae@rub.de

A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems

Keywords: MQ cryptography, MQQ cryptosystems, Equivalent keys, Good keys, MinRank, Gröbner bases

We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack. Our key-recovery attack finds an equivalent key using the idea of so-called good keys that reveals the structure gradually. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic 2 which is known to be the most difficult case to address in theory for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key, that is, using the minus modifier. This was not the case for previous MinRank like-attacks against MQ schemes. From a practical point of view, we are able to break an MQQ-SIG instance of 80 bits security in less than 2 days, and one of the more conservative MQQ-ENC instances of 128 bits security in little bit over 9 days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.

Introduction

Multivariate quadratic (MQ) public key schemes are cryptosystems based on the NP-hard problem of solving polynomial systems of quadratic equations over finite fields, also known as the MQ-problem. Until the mid 2000's, MQ cryptography was developing very rapidly, producing many interesting and versatile design ideas such as C * [START_REF] Imai | Algebraic methods for constructing asymmetric cryptosystems[END_REF], HFE [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF], SFLASH [START_REF] Courtois | Sflash, a fast asymmetric signature scheme for low-cost smartcards -primitive specification and supporting documentation[END_REF], UOV [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF], TTM [START_REF] Moh | A public key system with signature and master key functions[END_REF], TTS [START_REF] Yang | Tts: High-speed signatures on a low-cost smart card[END_REF]. However, many of them were soon successfully cryptanalysed, and the biggest surprise was probably the break of SFLASH in 2007 [START_REF] Dubois | Practical cryptanalysis of SFLASH[END_REF], shortly after it was chosen by the NESSIE European Consortium [START_REF]NESSIE: New european schemes for signatures, integrity, and encryption[END_REF] as one of the three recommended public key signature schemes. As a consequence, the confidence in MQ cryptosystems declined, and as a result, did the research in this area as well. Now, several years later, it seems that there have emerged new important reasons for renewal of the interest in MQ cryptography. First, in the past two years, the algorithms for solving the Discrete Logarithm (DL) problem underwent an extraordinary development (for instance, but not limited to [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]). The confidence in the hardness of the DL problem has been seriously rocked, and finding an algorithm that will show that this problem is in fact easy does not look as impossible as previously believed. Consequently, the mid and long term security of an array of cryptosystems based on the hardness of the DL problem over various groups is no longer clear. Second, two of the most important standardization bodies in the world, NIST and ETSI have recently started initiatives for developing cryptographic standards not based on number theory, with a particular focus on primitives resistant to quantum algorithms [10,[START_REF]ETSI: ETSI 2nd Quantum-Safe Crypto Workshop in partnership with the IQC[END_REF].

A common characteristic for all MQ schemes is the construction of the public key as P = T • F • S where F is some easily invertible quadratic mapping, masked by two bijective affine transformations S and T . A consequence of these construction is that some specific properties of the secret-key can be recovered on the public-key. In particular, one of the most important characteristic of MQ schemes that allows a successful key-recovery is connected to unexpected high rank defect on the matrices associated to the public-key. The attacks on TTM [START_REF] Courtois | Cryptanalysis of the TTM cryptosystem[END_REF], STS [START_REF] Wolf | On the security of stepwise triangular systems[END_REF][START_REF] Thomae | Cryptanalysis of Enhanced TTS, STS and all its Variants, or: Why Cross-Terms are Important[END_REF], Rainbow [START_REF] Billet | Cryptanalysis of Rainbow[END_REF], HFE and MultiHFE [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF][START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF][START_REF] Bettale | Cryptanalysis of multivariate and odd-characteristic hfe variants[END_REF][START_REF] Bettale | Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic[END_REF] are all in essence based on the problem of finding a low rank linear combination of matrices, known as MinRank in cryptography [START_REF] Buss | The computational complexity of some problems of linear algebra[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]. Although NP-hard, the instances of MinRank arising from MQ schemes are often easy, thus providing a powerful tool for finding equivalent keys in canonical form.

Our Contribution

In this paper, we are concerned with the security analysis of a particular family of MQ (Multivariate Quadratic) cryptosystems, namely the MQQ schemes proposed in 2008 [START_REF] Gligoroski | Multivariate Quadratic Trapdoor Functions based on Multivariate Quadratic Quasigroups[END_REF]. In these schemes the secret mapping F is derived from multivariate quadratic quasigroups (MQQ), which makes the inversion of F especially efficient. A message-recovery attack was proposed in [START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF], and later in [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF], it was proven that a direct attack [START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF] can be done in polynomial-time. In [START_REF] Gligoroski | MQQ-SIG -An Ultra-Fast and Provably CMA Resistant Digital Signature Scheme[END_REF], the authors proposed a signature scheme, called MQQ-SIG, based on the same idea and secure against direct attacks, as well as claimed to be CMA secure. They made heavy use of the minus modifier, known from HFE- [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF], to repair MQQ. Finally, in [START_REF] Gligoroski | The Multivariate Probabilistic Encryption Scheme MQQ-ENC[END_REF] the authors proposed an enhanced variant of the MQQ encryption scheme, called MQQ-ENC. The MQQ-SIG signature scheme is the fastest scheme in signing in the ECRYPT Benchmarking of Cryptographic Systems (eBACS) SUPERCOP [START_REF] Bernstein | ebacs: Ecrypt benchmarking of cryptographic systems[END_REF], and is therefore very appealing for practical use. We show in this paper that this family of designs has a fundamental weakness which allows us to mount an efficient key-recovery attack on all known constructions based on MQQ. More precisely, we can recover a key-equivalent to the secret-key by solving simultaneous instances of MinRank (Theorem 3) problems which due to the structure of the schemes can be solved in polynomial-time.

To do so, we first assume that the field is not to big. That is to say, we assume that q = O(n) which is indeed the case for most of the parameters proposed so far for MQQ cryptosystems. Of independent interest, we show that the simultaneous MinRank problem is equivalent to a rectangular MinRank (Corollary 1) problem. For the complexity of our attack, we summarize the first result below: Theorem 1. Let ω, 2 ≤ ω < 3 be the linear algebra constant. Let P = T • F • S be the public mapping of MQQ-SIG or MQQ-ENC consisting of n -r polynomials in n variables over F q (with Char(F q ) = 2). F is a set of quadratic polynomials derived from multivariate quadratic quasigroups (MQQ), while S and T are invertible matrices used to mask the structure of F. Then, the last columns of S and T (up to equivalence) can be recovered in O(n ω ). More generally, a key equivalent to the secret-key in MQQ-SIG or MQQ-ENC can be found by solving n -r MinRank instances with N -r matrices from F N ×(N -r) q

where N, r + 2 ≤ N ≤ n -1. If q = O(n) then each MinRank can be solved in polynomial-time assuming a mild regularity condition on the public-matrices. Under this condition and assuming q = O(n), we can recover a key equivalent to the secret-key in O(n ω+3 ), with probability 1 -1/q. The genericity assumption required in the previous result is that the rank defect in the skewsymmetric matrices derived from the public polynomials is not too big a constant. We have implemented our attack in practice and verified that this assumption is reasonable. We highlight that our theoretical results work in characteristic 2 which is known to be the most difficult case to address in theory [START_REF] Jiang | Kipnis-Shamir attack on HFE revisited[END_REF][START_REF] Bettale | Cryptanalysis of multivariate and odd-characteristic hfe variants[END_REF][START_REF] Bettale | Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic[END_REF] for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key (the minus modifier). This was not the case for previous MinRank like-attacks against MQ schemes. If we relax the condition on the size of q, we can still bound the complexity (although, we require a slightly stronger assumption).

Theorem 2 (informal version of Theorem 5). Let ω, 2 ≤ ω < 3 be the linear algebra constant. Let P = T •F •S be the public mapping of MQQ-SIG or MQQ-ENC consisting of n-r polynomials in n variables over F q (with Char(F q ) = 2). Assuming that the kernels of the skew-symmetric matrices derived from the public-key behave as random subspaces and a genericity condition on the MinRank modeling, then we can then recover a key-equivalent to the secret-key in

O n 3 ω+1 , with probability 1 -1 q 1 -1 q n-3 . (1)
The assumption used in Theorem 2 means that we can restrict our attention to a sub-system of our modeling of the simultaneous MinRank (Theorem 3) such that the sub-system is bi-linear with a block of variables of constant size. If the sub-system behaves as a generic affine bi-linear system, this implies that maximum degree reached during a Gröbner basis computation is constant [START_REF] Faugère | Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity[END_REF]. This is what we observed in practice. Indeed, in order to verify our assumptions and the correctness of the attack, we implemented the attack in Magma (Version 2. 19-10 [29]). The codes have been provided with the submission. The results obtained confirm the computed theoretical complexity. Using the implementation, we demonstrated that our attack is very efficient by practically breaking instances with recommended parameters. For example, we recovered an equivalent key for MQQ-SIG 160, of claimed security of O(2 80 ) in 2 48 operations, i.e. in less than 2 days. Similarly, for MQQ-ENC 128 defined over F 4 with claimed security of O(2 128 ), we recovered an equivalent key in 2 50.6 operations which took a little bit over 9 days. We also emphasize that the practical results obtained, almost perfectly match the theoretical complexity bound (1) derived in Section 7.1. Altogether, our attack shows that it is very hard to design a secure scheme based on an easily invertible MQQ structure. It seems that using MQQs successfully in future MQ designs may require deep insight from quasigroup theory, in order to obtain the necessary security while preserving the attractive performance level.

Organization of the Paper

The paper is organized as follows. In Sect. 2 we present the necessary preliminaries about MQ cryptosystems. We also recall the MinRank problem and the known tools for solving it, as well as the concepts of equivalent keys and good keys. In Sect. 3 we describe the cryptosystems from the MQQ family, and in Sec. 4 we uncover the algebraic structure that the two systems, MQQ-SIG and MQQ-ENC share, and that shows the weaknesses of the cryptosystems. Sect. 5 is devoted to the presentation of the main idea behind our key recovery attack on both MQQ-ENC and MQQ-SIG. We further point out the difference in the attack in odd and even characteristic fields, and present the necessary modifications of the attack for even characteristic fields. As a result of the analysis, in Sect. 6 we conclude that the problem of finding good keys can be modeled as a special instance of MinRank for rectangular matrices. The complexity analysis of our attack is given in Sect. 7. We conclude the paper in Sect. 8.

Preliminaries

Basic Notations

Throughout this paper, F q will denote the finite field of q elements. First, we briefly recall the general principle of MQ public key cryptosystems. This will allow to fix some notations. The public key of a MQ cryptosystem is usually given by a multivariate quadratic map P : F n q → F m q , that is

P(x 1 , . . . , x n ) :=       p 1 (x 1 , . . . , x n ) = 1≤i≤j≤n γ (1)
ij x i x j + n i=1 β (1)
i x i + α (1) . . .

p m (x 1 , . . . , x n ) = 1≤i≤j≤n γ (m) ij x i x j + n i=1 β (m) i x i + α (m)      
for some coefficients γ

(s) ij , β (s)
i , and α (s) ∈ F q . In our attack, we will see that w.l.o.g. we can restrict our attention to the homogeneous components of highest degree, i.e. to the quadratic components. Classically, a quadratic form can be written as

p s (x 1 , . . . , x n ) := 1≤i≤j≤n γ (s) ij x i x j = x P (s)
x, where x = (x 1 , . . . , x n ) and P (s) is an n × n matrix describing the degree-2 homogeneous component of p s . The public key P is obtained by obfuscating a structured central map F : x ∈ F n q → f 1 (x), . . . , f m (x) ∈ F m q . We denote by F (s) a (n × n) matrix describing the homogeneous quadratic part of f s . In order to hide the structured central map, we choose two secret linear1 transformations S, T ∈ GL n (F q ) and define the public key as

P := T •F •S.
Remark 1. It is known that the matrix of a quadratic form is constructed differently depending on the parity of the field characteristic. In odd characteristic, P (s) is a symmetric matrix, i.e. P (s)

ij := γ (s) ij /2 for i = j and P (s) ii := γ (s)
ii . Over fields F q of characteristic 2, we cannot choose P (s) in this manner, since ( γ ij + γ ji )x i x j = 2 γ ij x i x j = 0 for i = j. Instead, let P (s) be the upper-triangular representation of p s , i.e.

P (s) ij = γ (s) ij for i ≤ j.
The symmetric form is obtained by P (s) := P (s) + P (s) . In this case only the upper-triangular part represents the according polynomial, and all elements on the diagonal are zero. This implies that for x, y ∈ F n q the symmetric bilinear form x P (s) y is alternating and has even rank.

The MinRank Problem

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]. The MinRank problem over a finite field F q is as follows.

MinRank (MR) Input: n, m, r, k ∈ N, where n < m and M 0 , M 1 , . . . , M k ∈ M n×m (F q ). Question: Find -if any -a k-tuple (λ 1 , . . . , λ k ) ∈ F k q such that: Rank k i=1 λ i M i -M 0 r.
In Appendix A, we review some known techniques for solving MinRank.

Good Keys

Our attack relies on so-called equivalent keys introduced by Wolf and Preneel [START_REF] Wolf | Large Superfluous Keys in Multivariate Quadratic Asymmetric Systems[END_REF][START_REF] Wolf | Equivalent Keys in Multivariate Quadratic Public Key Systems[END_REF]. We briefly recall below the concept of equivalent keys, and then present good keys which are at the core of our attack.

Let F = {f 1 , . . . , f m } ⊂ F m q [x 1 , . . . , x n ]. For k, 1 ≤ k ≤ m, we denote by I (k) ⊆ {x i x j | 1 ≤ i ≤ j ≤ n} a subset of the degree-2 monomials. We define by F I = {f 1 I (1) , . . . , f m I (m) } where f k I (k) := x i x j ∈I (k) γ (k) ij x i x j is the restriction of f k to I (k) . Definition 1. Let (F, S, T ) and (F , S , T ) be in F q [x 1 , . . . , x n ] m × GL n (F q ) × GL m (F q ).
We say that (F, S, T ) and (F , S , T ) are equivalent keys, denoted by (F, S, T ) (F, S , T ), if and only if

(T • F • S = T • F • S ) ∧ F I = F I
, that is, F and F share the same structure when restricted to a fixed set I = {I (1) , . . . , I (m) }.

Since the relation given by Definition 1 is an equivalence relation [START_REF] Wolf | Large Superfluous Keys in Multivariate Quadratic Asymmetric Systems[END_REF], the set of all keys S, T can be partitioned into several equivalence classes. For a large fraction of all equivalence classes, we can find special representatives S and T with fixed entries at certain values. For ease of notation, let S := S -1 and T

:= T -1 . Obviously P = T •F •S, implies that F = T •P •S.
This leads to the equality below on the quadratic forms:

F (k) = S   n j=1 t kj P (j)   S, ∀k, 1 ≤ k ≤ m.
(2)

The corresponding system of equations is as follows:

F (k) ij = n x=1 n y=1 n z=1 P (x) yz t kx s yi s zj . (3)
Due to the structure of the secret mapping F, we know that certain coefficients in F (i) are systematically zero. This allows then to obtain cubic equations on the components of S and T . In general, the system of equations has too many variables for being solved efficiently in this form. The concept of equivalent keys allows to reduce the number of variables by introducing two linear maps (Σ,

Ω) ∈ GL m (F q ) × GL n (F q ) such that P = T • Σ -1 • Σ • F • Ω • Ω -1 • S. If F and F := Σ • F
• Ω share the same structure (cf. Def. 1), then T := T Σ -1 and S = Ω -1 S will be equivalent keys. Depending on Σ and Ω we can define a canonical form of the secret-keys and typically fix large parts of T and S (see [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][START_REF] Wolf | Equivalent Keys in Multivariate Quadratic Public Key Systems[END_REF]). We note that it may happen that such a canonical key does not exist. For example, the Unbalanced Oil and Vinegar Scheme has such an equivalent key with probability roughly 1 -1/q [START_REF] Thomae | About the Security of Multivariate Quadratic Public Key Schemes[END_REF].

The idea of good keys [START_REF] Thomae | Cryptanalysis of Enhanced TTS, STS and all its Variants, or: Why Cross-Terms are Important[END_REF] is to further decrease the number of unknowns or unfixed coefficients in (S , T ). Here, we do not aim to preserve all the zero coefficients of F, but just some of them. This way, we have more freedom to choose Σ and Ω and thus further reduce the number of variables. On the other hand, we can generate less equations. Finding the best trade-off is not obvious and strongly depends on the underlying structure of F. Formally, we define good keys through the following definition.

Definition 2 ([14]

). Let (F, S, T ), and (F , S , T ) be in 1) , . . . , I (m) } and J = {J (1) , . . . , J (m) } such that J (k) I (k) for all k, 1 ≤ k ≤ m with at least one J (k) = ∅. We shall say that (F , S , T ) ∈ F q [x 1 , . . . , x n ] m × GL n (F q ) × GL m (F q ) is a good key for (F, S, T ) if and only if:

F q [x 1 , . . . , x n ] m × GL n (F q ) × GL m (F q ). Let I = {I (
T • F •S = T • F •S ∧ F J = F J

MQQ Cryptosystems

The Multivariate Quadratic Quasigroup (MQQ) scheme was proposed in 2008 [START_REF] Gligoroski | Multivariate Quadratic Trapdoor Functions based on Multivariate Quadratic Quasigroups[END_REF]. The underlying idea is to use bijective multivariate quadratic maps, obtained through the existence of left and right inverses in some quasigroup, in order to build the trapdoor map F.

Definition 3. Let Q be a set and q : Q × Q → Q be a binary operation on Q. We call (Q, q) a left (resp. right) quasigroup if ∀ u, v ∈ Q, ∃! x, y ∈ Q : q(u, x) = v (resp. q(y, u) = v).
If (Q, q) is both left and right quasigroup, then we simply call it a quasigroup.

Clearly, q defines a bijective map if we fix some u ∈ Q. Hence, we can define two inverse operations q \ (u, v) = x and q / (v, u) = y, called left and right parastrophe, respectively. A multivariate quadratic quasigroup (MQQ) is a special quasigroup, that can be described through a multivariate quadratic map over some finite field F q . In [START_REF] Gligoroski | Multivariate Quadratic Trapdoor Functions based on Multivariate Quadratic Quasigroups[END_REF] F 2 is used to built such MQQs of order 2 d , with parameter d = 5 and bilinear maps q. The central map F was constructed using a so called quasigroup string transformation of the MQQs, in order to scale the number of variables.

Definition 4. Let Q := F d q and q i : Q × Q → Q be such that (Q, q i ) forms a quasigroup for 1 ≤ i ≤ and some parameter which allows to scale the scheme later on. We fix some element u ∈ Q, call it leader and define F :

F d q → F d q through (f 1 , . . . , f d ) := q 1 (u, x 1 ), (f d+1 , . . . , f 2d ) := q 2 (x 1 , x 2 ), . . . . . . (f ( -1)d+1 , . . . , f d ) := q (x -1 , x ).
In order to find pre-images of F, we use the corresponding left-parastrophe operations of q 1 , . . . , q .

In addition, the authors of [START_REF] Gligoroski | Multivariate Quadratic Trapdoor Functions based on Multivariate Quadratic Quasigroups[END_REF] used the Dobbertin bijection to deal with the linear part of F that comes from q 1 (u, x 1 ) for some fixed u ∈ Q and the fact that they chose bilinear maps q i .

Unfortunately this trapdoor provided a lot of structure so the MQQ encryption scheme was broken by a direct attack on the public key [START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF]. Faugère et al. showed in [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF] that the degree of regularity of the equations generated by the pubic key can be bounded from above by a small constant. Thus, the complexity of a direct Gröebner basis attack is polynomial.

MQQ-SIG Signature Scheme

Recently in [START_REF] Gligoroski | MQQ-SIG -An Ultra-Fast and Provably CMA Resistant Digital Signature Scheme[END_REF] a signature scheme was proposed, called MQQ-SIG, which is based on the same idea but makes heavy use of the minus modifier, known from HFE- [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF]. MQQ-SIG does not use the Dobbertin bijection and the construction of the quasigroup is different and given by the map

q : F d 2 × F d 2 → F d 2 : q(x, y) := B • (I + A 0 ) • B 2 • y + B • B 1 • x + c, (4)
where x = (x 1 , x 2 , . . . , x d ) , y = (y 1 , y 2 , . . . , y d ) , and

c ∈ F d 2 and B 1 , B 2 , B ∈ GL d (F 2 ) are arbitrary. The matrix A 0 is a d × d block matrix A 0 = [ 0 U 1 • B 1 • x U 2 • B 1 • x . . . U d-1 • B 1 • x ] ,
where U i , i ∈ {1, . . . d -1} are upper triangular matrices over F 2 having all elements 0 except the elements in the rows from {1, . . . , i} that are strictly above the main diagonal.

A key feature of the MQQ-SIG scheme is the application of the minus modifier. In particular, n/2 of the equations are removed in the public key P, in order to prevent direct algebraic and MinRank attacks. Therefore, we obtain a signature expansion of factor two for messages of length n/2. Further the public key is rather large, since it is defined over F 2 . In order to reduce the size of the public key the designers decided to split the message in two and sign it using twice the same trapdoor function. The proposed parameters are n ∈ {160, 192, 224, 256} for the trapdoor function for security levels of 2 80 , 2 96 , 2 112 , 2 128 binary operations respectively, and d = 8 for the order 2 d of the quasigroup.

MQQ-ENC Encryption Scheme

The encryption scheme MQQ-ENC was recently proposed in [START_REF] Gligoroski | The Multivariate Probabilistic Encryption Scheme MQQ-ENC[END_REF], and it follows the same line of design as its predecessors. Again, the internal mapping F is a quasigroups string transformation and the affine secrets S and T are built from two circulant matrices. The minus modifier is used again, but since it is an encryption scheme, only a small fixed number r of polynomials is removed. This destroys the bijectivity of P, so to enable correct decryption a universal hash function is used, and decryption is performed by going through all possible pre-images of P. Compared to its predecessors, MQQ-ENC can be defined over any small field F p k and instead of bilinear quasigroups, the authors used more general left quasigroups, i.e. mappings that are bijections only in the second variable.

Lemma 1 ([35]

). Let p be prime and k > 0 be an integer. For all s, 1 ≤ s ≤ d, we define the component q s ∈ F p k [x 1 , . . . , x d , y 1 , . . . , y d ] by:

q s := p s (y s ) + 1≤i,j≤d α (s) i,j x i x j + s<i,j≤d β (s) i,j y i y j + 1≤i≤d,s<j≤d γ (s) i,j x i y j + 1≤i≤d δ (s) i x i + s<i≤d (s) i y i + η (s) , (5)
where p s (y s ) ∈ {a (s) y s , a (s) y 2 s } for even p, and p s (y s ) = a (s) y s for odd p, for some a (s) = 0. The function q = (q 1 , q 2 , . . . , q d ) :

F 2d p k → F d p k as defined in (5) defines a left multivariate quadratic quasigroup (LMQQ) (F d p k , q) of order p kd .
Lemma 2. Let (F d p k , q) be an LMQQ as defined by Lemma 1. Let D and D y be d × d nonsingular matrices and c, c y vectors of dimension d over F p k . Then q(x, y) := D • q(x, D y • y + c y ) + c is again an LMQQ of order p kd . We say that q is linearly isotopic to q.

The recommended values for the parameters n, k, r, d, p for a security level of 2 128 are d = 8, p = 2 and (n, k, r) ∈ {(256, 1, 8), (128, 2, 4), (64, 4, 4), (32, 8, 1)}.

The Algebraic Structure of MQQ-ENC and MQQ-SIG

We explain the algebraic structure that both MQQ-ENC and MQQ-SIG share. This is the weaknesses that we are going to exploit to mount our attack. First of all, we note that the trapdoor of MQQ-SIG can be seen as a very special case of MQQ-ENC when defined over F 2 . Indeed, the quasigroup string transformation only makes use of the left translation (the bijection in the second variable) of a quasigroup q, i.e. the additional bijectivity in the first variable is unnecessary. Thus, we can regard the MQQs used in MQQ-SIG as left quasigroups without loss of generality. Even more, it can be shown (cf. proposition 1) that the MQQs used in MQQ-SIG are linearly isotopic to quasigroups that can be represented in the form given in Lemma 1, with some additional constrains on the coefficients.

Proposition 1 ([35]

). Let (F d 2 , q) be a quasigroup used in MQQ-SIG. Then q can be represented by q(x, y) = B • q(B 1 • x, B 2 • y) + c for some invertible matrices B, B 1 , B 2 , a vector c, and q = (q 1 , q 2 , . . . , q d ) with q s (x 1 , . . . , x d , y 1 , . . . , y

d ) = x s + y s + s<i,j≤d γ (s) i,j x i y j + s<i≤d δ (s) i x i + s<i≤d (s) i y i + η (s) ,
for all 1 ≤ s ≤ d and coefficients γ

(s) i,j , δ (s) i , (s)
i , η (s) ∈ F p k .

In the sequel, we will investigate the more general trapdoor of MQQ-ENC, since all the properties of MQQ-ENC apply to MQQ-SIG as well. In order to avoid redundancy and to provide a clear and simple algebraic description, we exploit the following simplification. In the central map F the authors used LMQQs constructed through Lemma 2, and not directly LMQQs from Lemma 1. This was done to mask the otherwise triangular structure of the LMQQs from Lemma 1. However, the linear isotopy, can actually be absorbed by S and T . First of all, as we are only considering quadratic coefficients later on, we can safely ignore c y and c. Further, the linear transformation D can be absorbed by T , i.e. instead of using q and the original T , we work with q and T • (I n d ⊗ D), with ⊗ the matrix tensor product of the n d dimensional identity matrix and D. The same holds for the transformation of variables S. Instead of working with q and the original transformation S, we work with (I n d ⊗ D -1 y ) • S and q(x 1 , x 2 ) := q(D -1 y x 1 , x 2 ). As there is no structure hidden in the first component of q, all the systematical zeros in q and q equal and thus we can assume a central map F with q according to Lemma 1. Writing the quadratic part of q s = x Q (s) x in its quadratic form with x = (x 1 , . . . , x d , y 1 , . . . , y d ) , we can illustrate the matrix Q (s) by Figure 1.

Q (s) = x y d d -s
Fig. 1. The quadratic form Q (s) of qs. Gray parts denote arbitrary values, whereas white parts denote systematic zeros.

• • • • • • • • • . . . . . . . . . . . . f1 f d+1 f 2d+1 f2 f d+2 f 2d+2 f d f 2d f 3d f n-d+1 f n-d+2
fn Fig. 2. Matrices of the quadratic forms of the central map F of MQQ-ENC. Gray parts denote some arbitrary values, whereas white parts denote systematical zeros.

Note that both in odd and even characteristic, the coefficient of y 2 s does not occur in Q (s) . In odd characteristic, p s (y s ) = a (s) y s , i.e. it is always linear. For characteristic 2, we have either p s (y s ) = a (s) y s or p s (y s ) = a (s) y 2 s , but nevertheless, it is again always linear, and the representation of Q (s) has systematic zeros on the main diagonal. The central polynomials f s (Definition 4), with s, 1 ≤ s ≤ m are illustrated in Figure 2. Another simplification can be made regarding the secret affine transformations S and T . First of all, we neglect linear terms, as we do not use them and they also never interfere with the coefficients of quadratic monomials. Thus we can assume S and T to be linear transformations. Note that using coefficients of linear terms could only speed up the attack, as long as they are not all chosen uniformly at random. Second, in [START_REF] Gligoroski | The Multivariate Probabilistic Encryption Scheme MQQ-ENC[END_REF] as well as in [START_REF] Gligoroski | MQQ-SIG -An Ultra-Fast and Provably CMA Resistant Digital Signature Scheme[END_REF], the authors did not choose S and T purely at random but as a combination of two circulant matrices. This structure was meant to reduce the key size and speed up the decryption process. We note that we do not use this special structure to speed up our attack. As we are recovering (I n d ⊗ D -1 y ) • S instead of S and T • (I n d ⊗ D) instead of T , for some randomly chosen D and D y , we lose most of the structure anyway. Therefore we assume to recover some random matrices in the sequel. Note that this gives a worst case complexity of our attack.

Key-Recovery Attack

In this part, we present an efficient algebraic key-recovery attack on MQQ-ENC and MQQ-SIG. To do so, we combine a MinRank attack and good keys in order to recover the columns of S and T .

High Level Description of the Attack

Remark 2. From now on for better readability, but without loss of generality, we assume the change of variables: x n-id+j → x n-id+d-j+1 . (This corresponds to moving the white bands in Fig. 1 to the lower right corner.)

Our attack is performed in n -r -1 steps, and in each Step N, N ∈ {n, . . . r + 2}, we remove the variable x N from all but the first of the public polynomials P. This is done by finding a good key (S N , T N ) of a particular form. At the end of each step, we remove the first polynomial form P, since, at this point, that is the only polynomial that contains the variable x N and repeat the procedure with the rest of the polynomials. Thus, at each Step N w.l.o.g. we can assume that the size of all public matrices is N . After n -r -1 steps, we obtain the equivalent key

S = S n • • • • • S r+2 and T = T r+2 • • • • • T n .
We can summarize the steps of our attack in Alg. 1.

Algorithm 1 High Level Description of the Key-Recovery Attack

Input: n -r public polynomials P in n variables.

for N := n down to r + 2 do Consider that all public polynomials involve ≤ N variables.

Step N : Find a good key (S N , T N ). Transform the public key as P ← T N • P • S N , and if N < n remove the first polynomial from P. end for;

Output: The equivalent key S = S n • • • • • S r+2 and T = T r+2 • • • • • T n .

Detailed Description of the Attack

We describe in this part the steps performed in Algorithm 1. We consider first the case N = n which is a bit different from the others steps.

Step n = N . How to recover a linear component of the secret-key. Let P be the n -r public polynomials in n variables of an MQQ scheme. From now on, we denote by P (1) , . . . , P (n-r) the corresponding public matrices. As explained, the public-key is constructed as P = T • F • S where F is a set of quadratic polynomials constructed as in Section 3 and S and T are two bijective linear maps used to mask the structure of P. We denote by F (1) , . . . , F (n) the quadratic forms of F. We explain how to recover one column of the secret transformation S using good keys. This corresponds to the first step performed Algorithm 1 and will allow to remove the variable x n . Recall from Subsection 2.3 that we are looking for two linear maps (Σ, Ω) ∈ GL m (F q ) × GL n (F q ) such that

P = T • Σ -1 • Σ • F • Ω • Ω -1 • S.
and F := Σ • F • Ω preserves some of the structure of F (cf. def. 2). Then T := T Σ -1 and S = Ω -1 S will be good keys. A crucial observation for MQQ-ENC is that the central polynomials f i , do not contain the monomials x n x i for any i, 1 ≤ i < n. This means that we preserve some structure even if we choose Σ = T and thus a good key T = I. In order to preserve the corresponding systematic zero coefficients, Ω is allowed to map every variable to every variable, except x n . We can then choose the good key S , or more precisely S := S -1 = SΩ, to be of the form given in Figure 3. Obviously, a good key S -according to Figure 3 -almost always exists. We can choose the first n -1 columns of Ω equal to the first n -1 columns of S. However, there is a small probability for Ω to not be invertible, in which case, a good key does not exist.

S • Ω = n -1 1 • Ω (1) 0 n -1 1 = n -1 1 = S .
Lemma 3. S nn = 0, then a good key S as given in Figure 3 does not exist.

Proof. Due to the structure of Ω in Figure 3, we have S nn Ω nn = S nn . Thus, S nn = 0 implies that S nn = 0 and S can not be invertible.

Remark 3. To guarantee that a good key as in Figure 3 exists with high probability, we can randomize the public quadratic forms P (1) , . . . , P (m) with a random invertible matrix S rand ∈ GL n (F q ). That is, we construct a new equivalent set of public polynomials P

rand := S rand P (i) S rand = (SS rand )   n j=1 t ij F (j)   SS rand . (i) rand : P (i)
Since S = 0 holds with probability 1/q, the average number of randomizations to obtain a nonzero entry at position ( , ) is q/(q -1). From now on, we will always assume that -up to randomization -good keys as in Figure 3 exist.

Using a good key T = I and S as in Figure 3, the algebraic system (3) can be rewritten as:

F (k) ij = n y=1 n z=1 P (k) yz s yi s zj .
We constructed F := Σ • F • Ω such that the monomial x n x i does not appear for any i, 1 ≤ i < n. This yields:

F (k)
n,j = 0, for all k, 1 ≤ k ≤ m, and j, 1 ≤ j < n.

Also, for all j = n, we have that s zj = 0 for z = j and s jj = 1 due to the structure of S . This yields a system of m(n -1) linear equations in (n -1) variables (since s n,n = 1), given by n y=1 P (k) yj s y,n = 0, for all k, 1 ≤ k ≤ m, and j, 1 ≤ j < n.

After solving the system, we obtain the good key S . We can then transform the public polynomials P with the change of variables S x, i.e.:

P • S = T • Σ -1 • Σ • F • Ω • Ω -1 • S • S = F .
From the previous discussion, the transformed public polynomials P • S do not contain the variable x n in any of the quadratic terms.

Remark 4. To ease the notation, we continue to denote the obtained transformed polynomials and their matrix representations as before (we regard P • S as being the public P). Since we removed the variable x n , we can consider that now the dimension of the public matrices P (i) is n -1. We explain now how to remove the variables x n-1 , x n-2 . . . down to x r+2 .

Step N ∈ {n -1, . . . , r + 2} -Using MinRank to recover the entire secret key. We assume that the dimension of all public matrices P (i) is N ∈ {n -1, . . . , r + 2}. Observe that the variable x N occurs in at most polynomial of the central map F, namely f N (cf. Figure 2). This suggests to find a linear combination of two public polynomials, w.l.o.g. p 1 and p k , with k, 1 < k ≤ m such that x N no longer occurs, so we want to find λ ∈ F q such that:

P (k) + λP (1) = S   N -1 j=1 (t kj + λt kj )F (j)   S. (6)
To recover such linear combination, we exploit the fact that the rank is invariant under a bijective linear transformation of variables, i.e. for all k, Rank(P (k) ) = Rank(S P (k) S). Thus, we can use the rank as distinguisher to recover parts of T . More precisely, we need to solve the following MinRank instance: Find λ ∈ F q such that Rank P (k) + λP (1) < N.

The good key (S N , T N ) given in Fig. 4 is a solution of [START_REF] Dubois | Practical cryptanalysis of SFLASH[END_REF]. Indeed, using the two public polynomials P (1) , P (k) and thanks to (3), we obtain the following system of N -1 quadratic equations in N -1 variables:

F (k) ij = N y=1 N z=1 P (k) yz + λP (1) yz s yi s zj .
By construction, F

N,j = 0 for all j, 1 ≤ j < N . Also, for all j < N and z = j we have that s zj = 0 and s jj = 1. This gives

N y = 1 P (k) yj + λP (1)
yj s y,N = 0, for all j, 1 ≤ j < n.

Applying the same reasoning for all of the public matrices P (k) , 1 < k ≤ N -r + 1 we obtain the good key (S N , T N ). The correctness of the procedure follows from the next theorem. Theorem 3. Let N be the number of variables in the N -r + 1 public polynomials of MQQ-ENC (or MQQ-SIG) during step N ∈ {n -1, . . . , r + 2}. Let s = (s 1,N , s 2,N , . . . , s N -1,N , 1) and t = (1, t 2,1 , t 3,1 , . . . , t N -r+1,1 ) be unknown vectors. Thus, it holds that (s 0 , t 0 ) is a solution of:

S N = N -1 1 , T N = N -r-1 1 .
s P (k) + t k1 P (1) = 0 1×N , ∀k, 1 < k ≤ N -r + 1 (9)
if and only if (S N , T N ) is a good key for MQQ-ENC (respectively MQQ-SIG), where S N is obtained from the identity matrix I N by replacing the last column with s 0 , and T N is obtained from the identity matrix I N by replacing the first column with t 0 .

Proof. From (2), we have that:

F (k) = S N P (k) + t k1 P (1) S N , ∀k, 1 < k ≤ N -r + 1
, or equivalently :

F (k) ij = N y=1 N z=1 P (k) yz + t k1 P (1) yz s yi s zj , ∀1 < k ≤ N -r + 1.
Thus, if (S N , T N ) is a good key then

F (k) iN = 0 (or equivalently F (k)
N i = 0) for every 1 ≤ i < N . By construction, for every 1 ≤ i < N , s yi = 0, for all y = i, and s ii = 1. Hence, (S N , T N ) is a good key if and only if for every i, k s.t. i < N and 1 < k ≤ N -r + 1 it holds that:

N z=1 P (k) iz + t k1 P
(1) iz s z,N = 0. The last system is equivalent to [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF], so the claim follows.

Remark 5. Note that Theorem 3 can be applied to Step n as well. In this case it is known that t k1 = 0, so instead of a system of quadratic equations we obtain a system of linear equations as explained in the the previous part. So, step n = N is actually just an easier sub-case of the others steps.

Modeling Good Keys as MinRank for Rectangular Matrices

Theorem 3 shows that the problem of finding a good key is equivalent to finding the intersection of the kernels of some linear combinations of the public matrices. This can be nicely modeled as a special instance of the MinRank problem for rectangular matrices.

Corollary 1. Let N , s and t be as in Thm. 3. Let P = [P (2) |P (3) | . . . |P (N -r+1) ] N ×N (N -r) and P i = [0| . . . |0|P (1) |0| . . . |0] N ×N (N -r) be block matrices, where P (1) is the i-th block in P i . It holds that finding a good key (S N , T N ) of the form given in Thm. 3 for MQQ-ENC (or MQQ-SIG) is equivalent to solving the MinRank instance defined below:

Find t 2,1 , . . . , t N -r+1,1 ∈ F q such that Rank P + N -r+1 k=2 t k1 P k < N. (10)
Proof. Using the Kipnis-Shamir modeling, the MinRank instance (10) can be expressed exactly as the system of equations ( 9). The claim follows from Thm. 3.

We now summarize our key-recovery attack in Algorithm 2 for MQQ-ENC and MQQ-SIG based on the results from Theorem 3, Remark 5 and Corollary 1.

Complexity of the Key-Recovery Attack

In this part, we show that the complexity of our attack is polynomial. To so do, we present a complexity analysis of the Algo. 2. We also present experimental results which confirm our theoretical results.

To analyse the complexity of this simple approach, we introduce: Definition 5. Let F q be a field of characteristic 2 and (A, B) ∈ F N q × F N q be a pencil [START_REF] Gantmacher | The Theory of Matrices[END_REF] of skewsymmetric matrices. We shall say that the pencil is generic if for all λ 0 ∈ F q , Ker (A + λ 0 B) is of dimension ≥ 2 if N is even and ≥ 1 otherwise.

If N is odd, a generic pencil (A, B) means that the pencil is always of maximal possible rank. If N is even, the pencil is generic if the rank defect, if any, is minimal, just one. Remark 7. For the parameter sets of the MQQ cryptosystems, we can assume with high probability that the pencils from the public matrices are generic. Indeed, let λ(q, n) = n i=1 1 -1/q i . be the probability that a n × n matrix over F q is invertible. It is known from [START_REF] Macwilliams | Orthogonal matrices over finite fields. Orthogonal matrices over finite fields[END_REF] (and recalled in [38, Section 10]) that the probability that a skew-symmetric matrix is of maximal rank (n -1) when n is odd is Pr odd = λ(q,n) λ(q 2 ,(n-1)/2) 1 1-1/q and the probability that it is of rank ≥ n -2 when n is even is: Pr even = λ(q,n) λ(q 2 ,(n-1)/2) 1 + q n -1 q n-2 (q 2 -1)(q-1) . Having this in mind, we get that the probability that the pencils in question are generic is Pr q odd or Pr q even , depending on the parity of n. In either case, for the parameter sets of MQQ-ENC and MQQ-SIG (as in Section 7.2), it can be checked that the a probability is bigger than 0.7.

We first assume that the field q is not to big, typically q = O(n). This is indeed the case for most of the parameters proposed so far for MQQ cryptosystems. Theorem 4. Let N ∈ {n -1, . . . , r + 2} and let F q be a field of characteristic 2 such that q = O(n). Let P (1) , . . . , P (N -r+1) ∈ F N ×N q be the skew-symmetric matrices occurring in Algorithm 2 at step Rectangular MinRank(N ). If there exists i 0 , 2 ≤ i 0 ≤ (N -r + 1) such that the pencil (P (1) , P (i 0 ) ) is generic, then, the system (9) of Theorem 3 can be solved with probability 1 -1/q in O(n ω+2 ) operations, where 2 ≤ ω < 3 is the linear algebra constant. In total, and under the assumptions, there exists an algorithm which recovers a key equivalent to the secret-key in O n ω+3 with probability 1 -1/q. The proof can be found in Appendix B. Theorem 4 can be extended even if we assume that there exists a pencil of matrices for which the rank defect is small, that is a constant. More generally, for arbitrary q and N , we show that we can get a complexity which is independent of the field size and polynomial in the number of variables. More precisely, the following result holds (proof in Appendix B). Theorem 5. Let F q be an arbitrary field of characteristic 2 and let N ∈ {n -1, . . . , r + 2}. We assume that the system (9) of Theorem 3 is not harder to solve than a generic affine bi-linear system (Theorem 7). Let the matrices P (1) , . . . , P (N -r+1) ∈ F N ×N q be as in Algorithm 2. If there exist i 0 , i 1 ∈ {2, . . . , (N -r + 1)} such that the pencils (P (1) , P (i 0 ) ), and (P (1) , P (i 1 ) ) are generic, and if we assume that the corresponding kernels behave like random, then, for all N ∈ {n -1, . . . , r + 2}, the system (9) of Theorem 3 can be solved in O(N 3 ω ), with 2 ≤ ω < 3 the linear algebra constant.

In total, and under the assumptions, there exists an algorithm which recovers a key equivalent to the secret-key in O(n 3 ω+1 ) field operations with probability 1 -1 q 1 -1 q n-3 .

Experimental Results

For the parameter sets proposed for MQQ-ENC [START_REF] Gligoroski | The Multivariate Probabilistic Encryption Scheme MQQ-ENC[END_REF] and MQQ-SIG [START_REF] Gligoroski | MQQ-SIG -An Ultra-Fast and Provably CMA Resistant Digital Signature Scheme[END_REF] the results from Theorem 5 lead to the complexities given in Table 1 and Table 2. They have been calculated using the more precise formula C(n, r, q) = n- 3 and Table 4. From the tables, we can see that all our experiments, for both MQQ-ENC, and MQQ-SIG, confirmed that the maximum degree reached during the Gröbner basis computation (d max ) of the system ( 9) is 3, consistent with Theorem 4. Furthermore, the results are almost a perfect match with the theoretical calculations of Theorem 5.

Conclusion

Mounting a successful key recovery attack against MQQ-ENC and MQQ-SIG using good keys, we have yet again shown that MinRank is a fundamental problem in MQ cryptography. We have however also shown that it is necessary to take into account the parity of the characteristic of the field when using MinRank to reveal the good key. Because of the different representation of quadratic polynomials over fields of characteristic 2, the attack, otherwise valid over odd characteristic fields, can not be directly applied. Interestingly, this has often been overlooked in the literature. By unveiling the pitfalls in the attack of the MQQ schemes arising from the even characteristic of the field, our analysis shows that the same modification is necessary when attacking similar MQ schemes over fields of characteristic 2 using MinRank.

Fig. 3 .

 3 Fig. 3. Unique transformation Ω to obtain the good key S .

Fig. 4 .

 4 Fig. 4. The good key (S N , T N ).

Table 1 .

 1 Theoretical complexities, in terms of field operations, of the key recovery attack on MQQ-ENC compared to the original decryption algorithm. All of the parameters are for claimed security of O(2 128 ).

			1 N =r+2	N +4 3	ω .
	2 k k n r d Decryption Key Recovery
	2 1 256 8 8	2 25	2 56.3
	4 2 128 4 8	2 23	2 48.2
	16 4 64 2 8	2 21	2 40.3
	256 8 32 1 8	2 20	2 32.5

Table 2 .

 2 Theoretical complexities, in terms of field operations, of the key recovery attack on MQQ-SIG compared to the claimed security level.We have implemented the attack in Magma (Version 2.19-10 [29]) on a workstation with 32 cores based on Intel Xeon 2.27GHz, with 1TB of RAM memory. The results of the practical attack are summarized in Table

	Security Level n d Key Recovery
	2 80	160 8	2 50.8
	2 96	192 8	2 52.9
	2 112	224 8	2 54.7
	2 128	256 8	2 56.2

Table 3 .

 3 Results of the practical attack on MQQ-ENC.

	2 k k n r d	Key Recovery	Key Recovery Practical
		Theoretical cycles	sec	dmax
	2 1 64 8 8	2 40.3	2 43.4	5421	3
	2 1 96 8 8	2 44.9	2 47.8	111844	3
	4 2 64 4 8	2 40.3	2 43.7	6978	3
	4 2 96 4 8	2 44.9	2 47.8	109258	3
	4 2 128 4 8	2 48.2	2 50.6	787214	3
	16 4 32 2 8	2 32.5	2 34.7	14	3
	16 4 48 2 8	2 37.0	2 38.9	251	3
	16 4 64 2 8	2 40.3	2 41.6	1783	3

Table 4 .

 4 Results of the practical attack on MQQ-SIG.

	n r d	Key Recovery	Key Recovery Practical
		Theoretical cycles	sec	dmax
	64 32 8	2 40.3	2 40.1	560	3
	96 48 8	2 44.9	2 43.2	4822	3
	128 64 8	2 48.2	2 46.0	34376	3
	160 80 8	2 50.8	2 48.0	120882	3

Note that S and T can actually be chosen to be affine. We restrict ourselves to linear secrets for the sake of simplicity. However, we mention that the attack can be simply adapted to work in the affine case (see[START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF][START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF]).

ω ), we obtain the total complexity of the attack.

Algorithm 2 Key Recovery

Input: n -r public polynomials P in n variables.

for N := n down to r + 2 do Consider the dimension of all public matrices P (i) to be N . If N = n, set b = 0, otherwise set b = 1.

Step Rectangular MinRank (N ): Let s = (s 1,N , s 2,N , . . . , s N -1,N , 1) and t = (t 2,1 , t 3,1 , . . . , t N -r+b,1 ) be unknown vectors. Find a good key (S N , T N ) by solving the system (9) in (s , t ):

, where if b = 0, then t = (0, 0, . . . , 0); for P = [P (2) |P (3) | . . . |P (N -r+1) ] 1×N (N -r) and Pi = [0| . . . |0|P (1) |0| . . . |0] 1×N (N -r) with P (1) being the i-th block in Pi. Transform the public key: P ← T N • P • S N , If b = 1 remove the first polynomial from P (P now contains N -r polynomials). end for;

Theoretical Complexity

The goal of this part is to bound the complexity of solving the algebraic equations ( 9) arising at each step of Alg. 2. As we will see from the experimental results (Section 7.2), it appears that the system (9) can be solved efficiently in practice. In particular, the maximum degree reached during the Gröbner basis computation is bounded by a small constant, 3. We will now theoretically explain this fact. A strategy for bounding the complexity of solving ( 9) is to consider a subset of the equations. In particular, the equations of (9) derived from a given k, 1 < k ≤ N -r + 1 correspond to a Kipnis-Shamir modeling of the MinRank problem [START_REF] Dubois | Practical cryptanalysis of SFLASH[END_REF]. To give intuition, we consider a pair of matrices P (1) , P (k) such that P (1) is invertible. Setting P * = P (k) P (1) -1 , we obtain that (7) is equivalent to:

Find λ ∈ F q such that Det(P * -λI N ) = 0.

We can compute the roots of the characteristic polynomial, which are the eigenvalues of P * -λI N , and the corresponding eigenvectors. All such pairs will vanish the k-th equation of [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]. We can then substitute each possible possible eigenvector in the others equations and solve the linear system involving the remaining unknowns. We have found a part of the secret-key as soon as the linear system is consistent. However, the complexity of this approach will depend on the multiplicity of the eigenvalues. If all the roots of (11) are simple, then the approach described, allows to solve the system (9) in polynomial-time.

Remark 6. In characteristic 2, the previous discussion does not directly apply since the matrix representation of a public polynomial has always an even rank (cf. Remark 1). In particular, the situation is as follows:

-When N is even, the rank of the skew-symmetric matrices P (1) and P (k) is ≤ N . A drop of the rank will likely yield Rank P (k) + λP (1) = N -2. In this case, we can expect that the MinRank problem has unique solution λ. For this λ, the dimension of Ker P (k) + λP (1) is 2 (in this case, [START_REF]ETSI: ETSI 2nd Quantum-Safe Crypto Workshop in partnership with the IQC[END_REF] would have a root of multiplicity > 1). Since s N,N = 1 in (8), we obtain q solutions for the good key S N . -For odd N , the rank of the matrices P (1) and P (k) is ≤ N -1, which means that ( 7) is satisfied for any λ. In this case, since s N,N = 1, for each λ ∈ F q we get a unique solution for the good key S N if the rank defect is minimum, just one.

A The MinRank problem

The MinRank problem over a finite field F q is defined as follows.

MinRank (MR)

Input: n, m, r, k ∈ N, where n < m and M 0 , M 1 , . . . , M k ∈ M n×m (F q ). Question:

Kipnis and Shamir [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] proposed to model the MinRank problem as a multivariate polynomial system of equations. The basic idea of the modeling is that the matrix k i=1 λ i M i -M 0 has rank ≤ r if and only if there exists a set of n -r independent vectors in its left kernel. Writing this set as a matrix in echelon form, yields a system of n (n -r) equations in r (n -r) + k variables given in matrix form:

Note that, over a finite field, the set of unknown independent vectors can be written in such a systematic form with high probability. Initially, relinearization [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF] was 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].

We recall the complexity of the F 5 algorithm for computing a grevlex Gröbner basis of a polynomial system 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 semi-regular polynomial systems[END_REF].

Theorem 6. 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

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. 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.

From Theorem 6, we can see that in order to estimate the complexity of finding the MinRank solution with this modeling, we need a good estimate of the degree of regularity of the system [START_REF] Courtois | Cryptanalysis of the TTM cryptosystem[END_REF]. Using the fact that ( 12) is an affine bilinear system, the following tight bound can be appropriately used for the purpose.

Theorem 7 ([28]

). Let X and Y be two blocks of variables of sizes n X and n Y respectively. We shall say

For the grevlex ordering, the degree of regularity of a generic affine bilinear zero-dimensional system over K[X, Y ] is upper bounded by

In particular, this result implies that computing the Gröbner basis of generic affine bilinear zerodimensional system with min(n X , n Y ) ∈ O(1) can be done in polynomial-time.

B Complexity Theorems Proofs

B.1 Proof of Theorem 4.

Proof. Without loss of generality, we can assume that i 0 = 2 (up to re-ordering the equations). Let λ 2 be a root of the degree-N univariate polynomial Det P (2) + X • P (1) . We denote by K 2 = Ker P (2) + λ 2 P (1) the corresponding kernel. We first assume that N is odd. By the genericity assumption, we know that K 2 is of dimension one. Since s N,N = 1 in (8), each K 2 yields an unique s 2 (stated differently, s 2 is the vector generating K 2 in a systematic basis). There is at most q = O(n) distinct values for s 2 . We then plug each s 2 in (9) which reduces then to a system of linear equation in the t . We know that there is at least one s 2 which leads to a consistent system. If N < n is odd, we can then solve [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] in O(n ω+1 ).

When N is even, the situation is very similar. The only difference is that K 2 is of dimension 2. Since s N,N = 1 in (8), each K 2 yields q = O(n) distinct s 2 . There is at most N < n distinct values for s 2 .

As before, we plug each possible s 2 in (9) which yields a system of linear equation in the t . Thus, if N is even, we can then solve [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] in O(n ω+2 ). Note that because of Lemma 3, the system will give a solution with probability q-1 q , so we need to randomize the public polynomials on average q q-1 times. The whole procedure needs to be repeated for every N starting from n -1 down to r + 2. Note that in the first iteration, when N = n, we actually solve only a linear system of equations.

B.2 Proof of Theorem 5.

Proof. Denote by n k q = (q n -1)(q n -q)...(q n -q k-1 ) (q k -1)(q k -q)...(q k -q k-1 ) the Gaussian binomial coefficient, that gives the number of k-dimensional subspaces of an n-dimensional vector space. The main idea of the proof is to show that in [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] it is enough to consider only two coordinates of t in order to get a unique solution for s with overwhelming probability. Namely, it is enough to consider only the equations corresponding to i 0 = 2, i 1 = 3 (w.l.o.g. up to reordering of equations):

s P (3) + t 31 P (1) = 0 1×N .

For odd N , for both i ∈ {2, 3} we have that Dim(Ker(P (i) + λP (1) )) = 1 for every λ ∈ F q . Denote the set {Ker(P (2) + λP (1) )|λ ∈ F q } by R 2 , and the set {Ker(P (3) + λP (1) )|λ ∈ F q } by R 3 . We know that, if there exists a good key, it will be a vector in the vector space that is the intersection R 2 ∩ R 3 . The probability that the intersection contains another vector space by chance is

, which is very small for big enough N . Similarly, for even N , there exist λ 2 , λ 3 such that for both i ∈ {2, 3}, Dim(Ker(P (i) + λ i P (1) )) = 2. Now, if a good key exists, it will be in the intersection of the kernels and all other elements in the intersection will be linearly dependent of the good key. Hence, in this case the probability that we get a solution of the system that is not a good key is the same as the probability that the two kernels coincide, which equals 1/ N 2 q ≈ q (4-2N ) . This again is very small. Thus, in total, with probability of 1 -1 q N -3 it is enough to use only the Equations ( 13) and ( 14). The task now reduces to solving a bilinear system of bidegree (1, 1), over F q [t i 0 ,1 , t i 1 ,1 , s 1,N , . . . , s N -1,N ]. From Theorem 7, such system can be solved in O N +4 3 ω .

Again because of Lemma 3, we need to randomize the public polynomials on average q q-1 times. The step of solving the system (9) needs to be repeated for every N starting from n -1 down to r + 2. Note that, when N = n, we actually solve only a linear system of equations, which is of smaller complexity. In total, asymptotically, since we have O(n) steps of complexity O( n+4