The XL-Algorithm and a Conjecture from Commutative Algebra

Claus Diem

Institute for Experimental Mathematics, University of Duisburg-Essen Essen, Germany

Abstract. The “XL-algorithm” is a computational method to solve overdetermined systems of polynomial equations which is based on a generalization of the well-known method of linearization; it was introduced to cryptology at Eurocrypt 2000. In this paper, we prove upper bounds on the dimensions of the spaces of equations in the XL-algorithm. These upper bounds provide strong evidence that for any fixed finite field K and any fixed c ∈ ℕ the median of the running times of the original XL-algorithm applied to systems of m = n+c quadratic equations in n variables over K which have a solution in K is not subexponential in n. In contrast to this, in the introduction of the original paper on XL, the authors claimed to “provide strong theoretical and practical evidence that the expected running time of this technique is […] subexponential if m exceeds n by a small number”. More precise upper bounds on the dimensions of the spaces of equations in the XL-algorithm can be obtained if one assumes a standard conjecture from commutative algebra. We state the conjecture and discuss implications on the XL-algorithm.

Keywords. Cryptanalysis, algebraic attacks, overdetermined systems of polynomial equations, extended linearization, Fröberg’s Conjecture

1 Motivation and introduction

The security of many cryptographic systems would be jeopardized if one could solve certain types of systems of polynomial equations over finite fields. For example, it has been pointed out in [8] that one can with a high probability recover an AES-128 key from one AES-128 plaintext-ciphertext pair if one can solve certain systems with 1600 variables and 8000 quadratic equations over 𝔽_{2}, and it has been pointed out in [14] that one can achieve the same goal if one can solve certain systems with 3986 variables and 3840 (sparse) quadratic equations as well as 1408 linear equations over 𝔽_{2^{8}}.

Of particular importance for cryptological applications are so-called overdetermined (or overdefined) systems of quadratic equations as for example the ones we just mentioned. Let us consider a system of quadratic polynomial equations

f_{1}(X_{1}, …, X_{n}) = 0 , …, f_{m}(X_{1}, …, X_{n}) = 0 ,  (1)

where the f_{j} are polynomials in n indeterminates X_{1}, …, X_{n} over an “effective” field K (the field being finite in the cryptological applications). We say that the system is overdetermined if the dimension of the K-vector space generated by the f_{j} is greater than n.

In [7], Courtois, Klimov, Patarin and Shamir propose a computational method called eXtended Linearization (XL) or XL-algorithm to solve such systems of polynomial equations (see the next section for a description of the method). In the same paper certain heuristics on the running time of this method are stated. These heuristics have subsequently been criticized by Moh ([13]) as being too optimistic, and in Sect. 4 of [13], the method is analyzed with heuristic upper bounds on the dimensions on the spaces of equations in the XL-algorithm. As however the assumptions on which the heuristic in [13, Sect. 4] relies are not very precisely stated, the question whether this heuristic or the original heuristic is more credible remained an open problem among cryptologists. In a recent work by Chen and Yang ([4]), the heuristic of [13, Sect. 4] is stated as a special case of a theorem ([4, Theorem 2]).^{1} However, the proof of [4, Theorem 2] (and of [4, Theorem 7]) has some serious flaws.

The main purpose of this paper is to show that under the assumption of a widely believed conjecture of commutative algebra, one can indeed derive the non-trivial upper bounds on the dimensions of the spaces of equations in the XL-algorithm conjectured by Moh and stated in [4, Corollary 6, 1] (see Theorem 1 in Sect. 5 for a more general statement). Moreover, we state upper bounds on the dimensions of the spaces of equations in the original XL-algorithm which can be proven without the assumption of this conjecture. These upper bounds provide strong evidence that for any fixed finite field K and any fixed c ∈ ℕ the median of the running times of the original XL-algorithm applied to systems of m = n + c quadratic equations in n variables over K which have a solution in K is not subexponential in n (see the next section for details).

2 The XL-algorithm and our analysis

Let us fix the system of quadratic equations (1) which we assume to have a solution in K and some D ∈ ℕ. The main idea of the XL-algorithm is to try to solve (1) by linearization of the system of all polynomial equations

∏_{ℓ=1}^{k} X_{i_{ℓ}} · f_{j}(X_{1}, …, X_{n}) = 0 ,  (2)

where k ≤ D − 2.

Let U_{D} be K-vector space generated by the polynomials ∏_{ℓ=1}^{k} X_{i_{ℓ}} · f_{j} with k ≤ D − 2.

According to [7, Definition 1], the XL-algorithm is as follows. (Except for changes in the notation, the description is verbatim.)

1 Theorem 2 of [4] is equivalent to the heuristics of [13] if D < q as can be seen by expanding the polynomial in item 1 of Corollary 6 in [4].

The XL-algorithm. Execute the following steps:

1. Multiply: Generate all the products ∏_{ℓ=1}^{k} X_{i_{ℓ}} · f_{j} ∈ U_{D} with k ≤ D − 2.

2. Linearize: Consider each monomial in X_{i} of degree ≤ D as an independent variable^{2} and perform Gaussian elimination on the equation obtained in 1. The ordering on the monomials must be such that all the terms containing one [specific] variable (say X_{1}) are eliminated last.

3. Solve: Assume that step 2 yields at least one univariate equation in the powers of X_{1}. Solve this equation over the finite fields (e.g. with Berlekamp’s algorithm).^{3}^{,}^{4}

