ńņš. 12 |

Ā© 2009 by Taylor and Francis Group, LLC

320 Algorithmic Cryptanalysis

Together with B ā— and assuming that vectors are represented by rows, Gram-

Schmidt algorithm computes a lower triangular matrix M, with 1s on its

diagonal, such that B = M B ā— . Equivalently, this means that for any index

j, we have:

jā’1

bā— mj,i bā— .

bj = + (10.11)

j i

i=1

Gram-Schmidt orthogonalization is given in pseudo-code as Algorithm 10.3.

The algorithm is illustrated in dimension 3 in Figure 10.5.

The output of the Gram-Schmidt algorithm also allows to write the Gram

matrix and the determinant of a lattice in a convenient form, indeed:

B Ā· B = M Ā· B ā— Ā· B ā— Ā· M. (10.12)

Moreover, B ā— Ā· B ā— is a diagonal matrix with diagonal entries equal to

2

bā— . Since the determinant of the square matrix M is 1, this shows that the

i

determinant of a lattice can be computed as the product of the norms of the

vectors in any Gram-Schmidt orthogonal basis.

Algorithm 10.3 Gram-Schmidt algorithm

Require: Initial basis of the vector space B = (b1 , b2 , Ā· Ā· Ā· , bn )

Create basis B ā— and transformation matrix M

for i from 1 to n do

Let bā— āā’ bi

i

for j from 1 to i ā’ 1 do

(bi |bā— )

j

Let mi,j āā’ 2

bā—

j

Let bā— āā’ bā— ā’ mi,j bā—

i i j

end for

end for

Output B ā— and M

10.3.2 Lenstra-Lenstra-LovĀ“sz algorithm

a

The algorithm of Lenstra-Lenstra-LovĀ“sz, also called the LLL or L3 algo-

a

rithm is obtained by combining Gauss reduction in dimension two, together

with Gram-Schmidt orthogonalization. The basic principle consists of apply-

ing Gauss reduction to a sequence of projected sublattices of dimension 2.

More precisely, it considers the lattice generated by the orthogonal projection

of two consecutive vectors bi and bi+1 on the vector subspace generated by the

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 321

bā—

3

b3

b1

b2

ā—

Figure 10.5: Computing b3 from b3

previous vectors (b1 , Ā· Ā· Ā· , biā’1 ) and applies one iteration of t-Gauss reduction1

to this projected lattice. In order to also modify the high dimension lattice,

all swap and translation operations are pulled back from the projected space

and applied to the vectors bi and bi+1 themselves. In addition, these vectors

may also be changed by adding to them some vector from the sublattice with

basis (b1 , Ā· Ā· Ā· , biā’1 ). The goal of this operation is to make sure that bi is not

ā—

too far from the corresponding projected vector bi . Once again, we illustrate

this in dimension 3 in Figure 10.6

Algorithm 10.4 gives a description of the L3 algorithm, using Algorithm 10.5

as a subroutine for length reduction. This subroutine is called RED within

Algorithm 10.4. In this description, all coordinates in B are integers and all

numbers in B ā— and M are represented as rationals.

To better understand this algorithm, let us detail the conditions of the

translation and exchange steps within the L3 algorithm. The goal of transla-

tions is to modify the oļ¬-diagonal coeļ¬cients in the triangular matrix M and

reduce them in absolute value below 1/2. In other words, these translations

ā—

are used to make sure that each bk is not too far from the corresponding bk

and āalmost orthogonalā to its predecessors. This is achieved by calling subal-

gorithm RED to translate a vector bi along bj (with j < i). This subalgorithm

also modiļ¬es M to reļ¬‚ect this translation. The updates performed on M are

1 Theuse of t-Gauss ensures polynomial time behavior. Note that, the parameter t and the

parameter Ī“ of LLL-reduction are related by Ī“ = 1/t.

Ā© 2009 by Taylor and Francis Group, LLC

322 Algorithmic Cryptanalysis

Algorithm 10.4 LLL algorithm using rationals

Require: Initial basis of an integer lattice B = (b1 , b2 , Ā· Ā· Ā· , bn )

Require: Parameter 1/4 < Ī“ ā¤ 1

Compute B ā— and M using Gram-Schmidt Algorithm 10.3

for i from 1 to n do

Let Li āā’ bā— 2 i

end for

Erase B ā—

Let k āā’ 2

while k ā¤ n do

Apply length reduction RED(k, k ā’ 1)

if (Lk + m2 k,kā’1 Lkā’1 ) ā„ Ī“ Lkā’1 then

for l from k ā’ 2 downto 1 do

Apply length reduction RED(k, l)

end for

Increment k

else

Let mm āā’ mk,kā’1

Let LL āā’ Lk + mm2 Lkā’1

Let mk,kā’1 āā’ mmLkā’1 /LL

Let Lk āā’ Lkā’1 Lk /LL

Let Lkā’1 āā’ LL

Exchange bk and bkā’1

for l from 1 to k ā’ 2 do

Let Āµ āā’ mi,k

Let mi,k āā’ mi,kā’1 ā’ Āµmm

Let mi,kā’1 āā’ Āµ + mk,kā’1 mi,k

end for

if k > 2 then

Decrement k

end if

end if

end while

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 323

bā—

3

b3

b3

b1

b2

Figure 10.6: An elementary reduction step of L3 in dimension 3

Algorithm 10.5 Length reduction subalgorithm RED(i, j)

Require: Current lattice basis B and matrix M

Require: Integer i and j, where bi is to be reduced by bj

if |mi,j | > 1/2 then

Let r āā’ mi,j

Let bi āā’ bi ā’ rbj

mi,j āā’ mi,j ā’ r

for w from 1 to j ā’ 1 do

Let mi,w āā’ mi,w ā’ rmj,w

end for

end if

Ā© 2009 by Taylor and Francis Group, LLC

324 Algorithmic Cryptanalysis

easy to follow and detailed in subalgorithm RED. Note that the orthogonalized

vector bā— remains unchanged during a call to RED.

i

The exchange steps are used to simultaneously reduce the norm of bā— and

kā’1

ā— ā—

increase the norm of bk . Note that B itself is not used during the algorithm

2

and that the knowledge of the squared norms bā— denoted by Li in the

i

algorithm and of the lower diagonal matrix M suļ¬ces. During exchange

steps, the values of the norms and the matrix M also need to be updated.

Since these updates are more complicated than during translation steps, we

now detail the mathematics behind them.

Given a pair of vectors bi and bi+1 , let us denote by u and v their respective

projections orthogonally the subspace spanned by (b1 , Ā· Ā· Ā· , biā’1 ). In the spe-

cial case i = 1, we have u = b1 and v = b2 . We have the following identities

before the exchange:

(v|u) (v|u)

bā— = bā—

i+1 = v ā’

u, u, mi+1,i = ,

i u2 u2

(bk |bā— )

(bk |bā— )

ā k > i + 1 : mk,i = i+1

, mk,i+1 = .

i

2 2

bā— bā—

i i+1

(10.13)

and after the exchange:

(v|u) (v|u)

Ėā— = Ėā—

bi+1 = u ā’

bi v, v, mi+1,i =

Ė ,

v2 v2

(bk |Ėā— )

(bk |Ėā— ) bi+1

bi

ā k > i + 1 : mk,i =

Ė , mk,i+1 =

Ė 2.

Ėā— 2 Ėā—

b b

i i+1

(10.14)

Moreover, since the determinant of a lattice is an invariant that does not

