13    Commutative Gröbner Basis Methods

13.1    Commutative Gröbner Bases

Besides numbers and group elements, polynomials are natural objects to use in algebraic cryptography. Recall that a polynomial f is a formal linear combination f = c₁t₁ + ··· + c_st_s whose coefficients c_i are taken in a field K and where the elements t_i are terms, that is power products of indeterminates x_i. The set of all polynomials of this form is called the polynomial ring P = K[x₁,..., x_n]. This set is a commutative ring with identity. In other words, polynomials can be added and multiplied in a natural way and the usual rules such as the associative and distributive laws hold.

Example 13.1.1. Using the base field K = ℚ and the indeterminates x, y, z, we can add the polynomials f = xy + yz and g = x² + xy and obtain f + g = x² + 2xy + yz. Their product equals f · g = x³y + x²y² + x²yz + xy²z. Notice that we can also factor f and g in the form f = y(x + z) and g = x(x + y).

For cryptographic applications, we need to work effectively with polynomials. The main tool for effective calculations with polynomials and polynomial ideals are Grobner bases. The first task we have to solve is to make equality of polynomials effective and to store them efficiently. How is it possible to detect in the preceding example that the polynomial xy²z + x²y² + x³y + x²yz equals f · g? Clearly, we need to order the terms in a unique way.

Definition 13.1.2. Let x₁,...,x_n be indeterminates, and let

be the set of terms in these indeterminates. A complete ordering relation a is called a term ordering on if the following conditions are satisfied.

(1)  The relation a is multiplicative, that is, if two terms t₁, t₂ ϵ satisfy t₁ ≤_σ t₂ and if t₃ ϵ then we have t₁t₃ ≤_σ t₂t₃.

(2)  The relation a is a well-ordering, that is, every decending chain t₁ ≥_σ t₂ ≥_σ ··· in is eventually stationary.

It is easy to see that the second condition is equivalent to requiring t ≥_σ 1 for all t ϵ . There exist plenty of term orderings, and many of them have special useful properties. The following example introduces two well-known term orderings.

Example 13.1.3. Let be the set of terms in the indeterminates x₁,..., x_n.

(1)  For and we let t ≤_lex t′ if and only if one of the following conditions holds:

–  α₁ < β₁

–  α₁ = β₁ and α₂ < β₂

–  ⋮

–  α₁ = β₁,..., α_n-1 = β_n-1 and α_n < β_n

–  t = t′

It is easy to check that this defines a term ordering ≤_lex on . It is called the lexicographic term ordering.

(2)  For practical computations, the most well-known and useful term ordering is the degree reverse lexicographic term ordering ≤_drl . It is defined by letting t ≤_drl t′ for and if and only if t = t′ or one of the following conditions is satisfied:

–  deg(t) = α₁ + · + α_n < deg(t′) = β₁ + · + β_n

–  deg(t) = deg(t′) and α_n > β_n

–  deg(t) = deg(t′), α_n = β_n and α_n-1 > β_n-1

–  deg(t) = deg(t′), α_n = β_n,..., α;₃ = α₃ and α₂ > β₂

It is straightforward to verify that these conditions indeed define a term ordering.

Given a term ordering σ, there is a natural way to represent a non-zero polynomial f ∊ P, namely to write f = c₁t₁ + · + c_st_s with c_j ∊ K and terms t_j ∊ satisfying t₁ >_σ · >_σ t_s. Using these representations, we can now define several notions which are central to Grobner basis theory.

Definition 13.1.4. Let σ be a term ordering on Tⁿ, and letf = c₁t₁ + · + c_st_s € P {0} be represented as above.

(1)  The term Lt(f) = t₁ is called the leading term off with respect to σ.

(2)  The field element Lc(f) = c₁ is called the leading coefficient of f with respect to σ.

(3)   The polynomial Lm(f) = c₁t₁ is called the leading monomial of f with respect to σ.

For instance, the polynomial f = x² + xy + y³ satisfies Lt_lex(f) = x² and Lt_drl(f) = y³. These definitions can be extended to polynomial ideals. A set of polynomials I is called an ideal in P if it is a subgroup with respect to addition and if it has the property that f ϵ I and g ϵ P imply fg ϵ I. Important examples of ideals are obtained as follows.

Example 13.1.5. Let I be a subset of the polynomial ring P.

(1)  If there exists a polynomial f ϵ P such that I = [fg | g ϵ P} then I is called the principal ideal generated by f and is denoted by I = (f).

(2)  More generally, if there exist polynomials f₁,...,f_s ϵ P such that I = [f₁g₁ + · + f_sg_s | g_i ϵ P} then I is called the ideal generated by f₁,...,f_s and is denoted by I = (f₁,...,f_s).

As an application of Grobner basis theory we shall see that, in fact, every ideal in P is of the type described in the preceding example. But first we generalize the notion of a leading term as follows.

Definition 13.1.6. Let σ bea term ordering on Tⁿ, and let I be an ideal in P. Then the ideal

Lt_σ (I) = (Lt_σ (f) | f ϵ I)

                                                 = [f₁g₁ + · + f_sg_s | s ≥ 0, f₁ ϵ I, g_j ϵ P}

is called the leading term ideal of I with respect to σ.

At this point we encounter a problem which is one of the main incentives to introduce Gröbner bases, namely the fact that the leading terms of a set of generating polynomials need not generate the leading term ideal of an ideal. The following example is a case in point.

Example 13.1.7. Let P = K[x, y],let σ = drl, and letI = (f₁, f₂) be the polynomial ideal generated by f₁ = x² - 1 and f₂ = xy - 1. Then we have x - y = yf₁ - xf₂ ϵ I and therefore x = Lt_σ(x - y) ϵ Lt_σ (I). Thus the inclusion (Lt_σ(f₁), Lt_σ(f₂)) c Lt_σ(I) is strict.

This example leads us to the following definition.

Definition 13.1.8. Let σ be a term ordering on Tⁿ,let I c P be a polynomial ideal, and let G c I be a subset of I. The set G is called a σ -Gröbner basis of I if Lt_σ (I) = (Lt_σ (g) | g ϵ G), that is if the leading term ideal of I is generated by the leading terms of the polynomials in G.

For instance, the polynomials in the preceding example can be extended to a Gröbner basis of I as follows.