4. Repeat: Simplify the equations and repeat the process to find the values of the other variables.

Remark 1. In the description of the method in [7], it seems that D is fixed beforehand. As the authors do however not say how D should be determined, it seems to be reasonable to assume that the authors of [7] had in mind that D is in fact a variable which is small (e.g. 2) in the beginning, and that the the XL-algorithm goes to Step 1 with an incremented D whenever in Step 3 no univariate equation in X_{1} with a solution in K is found.

Remark 2. In an “extended version” ([6]) of [7], the description of the method is the same as the one in [7] (and the one we present here) except that the authors have inserted the sentence “In all the following notations we suppose the powers of variables taken over K, i.e. reduced modulo q to the range 1, …, q −1 because of the equation a^{q} = a of the finite field K.” after the third paragraph of Sect.

3. (But the field is not assumed to be finite in the second paragraph of Sect. 3 and the number q is not mentioned before.) Apart from this insertion, there is no substantial difference between Sect. 3 to 7 of [7] and of [6]. Of course, if one identifies the monomials ∏_{ℓ=1}^{k} X_{i_{ℓ}} and X^{q} · ∏_{ℓ=1}^{k} X_{i_{ℓ}} the method becomes much faster if q, the field size, is small, q = 2, 3, 4, 5 say. According to the way the heuristics in Sect. 6 of [7] and [6] were conducted, this identification was however not made in the heuristic analysis of [7] and [6].

Definition 1. We call the above computational method the original XL-algo-rithm. The variant introduced in [6] is called reduced XL-algorithm.

Remark 3. Whereas the original XL-algorithm should only be applied to overdetermined systems of (quadratic) polynomial equations, if the field is finite and not too large, it makes sense to apply the reduced XL-algorithm to any system of (quadratic) polynomial equations.

2 The authors of [7] obviously mean that each monomial of degree ≤ D should be

considered as a new variable. 3 Note however that according to the second paragraph in [7, Sect. 3], the ground field

is not necessarily finite. 4 It should be avoided to repeatedly select univariate polynomial equations which

have more than one solution in K. Moreover, if a univariate polynomial equation is found which does not have a solution in K, the method should terminate and output “unsolvable”.

Remark 4. Neither of the two computational methods terminates for every input (even if they are only applied to overdetermined systems which have a solution in K); thus in contrast to their names, they are not algorithms (not even randomized algorithms) in the usual sense (cf. [11, Chapter 1, 1.1]).

As we will see in the next section, there is a strong connection between the original and the reduced XL-algorithm (see Proposition 1). Because of this connection, one can use an analysis of (a generalization of) the original XL-algorithm to analyze also the reduced XL-algorithm (see Theorem 1 and Corollary 1). In order to state the main ideas of our analysis and to compare our results with the conjectures of [7], in this section, we concentrate on the original XL-algorithm.

For D ∈ ℕ, let K[X_{1}, …, X_{n}]_{≤D} be the K-vector space of polynomials in X_{1}, …, X_{n} of (total) degree ≤ D, and let

χ(D) := dim_{K}(K[X_{1}, …, X_{n}]_{≤D}) − dim_{K}(U_{D}) .  (3)

One can surely obtain a non-trivial univariate polynomial by (Gaussian) elimination on (2) if χ(D) ≤ D. (This is because the K-vector space K[X_{1}]_{≤D} has dimension D + 1, thus if χ(D) ≤ D, then dim_{K}(U_{D}) + dim_{K}(K[X_{1}]_{≤D}) > dim_{K}(K[X_{1}, …, X_{n}]_{≤D}), and this implies that U_{D} ∩ K[X_{1}]_{≤D} ≠ {0}.) In order to analyze the running time of the XL-algorithm, it is of greatest importance to study the question for which D one can expect this condition to hold (if such a D exists at all). We thus define D_{min} be the minimal D with χ(D) ≤ D (if no such D exists, we set D_{min} = ∞).

The starting point for our analysis of the XL-algorithm is the interpretation of the original XL-algorithm via the theory of homogeneous polynomial ideals pointed out by Moh ([13]). This interpretation opens the door for the usage of well-established methods from commutative algebra – the keywords are Hilbert Theory, Hilbert functions, Hilbert series and Hilbert polynomials.

A crucial observation is that in order to derive lower bounds on χ(D) (i.e. upper bounds on dim_{K}(U_{D})) it suffices to study the dimensions of the homogeneous parts of algebras defined by generic systems of homogeneous polynomials. (This notion will be made precise in Sect. 4.) For m ≤ n + 1, these dimensions are known, and this information suffices to prove that for m = n + c, c ≥ 1,

D_{min} ≥ \frac{n}{\sqrt{c − 1} + 1}  (4)

(see Proposition 6.) In contrast to this inequality, it was suggested in [7, Sect. 6.4] that “even for small values of c”, c ≥ 2, one has

D_{min} ≈ \sqrt{n} .  (5)

Let us fix the field K and c ≥ 2 and study the asymptotic behavior of the running time of the original XL-algorithm for n ⟶ ∞ (and m = n + c): If (5) was true, the XL-algorithm in [7] would have a running time (in field operations) which is subexponential in n. (This hope was expressed at the end of Sect. 6.1 of [7] as well as at the end of the introduction of [7].) However by (4), the running time of all instances for which U_{D} ∩ K[X_{1}]_{≤D} = {0} for all D < D_{min} is not subexponential in n.