depend on the chosen basis, we necessarily have:

Ėā— Ā· Ėā— = bā— Ā· bā—

2 2 2 2

bi bi+1 (10.15)

i i+1

As a consequence, we derive the following update formulas:

bā— bā—

2 2

Ėā— Ėā—

= bā— ā—2

2 2

+ m2 2 i i+1

bi i+1,i bi , bi+1 = ,

i+1 Ėā— 2

bi

bā— 2

āk < i : mi+1,k = mi,k ,

Ė mi+1,i =

Ė mi+1,i ,

i

Ėā— 2

bi

mi,k = mi+1,k ,

Ė

ā k > i + 1 : mk,i+1 = mk,i ā’ mi+1,i mk,i+1 ,

Ė

mk,i = mk,i+1 + mi+1,i mk,i+1 .

Ė Ė Ė

(10.16)

3

Looking at the conditions enforced during L reductions, it is clear that

this algorithm yields a LLL-reduced basis of the input lattice. In addition, L3

is a polynomial time algorithm and LLL-reduced bases are reasonably good.

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 325

The L3 lattice reduction can also, with a minor modiļ¬cation, starting from

a family of vectors that generates a lattice, construct a reduced basis for this

lattice. This modiļ¬ed algorithm simply removes any zero vectors that appear

among the vectors bi during the computations.

Complexity of the L3 algorithm

In order to bound the complexity of the L3 algorithm, we are going to

rely on the notion of determinant described in Section 10.1. Given a basis

(b1 , Ā· Ā· Ā· , bn ) of a lattice L, we can construct a family of sublattices L1 , . . . , Ln ,

where each lattice Li is generated by an initial segment of the given basis of L:

(b1 , Ā· Ā· Ā· , bi ). We let di denote the determinant det(Li ) of the i-th sublattice.

At each step of the L3 algorithm, the values of di for the current basis may

change. More precisely, we can study the possible behavior of these values

during translations and during exchanges. During translations, we see that a

single vector is changed by addition of multiples of previous vectors. Clearly,

this operation does not modify any of the sublattices and only changes the

representations of these lattices. During exchanges, the situation is slightly

more complicated. Assume that bk and bkā’1 are exchanged, then we see that

none of the sublattices Li for i < k ā’ 1 are modiļ¬ed. Similarly, none of the

sublattices Li for i ā„ k are modiļ¬ed, since up to order the basis of each is

preserved. However, the sublattice Lkā’1 is modiļ¬ed. Thus, the determinant

dkā’1 can change. Since this determinant is the product of the norms of the

ā— ā—

vectors bi up to k ā’ 1 and since bk1 decreases by a factor at least Ī“ ā’1 , so

Ė

does dkā’1 . More precisely, if dkā’1 denotes the new value after the exchange,

we have:

Ė

dkā’1 ā¤ Ī“ Ā· dkā’1 . (10.17)

Thus, during each exchange of the L3 algorithm, one value of di goes down,

while the others are unchanged. During all other operations in L3 , all values

di s are left unchanged. As a consequence, the product of all di s

n

D= di (10.18)

i=1

is decreasing throughout the L3 algorithm. Moreover, whenever it changes,

it is divided by at least by Ī“ ā’1 . In addition, D2 is a non-zero integer, thus

D must remain greater than 1. Letting DInit denote the initial value of D,

we see that the L3 algorithm performs at most log(DInit )/ log(t) exchanges.

This allows to bound the number of arithmetic operations performed during

L3 ; however, it does not suļ¬ce to compute the running time of L3 . We also

need to analyze the size of the numbers that occur throughout the algorithm.

In fact, the real diļ¬culty is to check that the denominators of fractions remain

small enough. With the original L3 algorithm, they are bounded by the largest

value among the squared determinants d2 . As a consequence, it is possible to

i

show that, using ordinary multiplication, the complexity of L3 reduction for

Ā© 2009 by Taylor and Francis Group, LLC

326 Algorithmic Cryptanalysis

an integer lattice of rank r in dimension n, with all entries in the basis vectors

bounded by B is O(nr5 log3 (B)).

This complexity can be improved by using ļ¬‚oating point numbers instead

of rationals, within the L3 algorithm, keeping only the integer coordinates

of basis vectors in exact form. A side eļ¬ect of this change is that we can

no longer round numbers to their nearest integer without mistakes and that

we need to relax the length reduction condition given by Equation (10.9). It

suļ¬ces to replace the constant 1/2 in this algorithm by a slightly larger con-

stant, such as 0.501 or something similar. From a theoretical point-of-view the

fastest algorithm is described in [NS05] and has complexity O(nr4 log2 (B)).

In practice, ļ¬‚oating point numbers with ļ¬xed precision are often used; how-

ever, in bad cases the round-oļ¬ errors prevent the algorithm from terminating.

Many heuristics have been proposed to avoid this bad behavior, for example

see [SE94], but, despite their good performances in many cases, they some-

times fail.

Properties of LLL-reduced bases

Given a LLL-reduced basis for a lattice L, we ļ¬rst remark that any non-zero

vector of L has its norm at least as large as the norm of the shortest vector

bā— in the orthogonal basis. Due to LovĀ“sz conditions, we ļ¬nd:

a

i

1

2 2

bā— ā„ bā— Ī“ā’ . (10.19)

i+1 i

4

If Ī»1 denotes the ļ¬rst minimum of L, it is greater than the norm of the shortest

bā— . It follows that:

i

(nā’1)/2

1

Ī»1 ā„ Ī“ ā’ b1 . (10.20)

4

As a consequence, the ļ¬rst vector of a LLL-reduced basis is not too large

when compared to the ļ¬rst lattice minimum. This relation is often used in

the special case Ī“ = 3/4, yielding:

b1 ā¤ 2(nā’1)/2 Ī»1 . (10.21)

Another very useful inequality related the size of b1 with the determinant

of the lattice. Since the determinant is equal to the product of the norms of

all bā— and multiplying together the equations:

i

(iā’1)/2

1

bā— ā„ Ī“ā’ b1 , (10.22)

i

4

we ļ¬nd:

n(nā’1)/4

1 n

det(L) ā„ Ī“ ā’ b1 . (10.23)

4

Taking the n-th root and letting Ī“ = 3/4, we obtain:

b1 ā¤ 2(nā’1)/4 det(L)1/n . (10.24)

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 327

10.4 Shortest vectors and improved lattice reduction

Once we have computed a LLL-reduced basis for a lattice L, we already have

obtained some reasonably short vectors. However, we might wish to obtain

stronger results. One typical problem is to determine the ļ¬rst minimum Ī»1 (L)

of the lattice and ļ¬nd a non-zero vector achieving this minimal length. Note

that we cannot use a straightforward brute force approach to ļ¬nd such a

shortest vector. Indeed, the set of lattice vectors is inļ¬nite and we cannot

directly enumerate it. Instead, we ļ¬rst need to analyze the properties the

lattice and determine a ļ¬nite set of candidates that contains the shortest

vector. This is the basic idea of enumeration algorithms [Kan83].

10.4.1 Enumeration algorithms for the shortest vector

Assume that we are given a basis B for a lattice L of rank r. Then, for

any r-uples Ī± of integers, we can compute a vector V (Ī±) in L by the following

formula:

r

V (Ī±) = Ī± i bi , (10.25)

i=1

where the vectors bi are in the basis B. Can we determine a ļ¬nite set SB