Example 13.1.9. In the setting of the preceding example, let f₃ = x - y ϵ I and f₄ = ff - yf3 = y² - 1 ϵ I. Then the set G = {/1, ff, f3, f₄} satisfies (Lt_ff (/1),..., Lt_ff f)) = (x²,xy, x,y²) = (x,y²).Usingf₃ andf₄, it is not difficult to show that no polynomial of the form c₁y + c₂ with non-zero constants c₁ or c₂ is contained in I. Hence we have Lt_σ (I) = (x, y²) and it follows that G is a σ - Gröbner basis of I.

In general, every finite set of polynomials generating an ideal I can be extended to a finite Gröbner basis of I. This is achieved by Buchberger’s Algorithm. To introduce this algorithm, we first have to describe the multivariate version of polynomial division.

Proposition 13.1.10 (The Division Algorithm). Let P = K[x₁,...,x_n ], let a be a term ordering on Tⁿ, and letf, g₁,..., g_s ϵ P. Consider the following instructions.

(1)  Let q₁ = · = q_s = r = 0 and h = f.

(2)  Repeat the following steps until h = 0. Then return (q₁,..., q_s) and r and stop.

(3)  Repeat the following step as often as possible.

(4)  Find the smallest i ϵ {1,..., s} such that Lt_σ (h) is a multiple of Lt_σ (g_j). Ifsuch an i exists, replace q_j by q_j + Lm_σ (h)/ Lm_σ (g_j) and hbyh - (Lm_σ (h)/ Lm_σ (g_j)) g_j.

(5)  Replace r by r + Lm_σ (h) and hbyh - Lm_σ (h).

This is an algorithm which computes (q₁,..., q_s) ϵ P^s and r ϵ P such that f = q₁g₁ + · + qg + r and such that the following conditions hold.

(1)  No term ofr is divisible by any of the terms in [Lt_σ (g₁),..., Lt_σ (g_s)}.

(2)  For all i such that q_j = 0 we have Lt_σ (q_jg_j) <_σ Lt_σ (f).

Proof. Since the leading term of h becomes smaller with respect to σ during each execution of (4) or (5), and since σ isa term ordering, the algorithm is finite. Next we note that the equality f = q₁g₁ + · + q_sg_s + h + r holds throughout the execution of the algorithm. Since the algorithm stops when it reaches h = 0, we obtain the desired equality. The fact that the two additional conditions hold follows immediately from the descriptions of steps (4) and (5).

The division algorithm produces a polynomial NR_{a G}(f) = r which depends on the order of the elements in G = (g₁,... ,g_s). This polynomial is called the normal remainder of f with respect to G. Besides the Division Algorithm, we need one further ingredient for Buchberger’s Algorithm.

Definition 13.1.11. Let σ be a term ordering, let f_j, fj ϵ P {0}, and let Lm_σ(f_k) = c_kt_k with c_k ϵ K and t_k ϵ Tⁿ for k ϵ {, j}. Then we let t_jj = lcm(t_j, tj)/t_j and j = lcm(t_j, t_;-)/t_;- and call the polynomial S_jj = 1 t_jjf_j - 1 j fj the S-polynomial of f_j and fj.

The idea behind the definition of S_jj is that both tj f_j and j fj have thesameleading term lcm(t_j, tj) and that this term cancels in S_jj. Therefore the polynomial S_jj has a chance to produce a “new” leading term, and this is used in Buchberger’s Algorithm as follows.

Theorem 13.1.12 (Buchberger’s Algorithm). Let P = K[x₁,.. .,x_n], let a be a term ordering on Tⁿ, and letf₁,..., f_s ϵ P be non-zero polynomials which generate an ideal I = (f₁,...,f_s). Consider the following instructions.

(1)  Let G = (f₁,... ,f_s) and B = {(i, j) | 1 < i < j < s}.

(2)  Repeat the following steps until B = 0. Then return G and stop.

(3)   Choose a pair (i, j) ϵ B and remove it from B.

(4) Compute the S-polynomial S_jj off and fj and its normal remainder Sj = NR_{a >G}(Sy). IfSj = 0 then continue with step (2).

(5)  Increase s by one, append f_s = Sjto G, and append {(i, s) | 1 < i < s - 1} toB. Then continue with step (2).

This is an algorithm which computes a a-Grobner basis G of the ideal I.

For a proof of the finiteness and correctness of this algorithm, we refer to [KR1], Section 2.5. To get a feeling for the performance of this algorithm, let us apply it in the case of Example 13.1.7.

Example 13.1.13. Let P = K[x,y], let σ = drl, and let f₁ = x² - 1 and f₂ = xy - 1. Following Buchberger’s Algorithm, we compute S₁₂ = yf₁ - xf₂ = x - y and S1₂ = S₁₂ and appendf₃ = S1₂ = x - y to G. At this point we have B = {(1,3), (2,3)}.

Working on the pair (1,3) yields S₁₃ = f₁ - xf₃ = xy - 1 andS’₁₃ = 0. Next we check the pair (2,3) and get S₂₃ = f₂ - yf₃ = y² - 1 and S’₂₃ = S₂₃. Thus we appendf₄ = y² - 1 to G and have B = {(1,4), (2,4), (3,4)}. Working out these three pairs produces Sj = 0 each time, so that the algorithm returns G = (f₁,f₂,f₃,f₄) and stops.

Gröbner bases and Buchberger’s Algorithm have numerous applications in computational algebra. We end this section by listing a few of them which will be of use for algebraic cryptography. For detailed proofs of these results, we refer to [KR1].

Proposition 13.1.14 (Macaulay’s Basis Theorem). Let f₁,...,f_s e P be polynomials which generate an ideal I = (f₁,... ,f_s). We choose a term ordering a and use Buchberger’s Algorithm to compute a a-Gröbner basis G = (g₁,..., g_t) of I. Then the residue classes ofthe terms in the set

O_σ (I) = Tⁿ Lt_σ (I) = {t e Tⁿ | no term Lt_σ (g¡) divides t}

form a K-vector space basis of P/I.

Proposition 13.1.15 (Ideal Membership Test). Given apolynomial ideal I and apolyno- mialf e P, we can check as follows whether f e I holds:

(1)  Choose a term ordering a and use Buchberger’s Algorithm to compute a a - Gröbner basis G of I.

(2)  Using the Division Algorithm, check whether NR_{a G}(f) = 0.

13.2  Commutative Gröbner Basis Cryptosystems