If K is a finite field and #K and n are not “too small” it seems very reasonable to expect: Under all systems (1) which have a solution in K, the portion of systems for which U_{D} ∩ K[X_{1}]_{≤D} ≠ {0} for some D < D_{min} is negligible. This suggests that for any fixed c ≥ 1 the median of the running times of the original XL-algorithm applied to systems of m = n+c quadratic equations in n variables over K which have a solution in K is not subexponential in n. The hope stated at the end of Sect. 1 of [7] that “the expected running time of this technique is ... subexponential if m exceeds n by a small number” should be abandoned.

For c ≥ 3, much more precise lower bounds on D_{min} then the ones in (4) can be obtained if one assumes a certain conjecture which implies what the dimensions of homogeneous parts of algebras defined by generic systems of homogeneous polynomials should be (see Sect. 5). This conjecture – which is now approximately 20 years old – states that certain linear maps are either injective or surjective, that is, they have maximal rank. Because of this, we speak of the maximal rank conjecture (MR-conjecture).

3 A generalization of the original and the reduced XL-algorithm

The original as well as the reduced XL-algorithm of can easily be generalized to more general than quadratic systems of polynomial equations (see also [5, Sect. 2]).

For these generalizations, we start off with a system of m polynomial equations

f_{1}(X_{1}, …, X_{n}) = 0, …, f_{m}(X_{1}, …, X_{n}) = 0 .  (6)

The generalization of the original XL-algorithm works just as the original XLalgorithm stated in the previous section with the difference that for some D ∈ ℕ, one applies Gaussian elimination to the linearized system of all polynomial equations

∏_{ℓ=1}^{k} X_{i_{ℓ}} · f_{j}(X_{1}, …, X_{n}) = 0 ,  (7)

where k + deg(f_{j}) ≤ D.

Clearly, the reduced XL-algorithm can be generalized in a similar manner. From now on, we refer to these generalizations also as the “original” and the “reduced” XL-algorithm.

Let us fix the following notations.

– As in the previous section, let

U_{D} := ⟨ ∏_{ℓ=1}^{k} X_{i_{ℓ}} · f_{j}(X_{1}, …, X_{n}) with k ≤ D − deg(f_{j})⟩_{K}  (8)

– and

χ(D) := dim_{K}(K[X_{1}, …, X_{n}]_{≤D}) − dim_{K}(U_{D}) .  (9)

Let K = 𝔽_{q}.

– If f ∈ K[X_{1}, …, X_{n}]_{≤D}, we denote by f^{red} the “reduction” of f, i.e. f^{red} is the polynomial obtained by maximally reducing all exponents in the monomials according to the relations ∏_{ℓ=1}^{k} X_{i_{ℓ}} − X_{i}^{q} · ∏_{ℓ=1}^{k} X_{i_{ℓ}} = 0. Note that (…)^{red} is a homomorphism of K-vector spaces and that (U_{D})^{red} ≤ (K[X_{1}, …, X_{n}]_{≤D})^{red} is the space of equations generated in the reduced XL-algorithm.

– In order to analyze the reduced XL-algorithm, we set

χ^{red}(D) := dim_{K}((K[X_{1}, …, X_{n}]_{≤D})^{red}) − dim_{K}((U_{D})^{red}) .  (10)

– Let Ũ_{D} be defined just as U_{D} with respect to the system of m+n polynomials f_{1}, …, f_{m}, X_{1}^{q} − X_{1}, …, X_{n}^{q} − X_{n}, and let χ̃(D) be defined as χ(D) with respect to Ũ_{D}.

The proof of the following proposition can be found in Appendix A.

Proposition 1. We have χ^{red}(D) = χ̃(D).

Because of this proposition, the results on the original XL-algorithm can easily be carried over to the reduced XL-algorithm. What remains is to derive nontrivial lower bounds on χ(D).

4 The XL-algorithm and Hilbert Theory

In the following discussion, we assume that the reader is familiar with basic notions of commutative algebra as can for example be found in the first three chapters of [1].

As mentioned in Sect. 2, our analysis of the XL-algorithm relies on an interpretation via homogeneous polynomial ideals. The main idea is to consider (for some field K, some n ∈ ℕ and some D ∈ ℕ) the homogeneous polynomials of degree D in n + 1 variables instead of the polynomials of degree ≤ D in n variables.

Let K be an arbitrary field, n ∈ ℕ, and let f_{1}, …, f_{n} ∈ K[X_{1}, …, X_{n}]. We use the notations of the previous sections, and additionally we denote by K[X_{0}, …, X_{n}]_{D} the K-vector space of all homogeneous polynomials of degree D. More generally, for any positively graded K[X_{0}, …, X_{n}]-module M, we denote the homogeneous part of degree D of M by M_{D}.

Let F_{j} ∈ K[X_{0}, …, X_{n}] be the homogenization of f_{j}, that is, F_{j} is the unique homogeneous polynomial in K[X_{0}, …, X_{n}] of the same degree as f_{j} with F_{j}(1, X_{1}, …, X_{n}) = f_{j}(X_{1}, …, X_{n}).

Let

Φ : K[X_{1}, …, X_{n}]_{≤D} ⟶ K[X_{0}, …, X_{n}]_{D}

be the “degree D homogenization map”, that is, the K-linear map given by

∏_{ℓ=1}^{k} X_{i_{ℓ}} ↦ X_{0}^{D−k} ∏_{ℓ=1}^{k} X_{i_{ℓ}} .