such that the shortest non-zero vector in L is equal to V (Ī±) for some Ī± in

SB ? Kannan showed in [Kan83] that such a ļ¬nite set exists and can be used

to construct an algorithm for ļ¬nding the shortest vector.

As before in this chapter, we denote by B ā— the Gram-Schmidt orthogo-

nalized basis corresponding to B and by bā— the vectors from B ā— . Let Ī± by

i

a non-zero r-uple as above such that Ī±k is the last non-zero component in

Ī±, i.e., for any integer i > k, we have Ī±i = 0. Then, we have the following

identity:

k kā’1

Ī²i bā— + Ī±k bā— ,

V (Ī±) = Ī±i bi = (10.26)

i k

i=1 i=1

for some r ā’ 1-uple Ī². Since B ā— is an orthogonal basis, this implies that the

norm of V (Ī±) is greater than Ī±k times the norm of bā— . As a consequence, we

k

know that if Ī± is such that V (Ī±) is the shortest non-zero vector in L then for

any vector v in L we have:

v

|Ī±k | ā¤ . (10.27)

bā—

k

As a consequence, we have shown that there are only ļ¬nitely many possibilities

for the last non-zero integer in Ī±. Note that the quality of bound given by

Equation (10.27) varies depending on the vector v we choose and on the norm

of bā— . Using a LLL-reduced basis in this bound is a good idea because it gives

k

Ā© 2009 by Taylor and Francis Group, LLC

328 Algorithmic Cryptanalysis

two improvements. First, the ļ¬rst vector in the reduced basis is quite small

and is a good candidate for v. Second, thanks to Equation (10.19), the norm

of bā— in a reduced basis is not too large. More precisely, with a L3 reduced

k

basis, with parameter t, we can derive the following bound for Ī±k :

kā’1

1

2

|Ī±k | ā¤ Ī“ā’ (10.28)

4

It remains to see that the other component in Ī± can similarly be bounded

when V (Ī±) is the shortest non-zero vector in L. More precisely, substituting

Equation (10.11) into Equation (10.26) and letting Ī²k = Ī±k we may remark

that for a L3 reduced basis, we have:

k

Ī²j = Ī±j + Ī²i mi,j . (10.29)

i=j+1

This implies that:

k

k

Ī²i bā—

vā’ v

i

i=j+1

|Ī±j + Ī²i mi,j | ā¤ ā¤ . (10.30)

bā— bā—

j j

i=j+1

jā’1

Thus, for a L3 reduced basis, there are fewer than 2 Ī“ ā’ 1 values to

4

consider for Ī±j .

All in all, starting from a L3 reduced basis, it is possible to obtain the

2

shortest vector of a lattice of rank r by considering at most 2O(r ) vectors.

In addition to Kannan in [Kan83], this has also been studied by Fincke and

Pohst in [FP85] and, later, by Schnorr and Euchner in [SE94]. A completely

diļ¬erent algorithm for ļ¬nding short vectors was proposed by Ajtai, Kumar

and Sivakumar in [AKS01]. It is asymptotically much more eļ¬cient, but does

not seem to be practically competitive for the current dimensions that can be

addressed with lattice reduction.

Note that a technical diļ¬culty when programming this algorithm is that

we need to write down r level of embedded loops. Were r ļ¬xed, this would

cause no problem, but with varying values of r, we have to either write a

recursive routine or remove the recursivity by explicitly remembering a stack

of loop counters inside an array. A basic enumeration algorithm using this

second approach is listed as Algorithm 10.6. One important practical feature

of this algorithm is that whenever a new shortest vector is found, its length

is used to bound the coeļ¬cients used during the enumeration. Moreover, the

coeļ¬cients are bounded using the ļ¬rst inequality of Equation (10.30), which

is tighter than the second one.

In practice, Schnorr and Euchner propose in [SE94] to speed up the enu-

meration algorithm by changing the order in which the various possibilities

for Ī± are considered. Instead of enumerating the values at each level from the

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 329

Algorithm 10.6 A basic short vector enumeration algorithm

Require: Input L3 reduced basis B of rank r, orthogonalized B ā— and M

Require: Input round-oļ¬ error tolerance

Let array Ī±best [1 Ā· Ā· Ā· r] āā’ (1, 0, 0, Ā· Ā· Ā· , 0)

2

Let Lbest āā’ b1

Declare array Ī±[1 Ā· Ā· Ā· r + 1]

Let Ī±[r + 1] āā’ 0 {Deļ¬ned to avoid memory overļ¬‚ows}

2

Let Ī±[r] āā’ ā’ Lbest / bā— + r

Ė

Declare array L[1 Ā· Ā· Ā· r + 1]

Ė

Let L[r + 1] āā’ 0

Let t āā’ r {Initialize loop level index to outer loop}

while t ā¤ r do

if t = 0 then

r

Let c āā’ i=1 Ī±[i]bi

2

Let L āā’ c {Recompute exact squared norm}

if L < Lbest then

Let Lbest āā’ L

Let Ī±best āā’ Ī±

end if

Increment Ī±[1]

Let t āā’ 1

else

r

Let Ī² āā’ Ī±[t] + i=t+1 Ī±[i]mi,t

2

Ė Ė

Let L[t] āā’ L[t + 1] + Ī² 2 bā— {Approximate contribution to norm}

t

Ė

if L[t] < Lbest + then

if t > 1 then

r

Let Ī² āā’ i=t Ī±[i]mi,tā’1

2

Ė

Let Ī±[t ā’ 1] āā’ ā’ (Lbest ā’ L[t])/ bā— ā’Ī²

+

tā’1

end if

Decrement t {Go to next inner loop level}

else

Increment Ī±[t + 1]

Increment t {Go to next outer loop level}

end if

end if

end while

Output coordinates Ī±best of shortest vector in basis B.

Ā© 2009 by Taylor and Francis Group, LLC

330 Algorithmic Cryptanalysis

smallest to the largest possibility, they propose to use a centered approach.

For example, at the ļ¬rst level of the enumeration, i.e., when considering Ī±[r],

since the enumeration starts from the end, they enumerate the possibilities in

the order 0, 1, ā’1, 2, ā’2, . . . For inner levels, the enumeration starts from

the middle of the range of available option and proceeds outwards, alternating

on the left and right sides.

10.4.2 Using shortest vectors to improve lattice reduction

Thanks to the above enumeration algorithms for short vector, it is possible

to construct lattice bases which are more strongly reduced than L3 reduced

bases. Moreover, Kannan showed in [Kan83] that the relationship between

short vector and strong lattice reduction runs both ways. In one direction,

we can use short vectors to improve the quality of lattice basis, in the other

direction, the short vector enumeration algorithms run faster when applied to

strongly reduced basis. Using this bidirectional relationship, Kannan devised

a recursive algorithm that constructs strongly reduced basis and short vector

faster than by running the enumeration algorithm directly with a L3 reduced

basis. Recall that for a lattice of rank r, we showed in Section 10.4.1 that

2

starting from a L3 reduced basis, it suļ¬ces to enumerate 2O(r ) vectors to

ļ¬nd the shortest lattice vector. With the recursive algorithm of Kannan, the

complexity is lowered to 2O(r log r) .

This algorithm relies on the notion of Hermite-Korkine-Zolotarev or HKZ

reduced basis. A basis B of a lattice L, with orthogonalized basis B ā— such

that B = M Ā· B ā— is HKZ reduced, if and only if, the following properties are

satisļ¬ed:

1. The basis B is size-reduced, as in Equation (10.9), i.e., all oļ¬-diagonal

coeļ¬cients of M satisfy |mi,j | ā¤ 1/2.

2. The vector b1 realizes the ļ¬rst minimum Ī»1 (L).

3. The projection of the vectors b2 , Ā· Ā· Ā· , br orthogonally to b1 form an HKZ

reduced basis.

The third condition is recursive; however, it simply means that b2 is chosen

to minimize bā— and so on for the subsequent vectors. It is easy to remark

2

that an HKZ reduced basis is L3 reduced.

During Kannanā™s algorithm, we also need a slightly relaxed notion as an

intermediate computation step. We say that a basis B is quasi-HKZ reduced,

when b1 ā¤ 2 bā— and the projection of the sublattice (b2 , Ā· Ā· Ā· , br ) orthogo-

2

nally to b1 is HKZ reduced. The key point is that enumerating the shortest

vector in a lattice given a quasi-HKZ reduced basis is much more eļ¬cient

than with an L3 reduced basis. A sketch of Kannanā™s algorithm is given as

Algorithm 10.7. This algorithm uses L3 on a generating family as subroutine.

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 331

It has been thoroughly analyzed when the underlying L3 uses exact arith-

metic [HS07]. However, in practice, it is usually replaced by ļ¬‚oating point

heuristics. Due to its high time complexity, Kannanā™s algorithm for HKZ

reduction can only be used for lattices of small enough rank.

Algorithm 10.7 Kannanā™s HKZ reduction algorithm

Require: Input basis B of a lattice L

repeat

Reduce B using L3

Use HKZ reduction recursively on projected lattice (b2 , Ā· Ā· Ā· , br ) orthogo-

naly to b1 .

until b1 > bā— {Loop output of quasi-HKZ reduced basis}

2

Find bmin shortest vector in B using Algorithm 10.6.

Apply L3 on family (bmin , b1 , Ā· Ā· Ā· br ) to obtain a L3 reduced basis with bmin

As ļ¬rst vector. Put the output in B.

Use HKZ reduction recursively on projected lattice (b2 , Ā· Ā· Ā· , br ) orthogonally

to b1 .

Output HKZ reduced B, including lattice shortest vector.

10.4.2.1 Schnorrā™s block reduction

To conclude this chapter on lattice reduction, let us mention that for lattices

of large rank, where HKZ reduction is not feasible, there exists a family of

reduction algorithms introduced by Schnorr in [Sch87] called block Korkine-

Zolotarev reduction. The basic idea is to use HKZ reduction on projected

sublattices of ļ¬xed rank. Without going into the details, let us mention that

each algorithm in the family has a polynomial running time. Of course, the

degree of this polynomial grows with the size of the considered blocks. Heuris-

tic versions of this algorithm are available in some of the computer packages

cited in the preface.

10.5 Dual and orthogonal lattices

When dealing with lattice reduction in cryptography, the notions of dual

and orthogonal of a given lattice are frequently encountered. Since these two

notions are important and distinct from each other, we describe them in this

section.

Ā© 2009 by Taylor and Francis Group, LLC

332 Algorithmic Cryptanalysis

10.5.1 Dual of a lattice

Let L be a lattice of rank r in a vector space of dimension n. Consider

span(L), the vector subspace spanned by L. We ļ¬rst deļ¬ne the dual lattice

Lā— as a set:

Lā— = {u ā span(L) | ā v ā L : (u|v) ā Z} .

To check that Lā— is indeed a lattice, we need to prove that it is a discrete

subgroup of Zn . In fact, in this case, it is even a discrete subgroup of span(L).

The subgroup part is left as exercise to the reader. To prove that Lā— is a

discrete subgroup, we proceed by contradiction. If Lā— is not discrete, then

there exists a sequence of vectors ui of Lā— , whose norms tend to 0 as i tends

to inļ¬nity. Of course, this limit also holds for any equivalent norm. We now

consider (v1 , Ā· Ā· Ā· , vr ) a basis of L and the norm Ā· L deļ¬ned on span(L) by:

r

2

u = (u|vi ) .

L

i=1

Now, by deļ¬nition of Lā— , the norm of any vector in the sequence ui is a sum

of squares of integers and, thus, a non-negative integer. As a consequence,

the sequence ui L is a sequence of non-negative integers which tends to zero.

Moreover, since none of the ui is the zero vector, none of the norms ui can

be equal to zero and the norms are lower bounded by 1. This contradiction

concludes the proof.

When the lattice L has full rank, i.e., when r = n a basis for Lā— can simply

be obtained by the transpose of the inverse matrix of a basis of L. In the

general case, in order to explicitly construct a basis of the dual lattice, the

easiest is to start from a Gram-Schmidt orthogonalization of a basis of the

original lattice. Let us consider (b1 , Ā· Ā· Ā· , br ) a basis of L and (bā— , Ā· Ā· Ā· , bā— ), its

r

1

Gram-Schmidt orthogonalization.

2

We ļ¬rst remark that Ėr = bā— / bā— belongs to the dual lattice Lā— . Indeed,

b r r

2

bā—

with bi is 0 when i < r and bā— when i = r. Thus,

the scalar product of r r

decomposing any vector v in L on the given basis, we ļ¬nd that the scalar

product of v with Ėr is a integer. In truth, this integer is the coeļ¬cient of br

b

2

in the decomposition of v. Next, we consider the vector Ėā— = bā— / bā—

brā’1 rā’1 rā’1

and see that, in general, this vector does not belong to Lā— . Indeed, its scalar

products with all bi s are zeros when i < r ā’ 1 and its scalar product with

brā’1 is equal to one; however the scalar product with br is not necessarily an

integer. More precisely, using the notation of Section 10.3.1, we have:

2

(br |bā— ) = mr,rā’1 bā—

rā’1 . (10.31)

rā’1

It follows that:

(br |Ėā— ) = mr,rā’1 .

brā’1 (10.32)

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 333

Clearly, adding a multiple of bā— to Ėā— preserves the scalar product with bi

brā’1

r

for i < r and modiļ¬es the scalar product with br . In particular, if we consider

the vector Ėrā’1 = Ėā— ā’ mr,rā’1Ėr , the scalar product with br becomes 0 and

b brā’1 b

we obtain a second, linearly independent, vector in Lā— .

To construct a complete basis for Lā— , we ļ¬rst specify its Gram-Schmidt

orthogonalized basis:

bā— bā—

(Ėā— , Ā· Ā· Ā· , Ėā— ) = r 1

2,Ā·Ā·Ā· ,

br b1 . (10.33)

2

bā—

bā—

r 1

In other words, the basis for Lā— has the same orthogonalized basis as the

initial basis for L, but the order of vectors is reversed. Then, we specify the

Gram-Schmidt coeļ¬cients for the dual basis. For simplicity, it is preferable

to number the basis vectors of the dual lattice in reversed order and consider

a basis (Ėr , Ā· Ā· Ā· Ė1 ). The Gram-Schmidt coeļ¬cients of this basis are chosen as

b b

follows:

(Ėi |Ėā— )

b bj

2 = ā’mi,j .

Ėā—

bj

r

Equivalently, we simply compute Ėi as Ėā— ā’ j=i+1 mi,j Ėā— .

b bi bj

We leave as an exercise to the reader to check that by applying the same

method to compute a dual of the dual basis gives back the original basis of

the lattice L. In addition, the reader can also verify that when the initial