The computation of a Gröbner basis using Buchberger’s Algorithm has a very high worst-case complexity: EXPSPACE. The idea underlying Gröbner basis cryptosystems is to utilize this fact by constructing a cryptosystem whose security depends on the difficulty of computing a certain Gröbner basis. The first such cryptosystem was suggested by M. Fellows and N. Koblitz in 1994 (see [FK]) and is called the Polly Cracker Cryptosystem.

Polly Cracker Key Generation

Let K be a finite field and P = K[x₁, ...,x_n] a polynomial ring over K. Suppose that Bob wants to send a message m to Alice. The message space we use is P = K, and the ciphertext space is c = P. The secret Key k will be an element of K = Kⁿ. To generate it, we choose a random vector k = (a₁,..., a_n)in Kⁿ.

Next Alice chooses s > 1 and random polynomials f₁,..., f_s ϵ P. Then she computes the polynomialsg_j = f_j - f_j(a₁,..., a_n)for i = 1,...,s. The tuple (g₁,... ,g_s) ϵ P will serve as Alice’s public Key.

Encryption and Decryption

To encrypt a message m ϵ K, Bob chooses random polynomials h₁,...,h_s ϵ P and computes the ciphertext polynomial c = m + h₁g₁ + · + h_sg_s. In order to decrypt a ciphertext unit c ϵ P, Alice evaluates c(a₁,..., a_n) and obtains the original message unit m.

The correctness of this cryptosystem follows from the fact that we have

and thus

How is this cryptosystem related to Gröbner bases? Let us analyse its security. To decrypt a ciphertext unit c ϵ P, an attacker has to find an element z ϵ K such that c + z is contained in the ideal I = (g₁,...,g_s). To do this, he may try to compute a Gröbner basis G of I and then determine z using the equality z = NR_{a G}(c). Hence the Polly Cracker cryptosystem is not secure if an attacker is able to compute a Gröbner basis of I.

To make matters worse, the attacker may actually get away with computing a small part of a Gröbner basis of I. In the computation of the normal remainder NR_{a G}(c), only finitely many elements of the Gröbner basis G are used. Hence it may suffice to determine a partial Gröbner basis in order to decipher a single message.

A further weakness of the Polly Cracker cryptosystem is revealed by a statistical analysis of the ciphertext. In the computation of c = m + h₁g₁ + · + h_sg_s, usually only a small percentage of the terms cancels out completely. Most terms of the products h_jg_j will be contained in the ciphertext. Thus, if t is a term occurring in one of the secret polynomials g_j, many of its multiples will tend to show up in the ciphertext polynomial c. It is clear that a careful statistical analysis of greatest common divisors of the terms in c may reveal individual terms t. Then one can simplify the corresponding polynomial h_t and create a simpler ciphertext for the same message. By repeating this construction, it is frequently possible to decipher c.

In spite of these problems, Koblitz suggested in [Ko2], Ch. 5, several special cases of Polly Cracker cryptosystems whose security seems to be high at first glance.

Example 13.2.1 (The Graph-3-Colouring Cryptosystem). A graph is a pair r = (V, E) consisting of a set of vertices V = {v₁,..., v_r} and a set of edges E = {e₁,..., e_s} c V x V, each of which connects two vertices. A 3-colouring of a graph r = (V, E) is

a map $ : V —> Z₃ such that $ (v,) = $ (v_;) whenever there is an edge e_k = (v_j, Vj) connecting v_j and Vj. The graph r is called 3-colourable if a 3-colouring exists.

Given a graph r, the following two problems are NP-hard:

–  Decision problem: Is r 3-colourable?

–  Search problem: If r is 3-colourable, find a 3-colouring!

Based on these problems, we construct a Polly Cracker cryptosystem as follows. Alice chooses a suitable 3-colourable graph r = (V, E) for which she Knows a 3-colouring. (The question which graphs could be considered suitable will be discussed below.) Thus her secret Key is a tuple (a_jj) ϵ V xZ₃ such that

Alice’s public Key then consists of the following 4r + 3s polynomials in the ring K[x_jj |

i ϵ {1,.. .,r}, j ϵ {0,1,2}], where K = Z₃ = {0,1,2}, r = #V, ands = #E:

–  f_j = x_j1 + x_j2 + x_j3 - 1for i = 1,..., r

–  g_jj_k = x_jjx_jk for i = 1,..., r and 0 < j < k < 2

–  hjjk = xjkj if (i, j) ϵ E and 0 < j < 2

Based these Keys, Alice and Bob use the Polly Cracker cryptosystem.

The following observations show that the security of this cryptosystem relies on the difficulty of solving the 3-colouring search problem. First we check that (a_jj) is a common zero of the polynomials in the public Key.

(1)  For i = 1,..., r,we havef (a_j0, a^, a_j2) = a_j0 + a_j1 + a_j2 - 1 = 0, since every vertex has precisely one colour.

(2)   For i = 1,..., r and 0 < j < k < 2, we haveg_jj_k(a_j0, a_j1, a_j2) = a_jja_jk = 0 since every vertex has precisely one colour.

(3)  For i,j ϵ {1,...,r} such that (i,j) ϵ E and for every k ϵ {0,1,2}, we have h_jj_k(a_j0, a_j1, a_j2) = a_jkaj_k = 0 because not both vertices v_j and vj have colour K.