Then under the isomorphism Φ, the K-vector space U_{D} corresponds to

⟨ ∏_{ℓ=1}^{k} X_{i_{ℓ}} · F_{j}(X_{0}, X_{1}, …, X_{n}) with k = D − deg(F_{j})⟩_{K} ,

where the products are taken over the variables X_{0}, …, X_{n}. This space is nothing but the D^{th} homogeneous component of the homogeneous ideal

I := (F_{1}, …, F_{m}) ⊲ K[X_{0}, …, X_{n}] ,

denoted I_{D}. We have

χ(D) =^{Def} dim_{K}(K[X_{1}, …, X_{n}]_{≤D}) − dim_{K}(U_{D})
= dim_{K}(K[X_{0}, …, X_{n}]_{D}) − dim_{K}(I_{D})
= dim_{K}(K[X_{0}, …, X_{n}]_{D}/I_{D})
= dim_{K}((K[X_{0}, …, X_{n}]/I)_{D}) .

(11)

Let R := K[X_{0}, …, X_{n}]. Recall the following definitions (see e.g. [16, Sect. 1]).

Definition 2. Let M = ⨁_{i∈ℕ_{0}} M_{i} be any finitely generated positively graded R-module. Then the function

χ_{M} : ℕ_{0} ⟶ ℕ_{0}, χ_{M}(i) := dim_{K}(M_{i})

is called the Hilbert function of M.

The power series with integer coefficients

H_{M} := ∑_{i∈ℕ_{0}} χ_{M}(i)T^{i}

is called the Hilbert series of M.

Note that the above equation (11) states that

χ(D) = χ_{R/I}(D) for all D ∈ ℕ .  (12)

Let us denote by X\underline{i} the monomial corresponding to the multiindex \underline{i} ∈ ℕ_{0}^{{0,...,n}}. The following definition can be found in [10].

Definition 3. A form (i.e. a homogeneous polynomial) G = ∑\underline{i} a\underline{i}X\underline{i} ∈ R of degree d is generic if all monomials of degree d in R have coefficients a\underline{i} in G, and these coefficients are algebraically independent over the prime field of K.

A generic system of forms is a system of generic forms G_{j} = ∑\underline{i} a(j) ; \underline{i}X\underline{i} as

above (not necessarily of the same degree) such that all a(j) ; \underline{i} are algebraically independent over the prime field of K. An ideal I generated by a generic system of forms is called generic, and so is the R-algebra R/I.

Lemma and Definition 4. The Hilbert series of an ideal generated by a generic system G_{1}, …, G_{m} of forms of degrees d_{1}, …, d_{m} depends only on the characteristic of the field, the number n and the tuple of numbers (d_{1}, …, d_{m}). If the characteristic of the field is 0, we speak of the generic Hilbert series of type (n + 1; m; d_{1}, …, d_{m}).

Proof. Let K and L be two fields over the same prime field F, and let G_{1}, …, G_{m} ∈ K[X_{0}, …, X_{n}], G′_{1}, …, G′_{m} ∈ L[X_{0}, …, X_{n}] be two generic systems of forms such that deg(G_{j}) = deg(G′_{j}) for all j. Let G_{j} = ∑\underline{i} a(j) ; \underline{i}X\underline{i},

G′_{j} = ∑\underline{i} a′ ; \underline{i}^{(j)}X\underline{i}. Let k and l respectively be the subfields of K and L generated by the coefficients of G_{j} and G′_{j} over F. Then there exists a (unique) isomorphism between k and l under which a_{i}^{(j)} corresponds to a′_{i}^{(j)}. We thus have for all D ∈ ℕ_{0}

χ_{K[X_{0},...X_{n}]/(G_{1},...,G_{m})}(D) = dim_{K}((K[X_{0}, … X_{n}]/(G_{1}, …, G_{m}))_{D}) =

dim_{k}((k[X_{0}, … X_{n}]/(G_{1}, …, G_{m}))_{D}) =
dim_{l}((l[X_{0}, … X_{n}]/(G′_{1}, …, G′_{m}))_{D}) =

dim_{L}((L[X_{0}, … X_{n}]/(G′_{1}, …, G′_{m}))_{D}) = χ_{L[X_{0},...X_{n}]/(G′_{1},...,G′_{m})}(D) .

⊓ ⊔

Together with (12), the following proposition is crucial for our analysis of the XL-algorithm.

Proposition 2. Let K be any field (of any characteristic), and let F_{1}, …, F_{m} ∈ R = K[X_{0}, …, X_{n}] be forms of degree d_{1}, …, d_{m} (not necessarily generic). Let H_{g} be the generic Hilbert series of type (n + 1; m; d_{1}, …, d_{m}). Let I := (F_{1}, …, F_{m}) ⊲ K[X_{0}, …, X_{n}]. Then we have the coefficient-wise inequality

H_{R/I} ≥ H_{g} .

This proposition seems to be well-known in commutative algebra (see e.g. Sect. 4 of [16]); for the lack of a suitable reference we include the proof in Appendix B.

Because of (12) and this proposition the task is now to study generic Hilbert series. The following proposition is a well-known statement from commutative algebra.

Proposition 3. Let m ≤ n+1, and let G_{1}, …, G_{m−1}, G_{m} = G be a generic system of forms in R = K[X_{0}, …, X_{n}], where G has degree d. Let J := (G_{1}, …, G_{m−1}) ⊲ R. Then for all D ∈ ℕ_{0} the multiplication map