basis of L is L3 reduced, so is the resulting basis of the dual lattice.

10.5.2 Orthogonal of a lattice

Let L be an integer lattice in a vector space of dimension n, with rank

r < n. We deļ¬ne the orthogonal lattice Lā„ as the following subset of Zn :

Lā„ = {u ā Zn | ā v ā L : (u|v) = 0} .

It is clear that Lā„ is a subgroup of Zn and thus an integer lattice. Its

rank is equal to n ā’ r. Moreover, lattice reduction and, in particular, the L3

algorithm gives an eļ¬cient way to compute Lā„ from L. Consider the lattice

spanned by the columns of the following matrix:

k Ā· B(L)

I

where B(L) is the matrix of an L3 reduced basis of L, k is a large enough

constant and I is an n Ć— n identity matrix. After applying the L3 algorithm

to this lattice, we obtain a matrix of the form:

kĀ·U

0

ā„

B(L ) V

Ā© 2009 by Taylor and Francis Group, LLC

334 Algorithmic Cryptanalysis

where B(Lā„ ) is a L3 reduced basis of the orthogonal lattice Lā„ . This notion

of orthogonal lattice is frequently used in Chapter 13. Note that it is usually

more eļ¬cient to use linear algebra rather than lattice reduction to construct

a basis of the vector space spanned by B(Lā„ ). Moreover, by using a linear al-

gebra method that does not perform divisions, i.e., similar to Hermite normal

form computations, we can in fact obtain a basis B(Lā„ ). This is essential for

the eļ¬ciency of the algorithms presented in Chapter 13.

Ā© 2009 by Taylor and Francis Group, LLC

Lattice reduction 335

Exercises

1. Let A and N be two coprime integers. Consider the lattice L generated

by the rows of:

A1

.

N0

ā¢ Let (u, v) be any vector in this lattice with v = 0. What can you

say about u/v?

ā¢ What is the determinant of the lattice L?

ā¢ If (u, v) is the smallest vector in L, what can you say about u/v?

ā¢ Find a similar result using the continued fraction expansion of

A/N .

2h . Prove that the second vector in a Gauss reduced basis for a 2-dimensional

lattice achieves the second minimum of this lattice.

3. Consider the n dimensional lattice L generated by the identity matrix.

ā¢ What are the minima of this lattice?

ā¢ Write a program that generates random looking bases of L.

ā¢ How can you easily check that a matrix M is a basis for L?

ā¢ Experiment with an existing implementation of lattice reduction

algorithms and try to reduce random looking bases of L. When

does the lattice reduction algorithm output the identity matrix (or

a permuted copy)?

4h . Show that any lattice reduction algorithm can be modiļ¬ed to keep track

of the unimodular transform that relates the input and output matrices.

5. Reduce, by hand, with the L3 algorithm the lattice generated by:

ļ£« ļ£¶

12 3

ļ£4 5 6 ļ£ø.

7 8 10

Ā© 2009 by Taylor and Francis Group, LLC

Chapter 11

Polynomial systems and GrĀØbner

o

base computations

Thus, if we could show that solving a certain system requires at

least as much work as solving a system of simultaneous equations

in a large number of unknowns, of a complex type, then we would

have a lower bound of sorts for the work characteristic.

Claude Shannon

As shown by the above quote, written by Claude Shannon in his famous

paper [Sha49], multivariate polynomial systems of equations naturally arise

when writing down cryptanalytic problems. To illustrate this fact, let us

consider two simple examples, one coming from public key cryptography and

the other from secret key cryptography.

Factoring Writing down factoring as a multivariate system of polynomial

equations is a very simple process. Assume that N = P Q is an RSA number.

Writing P and Q in binary, we can deļ¬ne two sets p and q of unknowns over

F2 according to the following correspondence:

pi 2i , qi 2i .

P= and Q =

i i

Replacing P and Q in the equation N = P Q yields a multivariate polynomial

equation over the integers. Finding the factorization of N corresponds to

ļ¬nding a {0, 1} non-trivial solution to this equation.

In fact, it is possible to go further and rewrite this equation as a system

of equations over F2 . In order to get a reasonably simple expression, it is a

good idea to add extra variables to keep track of the computation. To give a

simple example, assume that we would like to factor 35 into two numbers of

3 bits each: P = 4p2 + 2p1 + p0 and Q = 4q2 + 2q1 + q0 . This easily yields an

equation:

16p2 q2 + 8(p1 q2 + p2 q1 ) + 4(p0 q2 + p1 q1 + p2 q0 ) + 2(p0 q1 + p1 q0 ) + p0 q0 = 35.

(11.1)

337

Ā© 2009 by Taylor and Francis Group, LLC

338 Algorithmic Cryptanalysis

To replace this equation with a system of equations over F2 , we deļ¬ne a

partial sum S = p0 Q + 2p1 Q and see that N = S + 4p2 Q. The partial sum

S can be represented as 16s4 + 8s3 + 4s2 + 2s1 + s0 . Adding two new sets of

variables c and c to deal with the carries in both additions, we ļ¬nally obtain:

s0 = p0 q0 ,

= p0 q1 ā• p1 q0

s1 c1 = p0 p1 q0 q1 ,

= c1 ā• p0 q2 ā• p1 q1 , c2 = c1 p0 q2 ā• c1 p1 q1 ā• p0 p1 q1 q2 ,

s2

= c2 ā• p1 q2 ,

s3 c3 = c2 p1 q2 ,

s4 = c3 ;

(11.2)

1 = s0 , 1 = s1 ,

0 = s2 ā• p2 q0 , c2 = s2 p2 q0 ,

0 = s3 ā• c2 ā• p2 q1 , c3 = s3 c 2 ā• s3 p2 q1 ā• c 2p2 q1 ,

0 = s4 ā• c3 ā• p2 q2 , 1 = s4 c 3 ā• s4 p2 q2 ā• c 3p2 q3 .

This is a polynomial system of multivariate equations of degree 4. This can

be generalized to express the factorization of any RSA number N as a system

of O(log(N )2 ) equations of degree 4 over F2 .

Cryptanalysis of DES We saw in Chapter 5 the bitslice description of the

DES algorithm. In this description, the S-boxes are given as logical formulas

or equivalently as polynomial expressions over F2 . Since the other compo-

nents of the DES algorithm are linear, the DES can in fact be written as a

sequence of polynomial evaluations. Thus, by substituting the plaintext and

ciphertext values he knows into these evaluations, a cryptanalyst may de-

scribe the key recovery problem of DES as a polynomial system of equations.

In order to limit the total degree of the system and preserve its sparsity, it is

convenient to introduce additional variables that represent the intermediate

values encountered in this Feistel scheme.

From these two simple examples, we see that multivariate polynomial sys-

tems of equations can be used very easily to describe many cryptanalytic

tasks. As a consequence, it is important to study whether such multivariate

systems of equations are easy to solve and to understand the key parameters

that govern the complexity of solving such systems.

11.1 General framework

ĀÆ

Throughout the rest of this chapter, K denotes an arbitrary ļ¬eld and K its

algebraic closure. As a ļ¬nal goal in this chapter, we would like to formalize

Ā© 2009 by Taylor and Francis Group, LLC

Polynomial systems and GrĀØbner base computations

o 339

the resolution of a system of m algebraic equations in n unknowns:

ļ£± ļ£¼

ļ£“ f1 (x1 , Ā· Ā· Ā· , xn ) = 0 ļ£“