Conversely, let us show that every common zero (c j of the polynomials in the public Key yields a 3-colouring of r.

(4)  Since c_jjc_jk = 0 for j = K, at most one of the numbers {c_j0, c_j1, c_j2} is non-zero.

(5)  Since c_j0 + c_j1 + c_j2 = 1, it follows that precisely one of the numbers {c_j0, c_j1, c_j2} is one and the other two are zero.

(6)  Since c_jkcj_k = 0 for (i, j) ϵ E, two vertices which are connected by an edge have different colours.

The upshot of this discussion is that the Knowledge of a 3-colouring of r is sufficient to break the graph 3-colouring cryptosystem. Finding a 3-colouring is equivalent to computing a common zero (a_jj) of the set of public polynomials, and therefore equivalent to computing a Gröbner basis G = {x_jj - a_tj | i ϵ {1,..., r}, j ϵ {0,1,2}} of an ideal containing the public polynomials. If we find a graph for which a 3-colouring is hard to find, a Gröbner basis of this Kind will be hard to compute.

So, what is the problem with this construction? First of all, we have to find a suitable graph. For most concrete instances of the graph 3-colouring search problem, the actual complexity will be much lower than the worst-case complexity. In fact, in most cases it will be linear in the size of r. Therefore we may have to choose very large graphs to make this problem infeasible. However, then we create a very large public Key {f_j, g_jj_k, h_jj_k} and the amount of data that we have to transmit in order to send a message consisting of a single element of Z₃ is huge. In other words, the data rate of this cryptosystem will be abysmal. Finally, we still face the problem to choose the graph r (and thus the public Key polynomials) such that the attacks using partial Gröbner bases and statistical analysis of the terms in the ciphertext become infeasible.

Until now, nobody has been able to find a convincing simultaneous solution to the problems inherent in the Polly Cracker cryptosystem. In order to get a wider choice of constructions, we introduce a far-reaching generalization, namely the general Commutative Gröbner Basis Cryptosystem (CGBC).

CGBC Setup and Key Generation

Let K be a finite field, let P = K[x₁,.. .,x_n], let σ be a term ordering on Tⁿ, let I c P be an ideal, and let G = {g₁,...,g_s} be a σ -Gröbner basis of I. The set G will serve as Alice’s secret Key. To construct a public Key, she chooses a set of terms O in Tⁿ Lt_σ (I). The K-vector space P = (O)_K generated by O is the set of plaintext units for the CGBC. The set of ciphertext units will be c = P. Finally, Alice chooses suitable polynomials f₁,... ,f_t ϵ I which constitute the public Key of the CGBC. (The correct interpretation of “suitable” will be discussed below.)

CGBC Encryption and Decryption

Let m ϵ (O}_K be the plaintext unit that Bob wants to send to Alice. He chooses suitable (e.g., sufficiently random) polynomials h₁,...,h_t ϵ P and computes c = m + h₁f₁ + · + h_tf_t. To decrypt a ciphertext unit c ϵ P, Alice calculates m = NR_{a G}(c).

The correctness of this procedure follows from fact that division by a Gröbner basis yields an ideal membership test (see Prop. 13.1.15). For m’ = NR_{a G}(c) we have m’ = c (mod I), and therefore m’ - m = 0 (modI). Since m and m’ are constants and I = P, they have to be equal.

General commutative Gröbner basis cryptosystems face a number of possible attacks by Eve, the evil attacker. Let us discuss some of them.

(1)  Obviously, the cryptosystem can be broken if Eve succeeds in computing any Gröbner basis of I. One difficulty may be that she does not Know I, but only a smaller ideal J = (f₁,...,f_t} for which a Gröbner basis may be hard to come by. On the other hand, it suffices for Eve to find any Gröbner basis of any ideal containing J.

(2)  As for the Polly Cracker cryptosystem, Eve can decipher an individual ciphertext unit c if she Knows a sufficiently large partial Gröbner basis of J (or I). The reason is that, in the division steps reducing c —> NR_{a G}(c), only some of the elements of G are involved.

(3)  In the calculation of a ciphertext unit c = m + h₁f₁ + · + h_tf_t, usually not many terms in the polynomials h_if_i cancel out completely. Unless special care is taken in the choice of the coefficient polynomials h_j, large subsets of the terms in c will have non-trivial greatest common divisors. Using statistical analysis, Eve may determine individual terms in h_j and simplify the ciphertext without changing the underlying plaintext.

(4)  In the computation of c, a large amount of cancellation of higher-degree terms has to occur to make the following Linear Algebra Attack infeasible: Eve guesses a degree bound for the polynomials h_i and writes them down using indeterminate coefficients. Then the equality c = m + h₁f₁ + · + h_tf_t yields a linear system of equations for these unknown coefficients. In addition, Eve may proceed to solve this system degree by degree (with respect to the terms in c) and utilize heuristics to exclude the appearance of certain terms in the polynomials h_j, thereby reducing the sizes of the partial linear systems of equations.

(5)  Finally, Eve may resort to a chosen-ciphertext-attack. If she is able to decipher illegal ciphertexts consisting of the terms t_j generating Lt_σ (I), she may construct a Gröbner basis {g₁, ...,g_s} of I via g_j = t_j - NR_{a >G}(t_j). Hence Alice has to restrict the set of terms O defining the plaintext unit space such that illegal ciphertexts like tj are revealed by having terms from (Tⁿ Lt_σ (I)) O in their decryption. Then her decryption algorithm can reject illegal ciphertexts.

Altogether, it has proven quite difficult to generate secure instances of commutative Gröbner basis cryptosystems, in particular if the need for an acceptable data rate is taken into account. Nevertheless, finding a large enough number of such instances is an attractive goal. We have seen that it is possible to encode NP-hard problems into the task of computing a Gröbner basis. Thus Gröbner basis cryptosystems are candidates for Post Quantum Cryptography. Later we study suggestions to overcome the aforementioned difficulties by resorting to non-commutative algebraic structures (such as free associative algebras or certain group rings) which support analogous Gröbner basis theories.

13.3  Algebraic Attacks Using Gröbner Bases

After seeing the difficulties involved in using (commutative) Gröbner bases for constructing new cryptosystems, let us turn the tables and try to use Gröbner bases to break existing cryptosystems. This topic is Known as algebraic attacks and has gained widespread attention after F. C. Faugere used it to meet the HFE Challenge (see [Fau]). Let us explain the basic idea first.

Every encryption map of a cryptosystem can be represented by a map sending bit- tuples to bit-tuples. Mathematically, we represent it as a map e : Zf —> Zf where P cZf and c cZf .A map like this is always polynomial, that is for K = Z₂ there exist polynomialsf₁,...,f_s ϵ K[x₁, ...,x_n] such that

for all (a₁,..., a_n) ϵ Kⁿ. Of course, these polynomials f₁,... ,f_s are not uniquely determined. Suppose that g₁,...,g_s ϵ K[x₁, ...,x_n] are further polynomials with the property that

for all (a1, . . . , an) P. Then the differences fi .gi are contained i he vanishing ideal

of P. It is easy to check that I(P) is in fact a polynomial ideal. Below we shall see an effective and efficient algorithm to compute a system of generators of this vanishing ideal. In this setting, we can mount different algebraic attacks using one of the following methods.

Remark 13.3.1 (Algebraic Known-Plaintext-Attack). Suppose that Alice and Bob are using a symmetric cipher and one or more plaintext-ciphertext pairs are Known to Eve. She represents the input bits of the encryption map by indeterminates x₁,..., x_n, certain bits of intermediate results by indeterminates y_jj, and the bits of the unknown Key by indeterminates k₁,...,k_e. Then Eve writes down the encryption map e : Zf —> Zf using polynomialsf₁,..., f_s ϵ Z₂ [x₁,..., x_n, {y_jj}, K₁,..., k_e]. By substituting the Known plaintext-ciphertext pairs, Eve obtains a system of polynomial equations in the indeterminates y_jj and K₁,..., k_e.

In many cases, this polynomial system of equations has a unique solution ({a,-,-}, b₁,...,b_e) defined over Z₂. In the language of Gröbner bases, this means that the ideal generated by those equations has the Gröbner basis G = {y, - a, }u{k₁ - b₁, ...,k_e - b_e}. If Eve is able to compute that Gröbner basis, she can use the secret Key (b₁,..., b_e) to decrypt further ciphertext units. She has broken the cryptosystem.

The situation of this remark can for instance occur if Bob encrypts a pdf-file (whose first four bytes are %PDF) and uses no further precautions. In less favourable situations Eve may still try to launch the following attack.

Remark 13.3.2 (Algebraic Ciphertext-Only-Attack). Suppose that Alice and Bob are using a symmetric cipher. Eve intercepts a number of ciphertext units. As in the preceding remark, she represents the encryption map e : ^2 —> Zj with polynomials

using different sets of indeterminates x1^m),..., , y(,^m) for every intercepted ciphertext unit, but the same indeterminates k₁,...,k_e for the Key bits. Then Eve tries to solve the resulting polynomial system for k₁,...,k_l and thereby break the cryptosystem.