G· : (R/J)_{D} ⟶ (R/J)_{D+d}, \overline{F} ↦ G · \overline{F}

is injective, in particular we have a short exact sequence

0 ⟶ (R/J)_{D} ⟶^{G·} (R/J)_{D+d} ⟶ (R/(J, G))_{D+d} ⟶ 0 .

(Here by (J, G) we denote the ideal of R generated by J and G.)

Indeed, this proposition is nothing but a reformulation of the well-known statement that a generic system of forms in K[X_{0}, …, X_{n}] with at most n + 1 elements forms a regular sequence (cf. [16, Sect. 4], Page 318). (The fact that a generic system of forms is a regular sequence can be seen as follows: By Lemma 3 in Appendix B, it suffices to prove that for all (d_{1}, …, d_{n+1}) ∈ ℕ^{n+1} there exist some forms F_{1}, …, F_{n+1} ∈ R of degrees d_{1}, …, d_{n+1} which form a regular sequence, and by [12, Theorem 16.1], the forms X_{0}^{d_{1}}, …, X_{n}^{d_{n+1}} do form a regular sequence.)

Note that the Hilbert series of R = K[X_{0}, …, X_{n}] is

H_{R} = ∑_{i} \binom{n + i}{i}T^{i} = \frac{1}{(1 − T)^{n+1}}  (13)

(see e.g. [16, Sect. 1]). Proposition 3 and (13) imply by induction on m:

Proposition 4. Let m ≤ n+1, and let G_{1}, …, G_{m} be a generic system of forms of degrees d_{1}, …, d_{m} in R. Then the Hilbert series of R/(G_{1}, …, G_{m}) is

\frac{∏_{j=1}^{m}(1 − T^{d_{j}})}{(1 − T)^{n+1}} .

For simplicity we now concentrate until the end of this section on the case of quadratic equations.

Proposition 5. Let m = n + c for some c ≥ 1. Let F_{1}, …, F_{m} be quadratic forms in R = K[X_{0}, …, X_{n}]. Then the Hilbert series of R/(F_{1}, …, F_{m}) is coefficient-wise greater-or-equal

(1 − (c − 1)T^{2})(1 + T)^{n+1} .

Proof. By Proposition 2 we only have to prove that the generic Hilbert series of type (n + 1; m; 2, …, 2) is coefficient-wise greater-or-equal (1 − (c − 1)T^{2})(1 + T)^{n+1}.

So let K be a field of characteristic 0, let R = K[X_{0}, …, X_{n}], and let G_{1}, …, G_{m} be a generic system of quadratic forms in R. (The assumption on the characteristic is not necessary for the following argument.) Let R′ := R/(G_{1}, …, G_{n+1}), and let I′ be the ideal generated by G_{n+2}, …, G_{m} in R′. Note that by the above proposition, the Hilbert series of R′ is (1 + T)^{n+1}. We have R/(G_{1}, …, G_{m}) ≃ R′/I′, thus

χ_{R/(G_{1},...,G_{m})}(D) = χ_{R′/(G_{n+2},...,G_{m})}(D) = dim_{K}(R′_{D}) − dim_{K}(I′_{D}) .

Now, for D ≥ 2, I′_{D} = ∑_{j=n+2}^{m} G_{j} · R′_{D−2}, where by definition G_{j} · R′_{D−2} is the image of R′_{D−2} under the multiplication map G_{j}· : R′_{D−2} ⟶ R′_{D}. It follows that

dim_{K}(I′_{D}) ≤ (m − n − 1) dim_{K}(R′_{D−2}) .

All in all, we have χ_{R/(G_{1},...,G_{m})}(D) ≥ χ_{R′}(D) − (c − 1)χ_{R′}(D − 2) ,

thus

H_{R/(G_{1},...,G_{m})} ≥ H_{R′} − (c − 1)T^{2}H_{R′} = (1 − (c − 1)T^{2})(1 + T)^{n+1} .

Proposition 6. Let K be any field, let m = n + c with c ≥ 1, let f_{1}, …, f_{m} ∈ K[X_{1}, …, X_{n}] be quadratic polynomials, and as in Sect. 2, let D_{min} be the minimal D with χ(D) ≤ D, where χ(D) is defined as above with respect to these polynomials. Then

D_{min} ≥ \frac{n}{\sqrt{c − 1} + 1} .

Sketch of the Proof. Let c ≥ 1, m = n + c, f_{1}, …, f_{m} and χ(D) be as in the proposition. By (12) and the above proposition, we have

χ(D) ≥ (\frac{(n − D + 2)(n − D + 3)}{(D − 1)D} − (c − 1)) · \binom{n + 1}{D − 2}

for all D ≥ 2. The proposition follows from the statement that (\frac{(n−D+2)(n−D+3)}{(D−1)D}− (c−1))·\binom{n+1}{D−2} > D for all D < \frac{n}{\sqrt{c−1}+1}. We only show the slightly weaker state-

ment that \frac{(n−D+2)(n−D+3)}{(D−1)D} − (c − 1) > 0 for all D < \frac{n}{\sqrt{c−1}+1}.

Let D < \frac{n}{\sqrt{c−1}+1}. Then D\sqrt{c − 1} + D < n, thus D^{2}(c − 1) < (n − D)^{2}. This