ļ£² ļ£½

.

. (11.3)

.

ļ£“ ļ£“

fm (x1 , Ā· Ā· Ā· , xn ) = 0

ļ£³ ļ£¾

More precisely, we would like to determine if such a system has got solutions

and if so, whether there are ļ¬nitely or inļ¬nitely many. Finally, we would like to

compute some solutions and, when the number of solutions is ļ¬nite, possibly

list all solutions. We already know that, even when considering univariate

polynomials, the notion of roots of polynomials is a delicate one. Indeed, over

the real ļ¬eld R, similar polynomials may have distinct behaviors, for example,

x2 ā’ 1 has two roots, while x2 + 1 has none. Thankfully, this ļ¬rst diļ¬culty

vanishes when the polynomials are considered over the algebraic closure of the

real ļ¬eld, i.e., the ļ¬eld C of complex numbers. There, both polynomials have

two roots. For this reason, we systematically consider roots of an algebraic

ĀÆ

system as in Equation (11.3) as deļ¬ned over the algebraic closure K.

Looking at our system of equations, intuition says that we should expect

a ļ¬nite number of solutions when the number of equations is equal to the

number of unknowns, m = n. With more unknowns than equations, there will

be degrees of freedom left and we expect an inļ¬nite number of solutions. With

more equations than unknowns, we expect that the equations are incompatible

and that no solutions exist. Of course, we already know from the simple case

of linear systems of equations that this is not always true. For example, the

following system of 2 linear equations in three unknowns has no solution:

x1 + x2 + x3 = 0

. (11.4)

x1 + x2 + x3 = 1

To also give a counter-example for the other case, let us consider the following

system of 3 linear equations in two unknowns:

ļ£± ļ£¼

ļ£² x1 + x2 = 0 ļ£½

x1 = 1 , (11.5)

x2 = ā’1

ļ£³ ļ£¾

this system clearly has a solution. In the case of linear systems, the algorithms

from Chapter 3 can solve all these issues. With general systems, the situation

is more complicated and we need to introduce some additional mathematical

notions. Comparing the systems given by Equations (11.3) and (11.4), we

ļ¬rst see a diļ¬erence in the way of writing the equations. With linear systems,

it is convenient to have a linear combination of the unknowns on the left-hand

side of each equation and a constant on the right-hand side. With algebraic

systems, it is often considered preferable to shift the constants to the left-hand

sides and incorporate them in the polynomials f1 , . . . , fm .

Ā© 2009 by Taylor and Francis Group, LLC

340 Algorithmic Cryptanalysis

11.2 Bivariate systems of equations

Since the issue of solving general systems of equations is quite complicated

and since we already know how to solve univariate polynomial equations,

we start by considering the reasonably simple case of bivariate systems of

equations before turning to the general case.

First, if we are given a single polynomial f (x, y) in two unknowns, we can

prove that this polynomial has a inļ¬nite number of roots over the algebraic

ĀÆ

closure K. For this purpose, let us write:

dx

f (i) (y)xi .

f (x, y) = (11.6)

i=0

Furthermore, let g(y) denote the greatest common divisor of (f (1) , Ā· Ā· Ā· , f (dx ) ),

omitting f (0) . This polynomial g has a ļ¬nite number of roots, possibly zero.

For each root Ī½ of g, we see that f (x, Ī½) is a constant polynomial and thus does

not have any root, unless f (0) (Ī½) = 0. For any value Ī½ with g(Ī½) = 0, f (x, Ī½)

is a non-constant polynomial and its number of roots (with multiplicities)

ĀÆ

is equal to its degree. Since K is always an inļ¬nite ļ¬eld, f has necessarily

inļ¬nitely many solutions: at least one for all possible values of y but the

ļ¬nitely many roots of g.

After considering a single polynomial, the next step is to look at a system

of two algebraic equations, f1 (x, y) = f2 (x, y) = 0. Proceeding as above, we

can write:

d1,x d2,x

(i) (i)

f1 (y)xi f2 (y)xi ,

f1 (x, y) = and f2 (x, y) = (11.7)

i=0 i=0

thus viewing f1 and f2 as polynomials in K[y][x]. With this view, it is natural

to compute the GCD of f1 and f2 using Euclidā™s algorithm for univariate

polynomial in x. Note that we need to be careful because K[y] is a ring and

not a ļ¬eld. To avoid this complication, one option is to allow rational fractions

from K(y) as coeļ¬cients of polynomial in x during the GCD computations.

At the end of the computation, we obtain a polynomial in x with coeļ¬cients

in K(y). Two cases are possible, either this polynomial is of degree zero in x

or it is of higher degree. When the degree is positive, we learn that f1 and

f2 are both multiples of another polynomial in x and y. Thus, we are back

to the case of a single polynomial. When the degree in x is 0, the GCD with

coeļ¬cient in K(y) is 1. Thus, at ļ¬rst, one may expect that the system has

no roots. However, at that point, we need to clear the denominators in the

relation and obtain:

Āµ(y)f1 (x, y) + Ī½(y)f2 (x, y) = g(y). (11.8)

Ā© 2009 by Taylor and Francis Group, LLC

Polynomial systems and GrĀØbner base computations

o 341

Since, at this point, g no longer contains the variable x, we say that we have

eliminated x from the algebraic system of equations.

An example of this approach is given in Figure 11.1. This example is quite

simple; however, in general, due to the need to clear denominators, using

GCD computations for the purpose of elimination is somewhat cumbersome.

Thankfully, there exists a diļ¬erent approach which always yields the correct

result and simply requires to compute the determinant of a square matrix

whose coeļ¬cients are univariate polynomials. This approach is the computa-

tion of resultants and is addressed in the next section.

11.2.1 Resultants of univariate polynomials

To understand how resultants work, we start with univariate polynomials.

Let g1 (x) and g2 (x) be two monic polynomials in K[x], we deļ¬ne the resultant

Res(g1 , g2 ) as:

Res(g1 , g2 ) = g2 (Ī±). (11.9)

ĀÆ

Ī± root in K of g1

(with multiplicity)

ĀÆ

Splitting g2 into a product of linear factor over K we see that:

(Ī± ā’ Ī²).

Res(g1 , g2 ) = (11.10)

ĀÆ ĀÆ

Ī± root in K of g1 Ī² root in K of g2

(with multiplicity) (with multiplicity)

As a consequence, exchanging the two products and replacing Ī² ā’ Ī± by Ī± ā’ Ī²,

we ļ¬nd that:

Res(g1 , g2 ) = (ā’1)deg(g1 ) deg(g2 ) Res(g2 , g1 ). (11.11)

Moreover, Res(g1 , g2 ) is 0 if and only if g1 and g2 share at least one common

root.

A very important fact is that computing the resultant of g1 and g2 does

not require to compute the roots of either polynomial. Instead, it suļ¬ces to

construct a simple matrix formed from the coeļ¬cients of both polynomials

and to compute its determinant using classical linear algebra techniques. If

d1 is the degree of g1 and d2 the degree of g2 , we construct a square matrix

of dimension d1 + d2 . Writing:

d1 d2

(i) (i)

g1 xi g2 xi ,

g1 (x) = and g2 (x) = (11.12)

i=0 i=0

Ā© 2009 by Taylor and Francis Group, LLC

342 Algorithmic Cryptanalysis

As a sample system of bivariate equations, let us deļ¬ne:

f1 (x, y) = y Ā· x3 + (2y 2 + y) Ā· x2 + (y 3 + y 2 + 1) Ā· x + (y + 1) and

f2 (x, y) = y Ā· x4 + 2 y 2 Ā· x3 + (y 3 + 1) Ā· x2 + y Ā· x.

Dividing f1 and f2 by y, we obtain unitary polynomials g1 and g2 in x whose

coeļ¬cients are rational fractions in y. Using Euclidā™s GCD Algorithm 2.1

produces the following sequence of polynomials of decreasing degree in x:

1

g3 (x, y) = (g2 ā’ (x ā’ 1)g1 )/(y + 1) = x2 + y Ā· x + ,

y

g4 (x, y) = g1 ā’ (x + y + 1) Ā· g3 = 0.

As a consequence, f1 and f2 are both multiples of g3 . It is even possible to

clear the denominator and write:

f1 (x, y) = (x + y + 1) Ā· (y x2 + y 2 x + 1) and

f2 (x, y) = (x2 + y x) Ā· (y x2 + y 2 x + 1).

Thus, solutions of the original system are either roots of y x2 + y 2 x + 1 or

solutions of the lower degree system given by:

h1 (x, y) = x + y + 1 and h2 (x, y) = x2 + y x.

Applying Euclidā™s algorithm once more, we ļ¬nd that:

h3 (x, y) = h2 ā’ (x ā’ 1)h1 = y + 1.

Thus, any solution to this system of equation has y = ā’1. Substituting

this value back into h1 and h2 , we ļ¬nd that in addition x = 0. Since

(x, y) = (0, ā’1) is not a root of y x2 + y 2 x + 1, this illustrates the fact that

in the general case, the set of roots of algebraic systems of equations can

be decomposed into a union of simpler sets. The reader interested in the

theory behind these decompositions should look up the notion of primary

decomposition in a textbook about algebraic geometry, such as [Eis95].

For further characterization of the roots of y x2 + y 2 x + 1, it is useful to

remark that this polynomial is symmetric in x and y. As a consequence,

when (x0 , y0 ) is a root, so is (y0 , x0 ). This polynomial can be rewritten as

sp+1, where s = x+y and p = xy are the elementary symmetric polynomials

in two variables. Note that there is a bijection between sets (x0 , y0 ), (y0 , x0 )

and pairs (s0 , p0 ). In the forward direction, one computes the sum and

product. In the backward direction, one solves the equation X 2 ā’ s0 X + p0

whose roots are x0 and y0 .

Figure 11.1: A sample algebraic system in two unknowns

Ā© 2009 by Taylor and Francis Group, LLC

Polynomial systems and GrĀØbner base computations

o 343

we construct the matrix:

ļ£« (d ) (d ā’1) (d ā’2) (0)

ļ£¶

g1 1 g1 1 g1 1 Ā·Ā·Ā· 0 Ā·Ā·Ā· 0

g1 0

(d ā’1)

(d ) (1) (0)

g1 1 g1 1 Ā·Ā·Ā· 0 Ā·Ā·Ā· 0 ļ£·

ļ£¬0 g1 g1

ļ£¬ ļ£·

ļ£¬. .ļ£·

.. .. .. .. ..

ļ£¬.

. Ā·Ā·Ā· . ļ£·

. . Ā·Ā·Ā· . .

ļ£¬. .

ļ£·

(i) (0) ļ£·

ļ£¬

Ā·Ā·Ā· Ā·Ā·Ā· Ā·Ā·Ā· g1 Ā· Ā· Ā· g1 ļ£·

ļ£¬0 0 0

MS (g1 , g2 ) = ļ£¬ (d2 ) (d2 ā’1) (11.13)

ļ£·

(d2 ā’2) (0)

Ā·Ā·Ā· 0 Ā·Ā·Ā· 0 ļ£·

ļ£¬ 2 g2

ļ£¬g g2 g2 0 ļ£·

(d ā’1)

(d ) (1) (0)

g2 2 g2 2 Ā·Ā·Ā· 0 Ā·Ā·Ā· 0 ļ£·

ļ£¬0 g2 g2

ļ£¬ ļ£·

ļ£¬. .ļ£·

.. .. .. .. ..

ļ£¬ ļ£·

ļ£. .ļ£ø

. . Ā·Ā·Ā· . . . Ā·Ā·Ā· .

.

(j) (0)

Ā·Ā·Ā· Ā·Ā·Ā· Ā·Ā·Ā· g2 Ā· Ā· Ā· g2

0 0 0

This matrix, called the Sylvester matrix of g1 and g2 can be interpreted in the

following way: each column corresponds to some power of x, 1 for the ļ¬rst

column, x for the second and so on, up to xd1 +d2 ā’1 for the last column. Each

row corresponds to a polynomial, the ļ¬rst d2 rows are given by g1 , xg1 , . . . ,

xd2 ā’1 g1 , the next d1 rows are given by g2 , xg2 , . . . , xd1 ā’1 g2 . The resultant of

g1 and g2 is obtained as the determinant of the Sylvester matrix:

Res(g1 , g2 ) = det(Ms (g1 , g2 )). (11.14)

The proof of this important result is out of the scope of this book and can,

for example, be found in [Lan05, Chapter IV]. Note that using the matrix

of Sylvester, the resultant is also deļ¬ned for non-monic polynomials. In this

case, we have:

d2 d1

(d1 ) (d2 )

Res(g1 , g2 ) = g1 g2 (Ī±ā’Ī²).

ĀÆ ĀÆ

Ī± root in K of g1 Ī² root in K of g2

(with multiplicity) (with multiplicity)

(11.15)

Prime factors of the resultant When g1 and g2 are monic polynomials

with integer coeļ¬cients, each prime p that divides the resultant is such that

g1 and g2 have at least a common root on the algebraic closure of Fp . Note,

however, that when a larger power of a prime, say pk , divides the resultant,

it does not imply that the polynomials have a common root modulo pk .

11.2.2 Application of resultants to bivariate systems

When g1 and g2 are bivariate polynomials in x and y, we can also use

resultants to solve the corresponding system of equations. To do this, we need,

as when considering GCDs, to view these polynomials as polynomials in x

whose coeļ¬cients are polynomials in y, i.e., polynomials in K[y][x]. With this

view, Sylvesterā™s matrix, given by Equation (11.13), is ļ¬lled with univariate

Ā© 2009 by Taylor and Francis Group, LLC

344 Algorithmic Cryptanalysis

polynomials in y and its determinant is another polynomial in y. In order to

specify which variable is eliminated from the system of equations during the

computation of the resultant, we say that we have computed the resultant of

g1 and g2 in the variable x. This resultant is a polynomial in y. Three cases

arise:

ā¢ If the resultant is the zero polynomial, the two polynomials g1 and g2

have a common factor. Using the example of the polynomials f1 and f2

from Figure 11.1, we may check that their Sylvesterā™s matrix (in x) is:

y 2y 2 + y y 3 + y 2 + 1

ļ£« ļ£¶

y+1 0 0 0

2y 2 + y y 3 + y 2 + 1

ļ£¬0 y y+1 0 0ļ£·

ļ£¬ ļ£·

2y 2 + y y 3 + y 2 + 1

ļ£¬0 0 y y+1 0ļ£·

ļ£¬ ļ£·

2y 2 + y y 3 + y 2 + 1 y + 1 ļ£·

ļ£¬0 0 0 y

ļ£¬ ļ£·

ļ£¬ y 2y 2 y3 + 1 y 0 0 0ļ£·