It is clear that similar algebraic attacks can be mounted against public Key ciphers and stream ciphers. For the sake of brevity, we describe only the first case in more detail.

Remark 13.3.3 (Algebraic Attacks to Public Key Systems). Suppose that Alice and Bob use a public Key cryptosystem. Since Eve Knows the public Key, she can describe the encryption map e : Z2 —> using polynomials /₁,...,/_s e Z₂[x₁,...,x_n] which do not involve any indeterminates related to the secret Key. Hence, if Eve want to attack a single ciphertext unit, it suffices to solve the polynomial system f(x₁, ...,x_n) = c, where i = 1,..., s and c, is the i-th bit of the ciphertext.

Eve may also decide to attack the public Key. For this purpose she describe the decryption map ô : Zj —> ^2 by polynomials gj(y₁,..., y_s, K₁,..., k_e) where the indeterminates y ₁,..., y_s represent the bits of the ciphertext and the indeterminates k₁,...,k_e represent the bits of the secret Key. Then Eve uses the publicly Known encryption map to create as many plaintext - ciphertext pairs as she needs and sets up arbitrarily many polynomial equations in the indeterminates k₁,...,k_e whose only solution over Z₂ is the secret Key.

Let us apply this former method in an extremely simple case.

Example 13.3.4. Suppose that Alice and Bob are using the RSA cryptosystem with the public Keys n = 15, e =5 and the secret Key d = 5. (Notice that ÿ(15) = 8 and de = 1(mod 8).) The plaintext and ciphertext units are elements of (Z/15Z)^X and will be represented by elements a₀ + 2a₁ + 4a₂ + 8a₃ with a, e {0,1}.

Then the encryption map e(a₀, a₁, a₂, a₃) = (c₀, c₁, c₂, c₃) is determined by c₀ + 2 c₁ + 4c₂ + 8c₃ = (a₀ + 2a₁ + 4a₂ + 8a₃)⁵. In view of the relations a² = a, for a_:j ϵ Z₂, this yields the polynomial representation c₀ = a₀a₁a₂a₃ + a₀a₁a₂ + a₀a₂ + a₀a₃ + a₂a₃ + a₀ + a₃

c₁ = a₀a₁a₂a₃ + a₀a₁a₂ + a₀a₁ a₃ + a₀a₂a₃ + a₀a₁ + a₁ + a₂ + a₃

c₂ = a₁a₂a₃ + a₀a₁ + a₁a₂ + a₁a₃ + a₁ + a₂

c₃ = a₀a₁a₂a₃ + a₀a₁a₂ + a₁a₂ a₃ + a₀a₁ + a₀a₂ + a₀a₃ + a₂a₃ + a₃.

For instance, if Eve intercepts the ciphertext bits (c₀, c₁, c₂, c₃) = (1,1,0,0), she can now compute a Gröbner basis of the ideal (f_j(a₀, a₁, a₂, a₃) - c | i = 0,1, 2,3} where the polynomials f_i correspond to the right-hand sides above. The result is G = {a₀ - 1, a₁ - 1, a₂, a₃}. This corresponds to the fact that the plaintext a₀ + 2a₁ + 4a₂ + 8a₃ = 3 encrypts to the given ciphertext.

At the heart of these algebraic attacks lies the problem of solving a large system of polynomial equations over a finite field K, where we usually have K = Z₂. Letf₁,..., f_s ϵ K[x₁,..., x_n] be the polynomials which define the polynomial system

Each solution of the polynomial system (S) satisfies every equation of the form g₁/₁ + · + g_s/_s = Owhere g_v..., g_s ϵ K[x₁,.. .,x_n] are arbitrary polynomials. Inotherwords, each solution of (S) is a zero of the polynomial ideal I = (/₁,...,/_s). The set of all zeros of I is called the zero set of I and is denoted by Z(I).