implies that (D − 1)D(c − 1) < (n − D + 2)(n − D + 3), i.e. \frac{(n−D+2)(n−D+3)}{(D−1)D} − (c − 1) > 0. ⊓ ⊔

Remark 5. For an application of the XL-algorithm to a system with m = n quadratic equations, one can easily see with Propositions 2 and 4 and (12) that one always has χ(D) ≥ 2^{n}, and for m = n + 1 quadratic equations, one has D_{min} ≥ n + 1. Both these results are consistent with conjectures in [7].

5 The maximal rank conjecture

The maximal rank conjecture (MR-conjecture) which we now state can be thought to be a (potential) generalization of Proposition 3.

Conjecture. Let K be a field of characteristic 0, and let G_{1}, …, G_{m−1}, G_{m} = G be a generic system of forms in R = K[X_{0}, …, X_{n}], where G has degree d. Let J := (G_{1}, …, G_{m−1}) ⊲ R. Then for all D ∈ ℕ_{0} the multiplication map

G· : (R/J)_{D} ⟶ (R/J)_{D+d}, \overline{F} ↦ G · \overline{F}

has maximal rank, that is it is injective if dim_{K}((R/J)_{D}) ≤ dim_{K}((R/J)_{D+d}) and it is surjective if dim_{K}((R/J)_{D}) ≥ dim_{K}((R/J)_{D+d}).

This conjecture – which is also known under the name “Fröberg’s Conjecture”

– can (in an equivalent formulation) be found in [10]. It is also stated in Sect. 4 of the informative overview article [16]. (Note however that the formulations at the beginning of Sect. 4 of [16] are a bit vague.) Interesting facts about this and related conjectures can be found in [15].

The conjecture is known to hold if one of the following five conditions is satisfied: m ≤ n + 1 (see Proposition 3), n = 1, n = 2, m = n + 2, D = min_{j}{deg(G_{j})} + 1 (see [10, 3.2.] and the citations in [16, Sect. 4]).

The conjecture is equivalent to the statement that

χ_{R/(J,G)}(D) = max{χ_{R/J}(D) − χ_{R/J}(D − d) , 0}

as one can easily see (cf. [16, Sect. 4]). (Here, we set χ_{R/J}(i) = 0 for i < 0.)

Obviously, if χ_{R/(J,G)}(D) = 0, then χ_{R/(J,G)}(D′) = 0 for all D′ > D. Using this fact, the conjecture can be reformulated via Hilbert series as:

H_{R/(I,G)} = |(1 − T^{d})H_{R/I}| ,  (14)

where for some power series p(T) with integer coefficients, |p(T)| denotes the power series q(T) = ∑_{i} q_{i}T^{i}, where

q_{i} = p_{i} if p_{j} > 0 for all j ≤ i
0 if p_{j} ≤ 0 for some j ≤ i .

Assumption. From now on, we assume that the maximal rank conjecture is valid.

Let K be a field of characteristic 0, let G_{1}, …, G_{m} be a generic system of forms in R, and let d_{j} := deg(G_{j}). Let I := (G_{1}, …, G_{m}). Using (13), (14) and Lemma 5 in Appendix C, we have

H_{R/I} = |\frac{∏_{j=1}^{m}(1 − T^{d_{j}})}{(1 − T)^{n+1}} | .  (15)

Definition 5. (see [16]) We call the right-hand side of the above equation the expected Hilbert series of a generic algebra of type (n + 1; m; d_{1}, …, d_{m}).

Proposition 2 implies:

Proposition 7. Let K be any field (of any characteristic), and let F_{1}, …, F_{m} ∈ R = K[X_{0}, …, X_{n}] be forms of degree d_{1}, …, d_{m} (not necessarily generic). Let H_{e} be the corresponding expected Hilbert series. Let I := (F_{1}, …, F_{m}). Then we have the coefficient-wise inequality

H_{R/I} ≥ H_{e} .

Together with (12), this proposition has the following implication for the original XL-algorithm.

Theorem 1. Let K be any field, let f_{1}, …, f_{m} be non-trivial polynomials in K[X_{1}, …, X_{n}] with degrees d_{1}, …, d_{m}. Let D ∈ ℕ, and let χ(D) be defined as in (9). Then χ(D) is greater-or-equal to the D^{th} term of the expected Hilbert series of a generic algebra of type (n + 1; m; d_{1}, …, d_{m}).

By Proposition 1, this theorem has the following corollary which can be used to analyze the reduced XL-algorithm.

Corollary 1. With the notations of the theorem, let K = 𝔽_{q}, and let χ^{red}(D) be defined as is (10). Then χ^{red}(D) is greater-or-equal to the D^{th} term of the expected Hilbert series of a generic algebra of type (n+1; m+n; d_{1}, …, d_{m}, q, …, q).

Remark 6. Let D_{n,m} be the degree of the expected Hilbert series of a generic algebra of type (n + 1; m; 2, …, 2). One can use the methods presented in [2, Sect. 5] to study asymptotic behaviors of D_{n,m}. A corresponding study is carried out in [3]. One obtains D_{n,n+c} ∼ \frac{n}{2} for any fixed c ≥ 2 and n ⟶ ∞. (More precise results for various small c can also be found in [3].) For a fixed α > 1, a reformulation of a result in [3] gives D_{n,αn} ∼ (α − \sqrt{α^{2} − α} − \frac{1}{2}) · n for n ⟶ ∞. For example, one has D_{n,2n} ∼ C · n with C = \frac{3}{2} − \sqrt{2} ≈ 0.0858 (which is consistent with the “Comparison with 2n equations over ℚ” on page 13 of [2]).