ļ£¬ ļ£·

2y 2 y3 + 1

ļ£0 y y 0 0ļ£ø

2y 2 y3 + 1

0 0 y y 0

Moreover, the determinant of this matrix is zero. Indeed, multiplying

MS (f1 , f2 ) on the left by the vector (0, ā’1, ā’y, 0, 0, 1, y + 1) yields the

null vector.

ā¢ If the resultant is a non-zero constant polynomial, we learn that the

system of equations is incompatible over the ļ¬eld of complex numbers.

However, assuming that f1 and f2 are monic, then modulo prime divisors

of the resultant, they have a common factor. If f1 and f2 are not monic,

the conclusion only holds for prime factors of the resultant which divide

none of the leading coeļ¬cients.

ā¢ If the resultant is a polynomial of higher degree, say R(y) , then the y

coordinate of any solutions of the system of equations given by f1 and

f2 is a root of R. However, the converse is not true.

11.2.2.1 Using resultants with more variables

In theory, using resultants with more variables allows to solve arbitrary

systems of equations. However, with n polynomials in n unknowns, we see

that the computation quickly becomes diļ¬cult. A ļ¬rst problem, we have

too many possible choices, we can choose to eliminate any of the n variables

for any of the n(n ā’ 1)/2 pairs of polynomials. Moreover, even if we decide

to eliminate a speciļ¬c variable, it is unclear whether we should compute the

resultant of all pairs of polynomials or only keep a fraction of them. With

the next variable to eliminate, we have even more options and do not know

how to proceed. A second problem is that the degrees of the polynomials we

construct during computations of resultants grow too quickly.

As a consequence, resultants can only be used to solve systems of polyno-

mial equations with a reasonably small number of unknowns and a diļ¬erent

approach is needed to address more general cases.

Ā© 2009 by Taylor and Francis Group, LLC

Polynomial systems and GrĀØbner base computations

o 345

11.3 Deļ¬nitions: Multivariate ideals, monomial order-

ings and GrĀØbner bases

o

We now turn to the general case of multivariate systems of equations as in

system of equations (11.3). Clearly, any root of this system is also a root of

all polynomials in the ideal I generated by f1 , . . . , fm . Recall that this ideal

is given by:

m

hi fi | ā(h1 , Ā· Ā· Ā· , hm ) ā K[x1 , Ā· Ā· Ā· , xn ]m

I = (f1 , Ā· Ā· Ā· , fm ) = . (11.16)

i=1

Given such an ideal I, we deļ¬ne the aļ¬ne algebraic variety of I, as the set

ĀÆ

V(I) of the common roots of all polynomials in I over the algebraic closure K :

V(I) = {(Ī±1 , Ā· Ā· Ā· , Ī±n ) | ā f ā I : f (Ī±1 , Ā· Ā· Ā· , Ī±n ) = 0} . (11.17)

Clearly, V(I) does not depend on the exact choice of generating polynomials

f1 , . . . , fm , but only on the ideal I. This is going to be a key property

for solving algebraic systems. In fact, the goal of the present chapter can

informally be rephrased into: Given a set of generating polynomials for an

ideal I, ļ¬nd a new set of generating polynomials better suited to determine

V(I) and its properties.

Conversely, we can ask whether I is uniquely determined by V(I). More

precisely, given a set of points V , let us deļ¬ne:

I(V ) = {f ā K[x1 , Ā· Ā· Ā· , xn ] | ā (Ī±1 , Ā· Ā· Ā· , Ī±n ) ā V : f (Ī±1 , Ā· Ā· Ā· , Ī±n ) = 0} .

(11.18)

We see that I(V ) is an ideal and that I(V(I)) ā‚ I. However, equality does

not hold in general. To give an example with a single variable, we see that

I(V((x2 ))) = (x). Indeed, the only (double) root of x2 is 0 and it is also a

root of x. The generalization of this example relies on the deļ¬nition of the

ā

radical of an ideal. Given an ideal I, we deļ¬ne its radical I as:

ā

I = f ā K[x1 , Ā· Ā· Ā· , xn ]|āt ā N; f t ā I . (11.19)

A famous theorem of Hilbert, called the Nullstellensatz theorem relates I(V(I))

ā

and I:

THEOREM 11.1

If K is an algebraically closed ļ¬eld and I an ideal of K[x1 , Ā· Ā· Ā· , xn ], then:

ā

I(V(I)) = I.

PROOF See [CLO07, Chapter 4].

Ā© 2009 by Taylor and Francis Group, LLC

346 Algorithmic Cryptanalysis

11.3.1 A simple example: Monomial ideals

We recall that a monomial in a polynomial ring K[x1 , Ā· Ā· Ā· , xn ] is a polyno-

mial of the form Ī»xĪ±1 Ā· Ā· Ā· xĪ±n . For conciseness, we denote it by Ī»X Ī± , where

n

1

Ī± = (Ī±1 , Ā· Ā· Ā· , Ī±n ). We say that an ideal I is a monomial ideal if I can be

(1) (m)

generated by a family of monomials, i.e., I = (X Ī± , Ā· Ā· Ā· , X Ī± ). Note that

since K is a ļ¬eld, the constants appearing in the monomials can be removed

after multiplication by their respective inverses.

Monomial ideals are easy to manipulate. First, a polynomial f belongs to a

(1) (m)

monomial ideal I = (X Ī± , Ā· Ā· Ā· , X Ī± ), if and only if all the monomials that

occur with a non-zero coeļ¬cient in f also belong to I. Moreover, a monomial

(i)

Ī»X Ī² , with Ī» = 0 is in I, if and only if, at least one monomial X Ī± divides

X Ī² . Furthermore, testing divisibility for monomials is very simple, indeed,

X Ī± divides X Ī² if and only if, for all 1 ā¤ i ā¤ n, we have Ī±i ā¤ Ī²i .

11.3.2 General case: GrĀØbner bases

o

Since the case of monomial ideals is very simple, it is useful to link the gen-

eral case with this special case. For this purpose, we introduce order relations

between monomials. We call a monomial ordering, any total order relation

on the set of monomials of K[x1 , Ā· Ā· Ā· , xn ] which satisļ¬es the following proper-

ties:

ā¢ Compatibility For any triple of monomials (X Ī± , X Ī² , X Ī³ ) :

XĪ± X Ī² implies X Ī± X Ī³ XĪ²XĪ³.

ā¢ Well-ordering Any set S of monomials contains a smallest element

with respect to , this element is denoted min (S).

By abuse of notation, when X Ī± X Ī² , we may also write Ī± Ī². With this

convention, the compatibility property becomes:

ā¢ Compatibility For any triple (Ī±, Ī², Ī³) :

Ī± Ī² implies Ī± + Ī³ Ī² + Ī³.

To better understand the well-ordering property, let us introduce two order

relations on monomials:

ā¢ The lexicographic ordering lex is deļ¬ned by: Ī± lex Ī², if and only if

there exists an index 1 ā¤ i0 ā¤ n such that:

ā“ For all i < i0 , Ī±i = Ī²i .

Ā© 2009 by Taylor and Francis Group, LLC

Polynomial systems and GrĀØbner base computations

o 347

ā“ And Ī±i0 > Ī²i0 .

ā¢ The reverse lexicographic1 order relation revlex is deļ¬ned by: Ī± revlex

Ī², if and only if there exists an index 1 ā¤ i0 ā¤ n such that:

ńņš. 12 |