Notice that we are always looking for solutions of the given polynomial systems which are defined over K, where K = F_q is a finite field. Therefore we my append the equations xf - x_{ = 0 to the system in question to make sure that the computed solution is indeed an element of K (and not of a larger finite field). These equations are also called the base field equations and the ideal (x - x₁,...,xf - x_n) is called the base field ideal.

Before we address particular methods for solving large polynomial systems over finite fields, we want to point out algorithms which can be used to describe the encryption map via polynomials. One way is of course to trace the explicit description of the encryption map and to represent each step by polynomials. For certain steps (such as S-boxes) or certain encryption maps, we can try to consider them as black box algorithms and apply the following algorithm for multivariate polynomial interpolation.

Theorem 13.3.5 (The Buchberger-Möller Algorithm). Let K be a finite field and X = |(p₁, K₁),..., (p_s, K_s)} afinite seto/pointsinKⁿ xK^e. Assume that the elementsp_i ϵ Kⁿ are plaintext units and the elements K_{ ϵ K^l are Keys o/a given cryptosystem. For i = 1,..., s, let (c_i1,..., c_im) ϵ K^m be the ciphertext unit obtained by encryptingPj using the Key Kj.

Let Q be the polynomial ring Q = K[x₁,..., x_n, y₁,..., y_e] and leto be a term ordering on Q. Consider the/ollowing sequence o/instructions.

(1)  Letg = 0, O = 0,S = 0,L = {1}, and M = (mj a matrix having initially s columns and 0 rows.

(2)  I/L = 0 then continue with step (6). Otherwise, let t = min_o (L).

(3)  Compute eval(t) = (t(p₁, K₁),..., t(p_s, K_s)) and row reduce this vector against the rows o/M. The result is o/the/orm

(v1,..., Vs) = eval(t) - £ ai • (m_iv..., m_fe) i

with a_t ϵ K.

(4)  I/ (v₁,..., v_s) = 0 then append the polynomial t - a^j to G where sj is the i-th element o/S. Delete all multiples o/t in L and continue with step (2).

(5)  Now let (v₁,..., v_s) = 0. Append (v₁,..., v_s) as a new row to M, append t - a^j to S, append t to O, and append to L all elements o/the set {x₁t,..., x_nt, y₁t,..., y_et} which are not in L or in Lt_o (G). Then continue with step (2).

(6)  Using row operations, trans/orm M into a diagonal matrix. Mimick these row operations on the elements o/S.

(7)  Forj = 1,...,m, let/j = c^j where sj is the i-th element o/S. Return (/₁,... ,/_m) and G and stop.

This is an algorithm which computes a tuple o/polynomials (/₁,... ,/_m) ϵ Q^m such that cj = /j(pi, Kj) /ori = 1,...,sandj = 1,...,m, as well as a set o/polynomials G c Qwhich is a o-Gröbner basis of the vanishing ideal

I(X) = {g ϵ Q | g(p_t, Kj) = 0 /ori = 1,..., s}.

A proof of this theorem is contained in [KR2], Section 6.3. Given a cryptosystem whose encryption map we can apply to individual plaintext units and Keys, the BuchbergerMöller algorithm can be used to construct a polynomial map which correctly represents the encryption map for many (or even all) inputs. A further, common way to apply the theorem is to determine polynomial representations of S-Boxes in symmetric ciphers.

13.3.1 The Gröbner Basis Attack

Above we showed that breaking many types of cryptosystems can be reduced to solving large systems of polynomial equations over finite fields. For a long time, this had been considered an utterly impossible task. The situation changed when J.-C. Faugere broke the HFE Challenge in [Fau] using a Gröbner basis computation. Let us outline the general method.

Let K be a finite field, let P = K[x₁,.. .,x_n], and let f₁, ·, f_s ϵ P be polynomials defining a system of equations

/1(x1,...,x„) = 0

(S)

/s(x!,...,x„) = 0.

We form the polynomial ideal I = (/₁,...,/_s, -x₁,..., xf -x_n) where q = #K. Our task is to find the zero set

Z(I) = {(a1,..., a_n) ϵ Kⁿ | /(a1,..., a„) = 0 for all/ ϵ I}.

To solve this task, it is sufficient to compute any Gröbner basis of the ideal I. Then there is an efficient algorithm, called the FGLM Algorithm (see [FGLM] or [DE], Section 2.2.4), to compute the reduced Gröbner basis of I with respect to the lexicographic term ordering o = Lex. Using a linear coordinate transformation, we can then bring I into normal x_n-position, that is we can make sure that the last coordinates of the points of Z(I) are pairwise distinct (see [KR1], Section 3.7). Finally, we are in the setting of the Shape Lemma (cf. [KR1], Theorem 3.7.25) which says that the reduced Lex-Gröbner basis G of I has the following shape:

G = x - g!(x„), ..., x„_1 - g„_1(x„), g„(x„)}

By factoring g_n(x_n), it is then easy to read off its zeros, and substituting these into the other polynomials of G reveals the zeros of I.

Using the following remark, many of these steps can be simplified in practice.

Remark 13.3.6. When we carry out an algebraic attack and search for the secret Key, the polynomial system (S) has frequently a unique solution. In this case every reduced Gröbner basis G of I is of the form G = {x₁ - a₁,...,x_n - a_n} where (a₁,..., a_n) ϵ Kⁿ is the unique solution of (S).

Our next example represents the first important case of a successful Gröbner basis attack.

Example 13.3.7. (The HFE Challenge). Let K be a finite field having q = 2” elements. The encryption function of the HFE cryptosystem can be described as a composition e = S°F°T : K —> K where S, T areinvertiblelinearmapsandF can be identified (via an identification P₂n s Z2,) with a polynomial map/ : ^2 —> ^2 given by/(x₁, ...,x_n) = (q₁(x₁,..., x_n),..., q_n(x₁,..., x_n)) with quadratic polynomials q_t €Z₂ [x₁,..., x_n].

Then the secret Key of HFE is the triple (S, F, T) and the public Key is the tuple of polynomials (p₁,... ,p_n) with p_; ϵ Z₂[x₁,.. .,x_n] representing the encryption map S ° F ° T as above. To break this system, it is clearly sufficient to solve the set of polynomial equations p_i(x₁,..., x_n) = c_{ for i = 1,..., n, where c_{ is the i-th bit of the ciphertext.

In [Fau], J.-C. Faugere carried out this Gröbner basis attack via an improved version of Buchberger’s Algorithm, called the F5-Algorithm, to break the first HFE Challenge with n = 80.

13.3.2 The Integer Programming Attack

In this subsection we will restrict our attention to algebraic attacks based on polynomial systems defined over Z₂. Although the generalization to other finite base fields is straightforward, we want to concentrate on the fundamental principles in the most important case. The task of solving a polynomial system (S) withf₁,..., f_s €Z₂ [x₁,..., x_n] can be rephrased as follows: Find a tuple (a₁,..., σ_n) ϵ {0,1}ⁿ such that

F₁(a₁,...,a_n) = 0 (mod 2)

F_s(a₁,...,a_n) = 0 (mod 2)

where F_j ϵ Z[x₁,..., x_n] is the canonical representative off_j. Thus we are looking for an integer solution (a₁,..., a_n) of this system which satisfies 0 < a_j < 1. This formulation suggests to linearise the system and to apply an Integer Programming (IP) algorithm

for finding a solution satisfying the stated bounds. The following proposition turns this idea into an effective algorithm.

Proposition 13.3.8 (The Integer Programming Attack). Letf₁,...,f_s ϵ P = Z₂[x₁, ...,x_n]. Then the following instructions define an algorithm which computes a tuple (a₁,...,a_n) ϵ {0,1}ⁿ which defines a zero of the polynomial ideal I = (f₁,... ,f_m, xf +

^x1^,...^,xf + ^xn^}.

(1)  Reduce f₁,...,f_s modulo the field equations, that is, make their terms squarefree. For i = 1,..., s, let T be the set of terms of degree > 2 in f_j and s_j the number of terms inf.

(2)  For i = 1,..., s, introduce a new indeterminate K_j and write down the linear inequality Kj : Kj < Lsj/2J.

(3)  For every tj ϵ T_j, introduce a new indeterminate y_jj. For i = 1,..., s, write f = £_;- tj +

I where the sum extends over all j such that tj ϵ T_j and where I, ϵ P_s1. Form the linear equation F_j: £_;- y_jj + I - 2 K_j = 0.

(4)  For i ϵ {1,..., s} and tj ϵ Tj, write tj = x^ • • • x^ with 1 < j₁ < · < j_r < n. Form the linear inequalities Y_jj: y_jj - x_j < 0 and Z_jj : -y_jj + x^ + · + x^ - r +1 < 0.

(5)  For all i €{1,..., s}, letX_j: x_j < 1.

(6)  Choose a linear polynomial c ϵ Q[x_;-, y_jj, K_j] and use an IP solver to find a tuple of natural numbers (a_p bj, c_j) which solves the system of linear equations and inequalities {K,, F_j, Y_jj, Z_jj, X} and minimizes C.

(7)  Return (a₁,...,a_n) and stop.

Proof. Since we are looking for natural numbers a¡ for which X_t holds, we have a¡ e {0,1}. Similarly, we have by e {0,1} by X¡ and Y¡_¡. Moreover, if t¡ e T¡ and if one of the numbers a_;1,..., a¡ is zero then Yy implies by = 0. On the other hand, if a_;1 = · = a_jr = 1 then Z¡¡ implies by > 1. Altogether, this means that by equals aj • • • a_jr, the value of t¡ at (a₁,..., a_n).

Next it follows from F¡ that f_i(a₁,..., a_n) = 2 k¡ is an even number, and K¡ is nothing but the trivial bound for k¡ implied by the number of terms of f¡. In this way the solutions of the IP problem correspond uniquely to the tuples (a₁,..., a_n) e {0,1}ⁿ which satisfy the above reformulation of the given polynomial system. □

In this proposition we have not taken any advantage of the possibility to choose the cost function C. Obviously, the number of additional indeterminates y¡¡ (and K¡)wehave to introduce depends on the sparsity of the system (S). For systems with few quadratic or higher degree terms, even a straightforward, non-optimized implementation yields satisfactory results, as our next example shows.

Example 13.3.9. Given the CTC (“Courtois Toy Cipher”) cryptosystem introduced in [Cou] and a plaintext-ciphertext pair, we construct an overdetermined algebraic system of equations in terms of the indeterminates representing Key bits and certain intermediate quantities. The task is to solve the system for the Key bits. The size of the system depends mainly on two parameters: the number b of simultaneous S-boxes and the number N of encryption rounds used.

For instance, in the case b = 3 and N = 4 we have to solve a polynomial system having 153 indeterminates, 285 equations, and 180 non-linear terms. Using a standard PC, the public domain IP solver GLPK, and the proposition, this system can be solved in less than a minute.

13.3.3 The SAT Attack

In this subsection we continue to work over the field K = Z₂. In order to solve the polynomial system (S), we proceed as follows:

(1)  Linearise the system by introducing a new indeterminate for each term occurring in one of the polynomials.

(2)  Having written a polynomial as a sum of indeterminates, introduce new indeterminates to cut it after a certain number of terms. (This number is called the cutting number.)

(3)  Convert the reduced sums into their logical equivalents using a CNF conversion.

Here CNF means conjunctive normal form and represents a set of propositional logic clauses of a certain type. Such sets of CNF clauses can be solved very efficiently using so-called SAT solvers. Therefore the transformation to a problem in logic is currently the fastest and most powerful way to solve polynomial systems over Z₂.

To explain this technique in more detail, we start by elaborating the transformation of a polynomial equation into its logical equivalent. Let M = {X₁,...,X_n} be a set of boolean variables (atomic formulas), and let M be the set of all (propositional) logical formulas that can be constructed from them, that is all formulas involving the operations -, A, and v.

Definition 13.3.10. Let f ϵ Z₂[x₁,.. .,x_n]. A logical formula F ϵ ^M is called a logical representation of f if fy_σ(f) = f(a₁,..., a_n) + 1 for every σ = (a₁,..., a_n) ϵ Zf. Here $_σ denotes the boolean value of F at the tuple of boolean values σ where 1 = true and 0 = false.

The following lemma provides the central step for the logical conversion process.

Lemma 13.3.11. Letf ϵ Z₂ [x₁,..., x_n, y] be of the form f = l₁ ·l_s + y, where 1 < s < n and I ϵ {•, x_j + 1} for i = 1,..., s. We define formulas L_j = X_j if I = x_j and L_j = -X if 1 = x_j + 1. Then

F = (-Y v L₁) A · A (-Y v L_s) A (Y v^L₁ v · v -L_s)

is a logical representation off. Notice thatF is in conjunctive normal form (CNF) and has s +1 clauses.

Proof. Let σ = (a₁,..., a_n, b) ϵ Zf⁺¹. By induction on s, we show $_σ(f) = f(a) + 1. In the case s = 1 we have f = x₁ + y + c with c ϵ {0,1} and F = (-Y v L₁) A (Y v -’L₁) where L₁ = X₁ if c = 0 and L₁ = -X₁ if c = 1. The claim $_σ(f) = f (a) + 1 follows easily with the help of a truth table.

Now we prove the inductive step, assuming that the claim has been shown for s -1 factors I, that is forf = l₁ · l_s-1 and the corresponding formula F’. To begin with, we assume that l_s = x_s and distinguish two sub-cases.

(1)  If a_s = 0, we have $_σ(f) = $_σ(-Y v L₁) A · A (-Y v L_s-1) a — = $_b(-Y) and f (a) = b. This shows $_σ(f) = f (a) + 1.

(2)  If a_s = 1, we have f(a) = f(a). Using $_σ(L_s) = 1, we obtain

$a(f) = 0a(-Y v L1) A · A (-Y v Ls_1) A (Y VL1 v^ • •v -.Ls_1) = $„(?)• Hence the inductive hypothesis yields $_σ(f) = $_σ(F’) = f(a) + 1 = f(a) + 1.

In the case l_s = x_s + 1, the proof proceeds in exactly the same way. □

Using this lemma, we define a standard conversion strategy for f ϵ Z₂ [x₁,..., x_n] as follows. Choose a cutting number l> 3. For each non-linear term t appearing in f, introduce a new indeterminate y and a new boolean variable Y. Substitute y for t in f and append the clause corresponding to t + y in the lemma to the set of clauses.

After f has been linearised, choose a polynomial g consisting of <1-1 terms off, introduce a new indeterminate z, replace f by f - g + z and collect the polynomial g + z in a set L. Repeat this step until all of f has been cut to short sums of terms.

Finally, use the fact that the logical representation of g + z is -G o Z repeatedly to transform L into a set of CNF clauses.

Let us apply this transformation to an actual example polynomial.

Example 13.3.12. Let f = x₁x₂ + x₂x₃ + x₁ + x₂ + 1 ϵ Z₂[x₁,x₂,x₃]. We convert f into a set of CNF clauses as follows. First we let y₁ = x₁x₂ and start with the corresponding clauses L = {-Y₁ v X₁, ->Y₁ v X₂, Y₁ v ->X₁ v -X₂}. Then we set y₂ = x₂x₃ and append the analogous three clauses to L.

Now we have f = y₁ + y₂ + x₁ + x₂ + 1 and choose I = 3. Lettingg₁ = z₁ + y₁ + y₂, we have corresponding clauses G₁ = {-Z₁ v Y₁ v Y₂, Z₁ v->Y₁ v Y₂, Z₁ v Y₁ v->Y₂, -Z₁ v-iY₁ v-iY₂}. Similarly, the polynomials g₂ = z₂ + x₁ + x₂ leads to a set of four clauses G₂ and f = z₁ + z₂ + 1 corresponds to F = {-Z₁v₂, Z₁ v ->Z₂}.

Altogether, the standard CNF conversion of f consists of the 16 clauses in L u G₁ u G₂ u F.

The application of state-of-the-art SAT solvers now allows us to solve very big polynomial systems arising from algebraic attacks. Here is a case in point.

Example 13.3.13. In the CTC family of cryptosystems (see [Cou]), we choose b = 6 simultaneous SBoxes and N = 6 encryption rounds. A straightforward algebraic attack yields a polynomial system consisting of 612 quadratic equations in 468 indetermi- nates over the field Z₂. The above transformation strategy converts this system to a set of 5065 propositional logical clauses in 937 boolean variables. Standard SAT solvers such as CryptoMiniSat solve this SAT instance in a few seconds on a standard PC.

With this example we end our excursion into algebraic attacks. For the interested reader, we suggest to consult [Kre] for further variants.

13.4  Exercises

13.1  Prove that the orderings <_lex and <_drl defined in Example 13.1.3 are indeed term orderings.

13.2  Define an ordering relation <_rlex on Tⁿ by letting t = x”¹ ·x”“ <_rlex t = x1¹ ·x”“ if and only if the last non-zero component of (a₁ - fi₁,...,a_n - fi_n) is negative. Show that this reverse lexicographic ordering is a multiplicative ordering relation, but not a well-ordering. How are the indeterminates ordered ^by <rlex?

13.3  Let σ be a term ordering on Tⁿ, and let f ϵ K[x₁, ...,x_n] {0}. Prove that the leading term ideal of the principal ideal f} is generated by Lt_σ f).

13.4  Using the term ordering σ = drl, show that the following sets of polynomials are σ-Gröbner bases of the ideals they generate.

(a)  G₁ = {x² - 1, xy - 1, x - y, y² - 1} in K[x, y] (see Example 13.1.9)

(b)  G₂ = {y² - x, z³ - x} in K[x, y, z]

(c)  G₃ = {x² - y², xy² - z³, y⁴ - xz³} in K[x,y,z]

13.5  Generalize Example 13.2.1 to a Graph-p-Colouring Cryptosystem, wherep > 2 is a prime. Describe a suitable polynomial ring and the polynomials which form Alice’s public Key.

13.6  Let K be a field which contains three solutions of x³ = 1, i.e., three cubic roots of unity. Suppose that these cubic roots of unity represent three colours. Define a suitable ideal in a polynomial ring K[x₁, ...,x_n] such that 3-colourings of a graph r = (V, E) correspond uniquely to zeros of this ideal.

13.7  Given a graph r = (V, E), a perfect code in r is a subset S c V such that every vertex of r is in S or joined to precisely one element of S by an edge. For every v ϵ V, let N_v be the neighbourhood of v, i.e., the set consisting of v and all vertices of r which are joined to v by an edge. The problem of finding a perfect code in r is Known to be NP-complete.

(a)  Let V = {v₁,..., v_r}, andletP = Z₂[x₁ ,...,x_n]. For i = 1,..., r,welet f_j = 1 - Z;e_N x_;-,andifdist_r(v_;-, v_k) < 2, we letg_jk = xjx_k. Show that the polynomials f gj_k generate an ideal whose zeros correspond uniquely to perfect codes inr.

(b)  Using (a), construct an instance of the Polly Cracker Cryptosystem whose security depends on the Graph Perfect Code search problem in r.

13.8  Suppose that Alice and Bob are using the RSA cryptosystem with the public Keys n = 77 and e = 11, and the secret Key d = 11. We represent an element c₀ + 2c₁ + 4c₂ + 8c₃ + 16c₄ + 32c₅ + 64c₆ in Z₇₇ with c_j ϵ {0,1} by the tuple (co,...,c6)inZf.

(a)  Compute polynomials in Z₂[x₀,...,x₆] which represent the encryption map e : —> Zf.

(b)  Decrypt the ciphertext (0,1,1,1,0,1,0) by solving the corresponding polynomial system via a Gröbner basis calculation.