Acknowledgment

I thank G. Böckle, T. Bröcker, C. Cid, A. Conca, G. Frey, S. Galbraith, J. Herzog, J. Scholten, A. Wiebe and B.-Y. Yang for discussions. I am particularly in debt to J. Herzog and A. Wiebe for pointing out the “maximal rank conjecture” to me.

Support by the IST Programme “Ecrypt” of the European Union is gratefully acknowledged.

References

[1] M. Atiyah and I. Macdonald. Introduction to Commutative Algebra. Addison-Wesley, Reading, 1969.

[2] M. Bardet, J.-C. Faugère, and B. Salvy. Complexity of Gröbner basis computations for Semi-regular Overdetermined sequences over 𝔽_{2} with solutions in 𝔽_{2}. INRIA Rapport de recherche No. 5049, 2003.

[3] J.-M. Chen and B.-Y. Yang. All in the XL Familiy: Theory and Practice. manuscript from June 2004.

[4] J.-M. Chen and B.-Y. Yang. Theoretical Analysis of XL over Small Fields. In H. Wang, J. Pieprzyk, V. Varadharajan, editors, Information Security and Privacy, volume 3108 of LNCS, pages 277-288, Springer-Verlag, Berlin, 2004.

[5] N. Courtois. Higher Order Correlation Attacks, XL algorithm, and Cryptanalysis of Toyocrypt. In P.J. Lee, C.H. Lim, editors, Advances in Cryptology — ICISC 02, volume 2587 of LNCS, pages 182–199, Springer-Verlag, Berlin, 2002.

[6] N. Courtois, A. Klimov, J. Pararin, and A. Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. ”extended version”, available under http://www.minrank.org/xlfull.pdf (as of August 24, 2004).

[7] N. Courtois, A. Klimov, J. Pararin, and A. Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In B. Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of LNCS, pages 392–407. Springer-Verlag, Berlin, 2000.

[8] N. Courtois and J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In Y. Zheng, editor, Advances in Cryptology — ASIACRYPT 2002, volume 2501 of LNCS, pages 267–287. Springer-Verlag, Berlin, 2002.

[9] D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry. Springer-Verlag, New York, 1995.

[10] R. Fröberg. An inequality for Hilbert series of graded algebras. Math. Scand., 56:117–144, 1985.

[11] D. Knuth. The Art of Computer Programming. Addison-Wesley, Reading, 1973.

[12] H. Matsumura. Commutative Ring Theory. Cambridge University Press, Cambridge, UK, 1986.

[13] T. Moh. On the method of ”XL” and its inefficiency to TTM. manuscript from January 28, 2000, available under http://eprint.iacr.org/2001/047.

[14] S. Murphy and M.J.B. Robshaw. Essential algebraic structure within the AES. In M. Yung, editor, Advances in Cryptology — CRYPTO 2002, pages 1–16, 2002.

[15] K. Pardue. Generic Sequences of Polynomials. manuscript from March 30, 2000.

[16] G. Valla. Problems and Results on Hilbert Polynomials of Graded Algebras. In J. Elas and J. Giral, editors, Six Lectures on Commutative Algebra, volume 166 of Progress in Mathematics. Birkhäuser, Basel, 1996.

A On the connection between the the original and the reduced XL-algorithm

The purpose of this section is to prove Proposition 1.

As in Proposition 1, let K = 𝔽_{q}. Let

V_{D} := ⟨∏_{ℓ=1}^{k} X_{i_{ℓ}} · (X_{i}^{q} − X_{i}) with k + q ≤ D⟩_{K} ≤ K[X_{1}, …, X_{n}]_{≤D} .

Lemma 1. Let U be any K-vector subspace of K[X_{1}, …, X_{n}]_{≤D}. Then we have a short exact sequence

0 ⟶ U ∩ V_{D} ⟶ U ⟶ U^{red} ⟶ 0 .

Proof. It is obvious that U∩V_{D} is contained in the kernel of (…)^{red}. The converse follows from the following lemma. ⊓ ⊔

Lemma 2. Let f ∈ K[X_{1}, …, X_{n}]. Then there exist polynomials p_{1}, …, p_{n} of degree ≤ deg(f) − q with

f = p_{1} · (X_{1}^{q} − X_{1}) + ⋯ p_{n} · (X_{n}^{q} − X_{n}) + f^{red} .

Proof. By the linearity of (…)^{red}, it suffices to prove the statement for monomials, and for monomials it is obvious by the very definition of (…)^{red}. ⊓ ⊔

Let us use the definitions of Sect. 3.

We have by Lemma 1

(K[X_{1}, …, X_{n}]_{≤D})^{red} ≃ K[X_{1}, …, X_{n}]_{≤D}/V_{D} ,
(U_{D})^{red} ≃ U_{D}/(U_{D} ∩ V_{D}) ≃ (U_{D} + V_{D})/V_{D} ≃ Ũ_{D}/V_{D} ,

thus

\begin{matrix}(K[X_{1}, …, X_{n}]_{≤D})^{red}/(U_{D})^{red} ≃ (K[X_{1}, …, X_{n}]_{≤D}/V_{D})/(Ũ_{D}/V_{D}) \\ ≃ K[X_{1}, …, X_{n}]/Ũ_{D} . \end{matrix}

This implies:

χ^{red}(D) = dim_{K}((K[X_{1}, …, X_{n}]_{≤D})^{red}/(U_{D})^{red})
= dim_{K}(K[X_{1}, …, X_{n}]_{≤D}/Ũ_{D}) = χ̃(D) .

B Hilbert series of generic and arbitrary algebras

The purpose of this section is to prove Proposition 2. Let us before we come to the proof state two lemmata.

Lemma 3. Let A be a domain with quotient field Q. Let K be a field and let φ : A ⟶ K be a homomorphism, and let Φ : A[X_{0}, …, X_{n}] ⟶ K[X_{0}, …, X_{n}] be the canonical extension of φ. Let I ⊲ A[X_{0}, …, X_{n}] be a homogeneous ideal (that is, an ideal generated by homogeneous polynomials). Then we have the coefficient-wise inequality

H_{K[X_{0},...,X_{n}]/(Φ(I))} ≥ H_{Q[X_{0},...,X_{n}]/(I)} .

Proof. Let D ∈ ℕ_{0}. The map φ : A ⟶ K induces a canonical map

\begin{matrix}(A[X_{0}, …, X_{n}]/I)_{D} ⟶ (A[X_{0}, …, X_{n}]/I)_{D} ⊗_{A} K \\ ≃ (A[X_{0}, …, X_{n}]/I ⊗_{A} K)_{D} ≃ (K[X_{0}, …, X_{m}]/(Φ(I)))_{D}. \end{matrix}

This implies that

χ_{K[X_{0},...,X_{n}]/(Φ(I))}(D)

= dim_{K}((A[X_{0}, …, X_{n}]/I)_{D} ⊗_{A} K)
≥ dim_{Q}((A[X_{0}, …, X_{n}]/I)_{D} ⊗_{A} Q) by Lemma 4 below
= dim_{Q}((Q[X_{0}, …, X_{n}]/(I))_{D})
= χ_{Q[X_{0},...,X_{n}]/(I)}(D) .

Lemma 4. Let A be a domain with quotient field Q, and let M be a finitely generated A-module. Let K be a field and let φ : A ⟶ K be a homomorphism. Then

dim_{K}(M ⊗_{A} K) ≥ dim_{Q}(M ⊗_{A} Q) .

Proof. Let 𝔪 be the kernel of φ. Then M ⊗_{A} K ≃ M_{𝔪} ⊗_{A_{𝔪}} K and M ⊗_{A} Q ≃ M_{𝔪} ⊗_{A_{𝔪}} Q. We can thus assume that A is a local ring with maximal ideal 𝔪 = ker(φ). As the dimension of a vector space is stable under base-change, we can further assume that φ is surjective. Now if m_{1}, …, m_{r} form modulo 𝔪 a basis of M ⊗_{A} K over K then by Nakayama’s Lemma ([9, Corollary 4.8]) they generate the A-module M, thus they generate M ⊗_{A} Q over Q. ⊓ ⊔

Proof of Proposition 2. We keep the notations of the proposition. The proposition follows from Lemma 3 applied to the multivariate polynomial ring A =

ℤ[\{a(j) ; \underline{i}\}], the ideal I = (G_{1}, …, G_{m}), where G_{1}, …, G_{m} with G_{j} = ∑\underline{i} a(j) ; \underline{i}X\underline{i}

and deg(G_{j}) = d_{j} is a generic system of forms, and the specialization homomorphism φ : A ⟶ K sending a(j) ; \underline{i} to the corresponding coefficient of F_{j}. (Note

that the quotient field of A is ℚ(\{a(j) ; \underline{i}\}) which has characteristic 0.) ⊓ ⊔

C A lemma on power series

The following lemma generalizes [10, Lemma 4]. For the convenience of the reader, we include a proof.

Lemma 5. Let p(T) be a power series with integer coefficients, let d ∈ ℕ. Then

|(1 − T^{d})p(T)| = |(1 − T^{d})|p(T)|| .

Proof. Note that ((1 − T^{d})p(T))_{i} = p_{i} for i < d and ((1 − T^{d})p(T))_{i} = p_{i} − p_{i−d} for i ≥ d.

Thus the coefficients whose index is < d of both sides agree. Furthermore, if p_{i} < 0 for some i < d, then both sides are equal.

Let us assume that for all i = 0, …, d − 1, we have p_{i} > 0.

If now for all i we have p_{i} −p_{i−d} > 0, then we also have p_{i} > 0 for all i as can easily be seen by induction on i. In this case, both sides agree with (1−T^{d})p(T).

Assume that this is not the case and let a be the least natural number for which p_{a} − p_{a−d} ≤ 0.

Then for each i < a, we have p_{i} > 0 again by induction on i.

There are two cases: Either p_{a} > 0. Then |p(T)|_{a} −|p(T)|_{a−d} = p_{a} −p_{a−d} < 0 by definition of a. Or p_{a} ≤ 0. Then |p(T)|_{a} − |p(T)|_{a−d} = −p_{a−d} < 0.

We conclude that for i ≤ d − 1, the i-th coefficient of both sides agrees with p_{i}, for d < i < a, the i-th coefficient of both sides agrees with p_{i} − p_{i−d}, and for i ≥ a, the i-th coefficient of both sides is 0. ⊓ ⊔

The work described in this paper has been supported in part by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT. The information in this document reflects only the author’s views, is provided as is, and no guarantee or warranty is given that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.