Nicolas Gama

Phong Q Nguyen

Oded Regev

Lattice Enumeration using Extreme Pruning

Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.

Introduction

A lattice is the set of all integer combinations of n linearly independent vectors b 1 , . . . , b n in R n . These vectors are known as a basis of the lattice. The most basic computational problem involving lattices is the shortest vector problem (SVP), which asks to find a nonzero lattice vector of smallest norm, given a lattice basis as input. The inhomogeneous version of the problem is called the closest vector problem (CVP); here we are given an arbitrary vector in addition to the lattice basis and asked to find the lattice point closest to that vector.

Algorithms for these problems can be used to solve a wide range of problems, such as integer programming [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF], factoring polynomials with rational coefficients [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], integer relation finding [START_REF] Håstad | Polynomial time algorithms for finding integer relations among real numbers[END_REF], as well as problems in communication theory (see [START_REF] Agrell | Closest point search in lattices[END_REF][START_REF] Nguyen | The LLL Algorithm: Survey and Applications[END_REF] and references therein). They are also extremely useful in public-key cryptanalysis, notably they can break special cases of RSA and DSA (see [START_REF] Nguyen | Public-key cryptanalysis[END_REF] and references therein). And the growing interest in lattice-based cryptography further motivates their study.

There are two main algorithmic techniques for lattice problems. The first technique, known as lattice reduction, started with the celebrated LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] and continued with blockwise algorithms [START_REF] Schnorr | A hierarchy of polynomial lattice basis reduction algorithms[END_REF][START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF][START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF] such as BKZ [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]. It works by applying successive elementary transformations to the input basis in an attempt to make its vectors shorter and more orthogonal. For usual parameters, such algorithms run in polynomial time, but the approximation factor they provide is asymptotically exponential (see [START_REF] Gama | Predicting Lattice Reduction[END_REF] for experimental results). A second and more basic approach, which is the focus of our work, is the enumeration technique which dates back to the early 1980s with work by Pohst [START_REF] Pohst | On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications[END_REF], Kannan [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF], and Fincke-Pohst [START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF], and is still actively investigated (e.g., [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF][START_REF] Agrell | Closest point search in lattices[END_REF][START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)[END_REF][START_REF] Pujol | Rigorous and efficient short lattice vectors enumeration[END_REF][START_REF] Schnorr | Average time fast SVP and CVP algorithms for low density lattices[END_REF][START_REF] Micciancio | A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations[END_REF][START_REF] Stehlé | On the extremality of an 80-dimensional lattice[END_REF]). In its simplest form, enumeration is simply an exhaustive search for the best integer combination of the basis vectors. Enumeration algorithms run in exponential time (or worse) but find the shortest vector (as opposed to a loose approximation thereof).

The two approaches are often combined. First, blockwise lattice reduction algorithms rely on a subroutine to find short vectors in a low-dimensional lattice, whose dimension is a parameter known as the "block size". This subroutine is typically implemented through enumeration. Second, the running time of enumeration algorithms crucially depends on the quality of the input basis. Therefore, enumeration algorithms are almost never applied directly to a given basis; instead, one first applies lattice reduction and then runs an enumeration algorithm on the resulting reduced basis.

An alternative algorithmic technique for solving lattice problems was suggested in 2001 by Ajtai, Kumar, and Sivakumar [START_REF] Ajtai | A sieve algorithm for the shortest lattice vector problem[END_REF] (see also [START_REF] Ajtai | Sampling short lattice vectors and the closest lattice vector problem[END_REF][START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF][START_REF] Micciancio | Faster exponential time algorithms for the shortest vector problem[END_REF][START_REF] Pujol | Solving the shortest lattice vector problem in time 2 2.465n[END_REF] for recent improvements). Although this technique, known as sieving, leads to the asymptotically fastest algorithms for solving lattice problems exactly (running in time essentially 2 O(n) ), it also requires an exponential amount of space, and as a result, it is so far not useful in practice. We will not discuss this technique in the remainder of the paper.

Previous results. As mentioned above, the focus of our work is on enumeration algorithms which are important not just as standalone algorithms, but also as routines in lattice reduction algorithms. The basic enumeration algorithm (as in [START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF][START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]) essentially amounts to an exhaustive search for an integer combination of the basis vectors whose norm is small enough, say, at most some given threshold R. The search can be seen as a depth-first search on a tree whose leaves correspond to lattice points, and whose internal nodes correspond to partial assignments to the coefficients of the integer combination, or geometrically, to the intersection of the lattice with subspaces (see Sect. 3 for a more detailed description). We include in the tree only those nodes whose norm is at most R.

In an attempt to speed up the running time of this algorithm, Schnorr, Euchner, and Hörner [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF][START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] suggested in the 1990s a modification of the basic enumeration algorithm, called pruned enumeration. The rough idea is to prune subtrees of the tree in which the "probability" of finding a desired lattice point is "too small". 4 By doing so, we effectively restrict our exhaustive search to a subset of all possible solutions. The hope is that although this introduces some probability of missing the desired vector, this "probability" would be small compared to the gain in running time.

Experimentally, this led to breaking certain instances of the Chor-Rivest cryptosystem, and as a result, the pruning algorithm of Schnorr and Hörner [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] made it into the popular mathematical library NTL [START_REF] Shoup | Number Theory C++ Library (NTL) version 5[END_REF], as a subroutine of BKZ [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]. Unfortunately, to the best of our knowledge, no careful analysis of pruned enumeration was ever performed. The arguments that appear in the existing literature are, as far as we can tell, mostly intuitive and do not provide a proper analysis of pruned enumeration. 5Our results. We start out by providing what we believe is the first sound analysis of pruned enumeration. Our analysis applies to a very general family of pruned enumeration algorithms, in which the pruning is determined by an arbitrary bounding function, which provides for each level of the tree an upper bound on the distance of nodes that should be considered. As we will see, the running time of the enumeration algorithm is determined by the volume of certain highdimensional bodies. Our analysis is based on two heuristic assumptions, both of which we believe are very reasonable. We also provide experimental evidence to back these assumptions.

Next, we use our analysis to understand the effect of various bounding functions on the performance of pruned enumeration algorithms. For instance, the analysis can show that well-chosen bounding functions lead asymptotically to an exponential speedup of about 2 n/4 ≈ 1.189 n over basic enumeration, while maintaining a success probability ≥ 95%.

But our main contribution is the realization that further exponential speedups can be obtained by using bounding functions that significantly reduce the search region. With such bounding functions, the probability of finding the desired vector is actually rather low (say, 0.1%), but surprisingly, the running time of the enumeration is reduced by a much more significant factor (say, much more than 1000). A rigorous explanation of why this happens will be given in Section 5. As a result, we can repeat the pruned enumeration algorithm several times (say, 1000) until the desired vector is found, and the total running time becomes significantly smaller than what one would obtain with standard pruned enumeration. We note that we must "reshuffle" the basis vectors before each enumeration as otherwise all the enumerations would behave identically (this will be explained in more detail when we discuss our second heuristic assumption).

We call this method, which we view as our main conceptual contribution, extreme pruning. We note that a similar idea is used in other algorithms; for instance, this is one of the underlying ideas in Lenstra's elliptic curve factoring method. We are not aware of any other application of this idea in the context of lattice algorithms. Our analysis shows that a well-chosen extreme pruning leads asymptotically to an exponential speedup of about (2-ε) n/2 ≈ 1.414 n over basic enumeration, which is roughly the square of the previous speedup 2 n/4 . Experimental results. In practice, our best extreme pruning is able to find the shortest vector of dense knapsack lattices of dimension 110 (resp. 100) in less than 62.12 (resp. 1.73) CPU days of sequential computation on a single 1.86-Ghz core, with a negligible amount of memory and in a trivially parallelizable manner. With plain Schnorr-Euchner enumeration [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF] on a BKZ-35 reduced basis, it would have taken 1.38 • 10 9 (resp. 482000) CPU years, so the speedup is about 8.1 • 10 9 (resp. 1.0 • 10 8 ). We are currently running new experiments on random lattices (as used in [START_REF] Gama | Predicting Lattice Reduction[END_REF]), and we expect similar exponential speedups. To the best of our knowledge, none of these dense lattices can be handled by standard lattice reduction: they are harder than the 350-dimensional lattice (solved in [START_REF] Nguyen | Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97[END_REF]) from the GGH challenges.

Open Questions. We expect extreme pruning to improve the performance of lattice reduction algorithms [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF][START_REF] Gama | Predicting Lattice Reduction[END_REF], but we leave it to future work to assess its precise impact. Our focus in this paper is on high-dimensional enumeration, whereas lattice reduction algorithms typically apply enumeration on blocks whose dimension is rather small; for instance, the experiments of [START_REF] Nguyen | Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97[END_REF] used a block size of 60. Currently, our extreme pruning algorithm improves enumeration by randomization, but still uses negligible space; it would be interesting to see if further improvements can be made by using more space. One way to do so would be to design new algorithms for the closest vector problem with preprocessing (CVPP). Indeed, a good CVPP algorithm can help to prune the enumeration tree in the following way: one would enumerate all the nodes at some depth k, and use the CVPP algorithm to discard those which do not lead to any leave, without having to compute all their children. Unfortunately, we have so far been unable to obtain an improvement in practice using state-of-the-art CVPP algorithms [START_REF] Aharonov | Lattice problems in NP intersect coNP[END_REF]. (But see [START_REF] Micciancio | A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations[END_REF] for a theoretically important algorithm that combines CVPP and enumeration.)

Roadmap. We start in Section 2 with some background and notation on lattices, and continue with a description of the basic enumeration algorithm in Section 3. In Section 4 we describe the pruned enumeration algorithm and give our rigorous analysis. Using that analysis, we introduce and analyze the extreme pruning algorithm in Section 5. Finally, we present our experimental results in Sect. 6. Further information is given in the Appendix: App. A discusses the Schnorr-Hörner pruning [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF]; and App. B describes the code used in our experiments, which includes an apparently new implementation trick that speeds up enumeration.

Preliminaries

Lattices are discrete subgroups of R m . Any lattice L can be defined by a basis, which is a set of linearly independent vectors (b

1 , . . . , b n ) in R m such that L is equal to the set L(b 1 , . . . , b n ) = { n i=1 x i b i , x i ∈ Z} of
all integer linear combinations of the b i 's. All the bases of L have the same number n of elements, called the dimension of L, and they all have the same volume, called the volume vol(L) or determinant of L. Throughout the paper, we use row representations of matrices. The Euclidean norm of a vector v ∈ R m is denoted v . We denote by Ball n (R) the n-dimensional Euclidean ball of radius R, and by

V n (R) = R n • π n/2
Γ (n/2+1) its volume. The n-dimensional unit sphere is denoted by S n-1 .

Shortest vector. A lattice L contains non-zero vectors of minimal Euclidean norm: this norm is called the first minimum λ 1 (L) of L. A vector of norm λ 1 (L) is called a shortest vector of L, and is in general unique up to the sign. Hermite's constant γ n is the supremum of the ratio (λ 1 (L)/vol(L) 1/n ) 2 over all n-dimensional lattices. Minkowski's theorem shows that √ γ n is smaller than the diameter of the n-dimensional ball of volume 1:

√ γ n ≤ 2 • V n (1) -1/n ≤ √ n. Orthogonalization. A basis B = (b 1 , . . . , b n ) can be written uniquely as a prod- uct B = µ • D • Q where µ = (µ i,j ) is
, . . . , b i-1 ) ⊥ . For all i ∈ {1, . . . , n + 1}, π i (L) is an n + 1 -i dimensional lattice generated by the basis (π i (b i ), . . . , π i (b n )), with vol(π i (L)) = n j=i b * j .
Reduced bases. Lattice reduction algorithms aim to transform an input basis into a "high quality" basis. There are many ways to quantify the quality of bases produced by lattice reduction algorithms. One popular way, which is particularly useful for our purposes, is to consider the Gram-Schmidt norms b * 1 , . . . , b * n . Intuitively speaking, a good basis is one in which this sequence never decays too fast. In practice, it turns out that the Gram-Schmidt coefficients of bases produced by the main reduction algorithms (such as LLL or BKZ) have a certain "typical shape", assuming the input basis is sufficiently random. This property was thoroughly investigated in [START_REF] Gama | Predicting Lattice Reduction[END_REF][START_REF] Nguyen | LLL on the average[END_REF]: accordingly, our speedup analysis assumes to simplify that b * i / b * i+1 ≈ q where q depends on the reduction algorithm.

Gaussian Heuristic. The Gaussian Heuristic provides an estimate on the number of lattice points inside a "nice enough" set.

Heuristic 1 Given a lattice L and a set S, the number of points in S ∩ L is approximately vol(S)/vol(L).

In some cases, this heuristic can be proved. For instance, Ajtai showed [3] that for any finite Borel set S of measure V which does not contain 0, the expectation of S ∩ L taken over a certain natural distribution on lattices L of volume D is V /D. In particular, the expectation of λ 1 (L) on random lattices of volume D is the radius of the n-dimensional ball of volume D, that is

D 1/n • V n (1) -1/n ,
which is often used as a "prediction" of λ 1 (L) for a "typical" lattice. There are also counterexamples to this heuristic (see, e.g., [START_REF] Mazo | Lattice points in high dimensional spheres[END_REF] for counterexamples in Z n ).

Enumeration

We recall Schnorr-Euchner's enumeration algorithm [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF] which is the enumeration algorithm used in practice, and analyze its cost.

Setting

To simplify the exposition, we assume in the rest of the paper the following setting. Let L be a lattice whose shortest vector v is unique (up to sign). Our goal is to find v. (Our entire analysis can be extended in a straightforward manner to the closest vector problem.) We assume we are given a basis (b 1 , . . . , b n ) of L and a very good upper bound R on λ 1 (L) so that finding ±v amounts to finding any nonzero lattice vector w ∈ L such that w ≤ R, and therefore, we can easily check whether or not the solution is correct. In many practical situations, λ 1 (L) is known exactly: this is typically true in cryptographic situations, such as in CJLOSS lattices [START_REF] Coster | An improved low-density subset sum algorithm[END_REF]. In the full version, we will explain how to adapt our analysis to the general case of SVP.

Description

To find ±v, enumeration goes through the enumeration tree formed by all vectors in the projected lattices π n (L), π n-1 (L), . . . , π 1 (L) of norm at most R. More precisely, the enumeration tree is a tree of depth n, and for each k ∈ {0, . . . , n}, the nodes at depth k are all the vectors of the rank-k projected lattice π n+1-k (L) with norm at most R. In particular, the root of the tree is the zero vector (because π n+1 (L) = {0}), while the leaves are all the vectors of L of norm ≤ R. The parent of a node u ∈ π n+1-k (L) at depth k is by definition π n+2-k (u) at depth k -1. And we order the child nodes by increasing Euclidean norm: note that all ancestors of a given node are at most as long as the node, because they are projections of the node.

We note that the tree is symmetric, because if x ∈ L then -x ∈ L. Thus, we halve the tree by restricting to "positive" nodes: we only consider nodes π n+1-k (u) where the last nonzero coordinate of u ∈ L with respect to (b 1 , . . . , b n ) is positive. From now on, by enumeration tree, we mean this halved enumeration tree, which has a single leaf, either v or -v. The Schnorr-Euchner algorithm [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF] performs a Depth First Search of the tree to find the single leaf. The more reduced the basis is, the less nodes in the tree, and the cheaper the enumeration.

Concretely, the shortest vector v ∈ L may be written as

v = v 1 b 1 +• • •+v n b n where the v i 's are unknown integers and b i = b * i + i-1 j=1 µ i,j b * j . Then v = n j=1 v j + n i=j+1 µ i,j v i b * j ,
which gives the norms of its projections as:

π n+1-k (v) 2 = n j=n+1-k   v j + n i=j+1 µ i,j v i   2 b * j 2 , 1 ≤ k ≤ n (1)
Now, if v is a leaf of the tree, then the n inequalities π n+1-k (v) ≤ R together with (1) enable us to perform an exhaustive search for the coordinates

v n , v n-1 , . . . , v 1 of x: n j=n+1-k   v j + n i=j+1 µ i,j v i   2 b * j 2 ≤ R 2 , 1 ≤ k ≤ n,
which can be rewritten for 1 ≤ k ≤ n as

v n+1-k + n i=n+2-k µ i,j v i ≤ R 2 - n j=n+2-k v j + n i=j+1 µ i,j v i 2 b * j 2 b * n+1-k (2)
We start with k = 1 in (2), that is: 0 ≤ v n ≤ R/ b * n because we restricted to "positive" nodes. This allows to perform an exhaustive search for the integer v n , and we do so by increasing values of v n . Now, assume that the projection π n+2-k (v) has been guessed for some k: the integers v n+2-k , . . . , v n are known. Then (2) enables to compute an interval I n+1-k such that v n+1-k ∈ I n+1-k , and therefore to perform an exhaustive search for v n+1-k . A Depth First Search of the tree corresponds to enumerating I n+1-k from its middle, by increasing values of

π n+1-k (v) , namely v n+1-k = - n i=n+2-k µ i,j v i , - n i=n+2-k µ i,j v i ± 1,
and so on.

Complexity

The running time of the enumeration algorithm is N polynomial-time operations where N is the total number of tree nodes. Hence, in order to analyze this running time, we need to obtain good estimates of N . As already suggested by Hanrot and Stehlé [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)[END_REF], a good estimate of N can be derived from the Gaussian heuristic. More precisely, the number of nodes at level k is exactly half the number of vectors of π n+1-k (L) of norm ≤ R (where the half comes because we halved the tree). Since vol(π n+1-k (L)) = n i=n+1-k b * i , the Gaussian heuristic predicts the number of nodes at level k scanned by the Schnorr-Euchner algorithm to be close to

H k = 1 2 • V k (R) n i=n+1-k b * i . (3)
If this holds, then N ≈ n k=1 H k . In Sect. 6.1, we present experiments that strongly support this heuristic estimate.

For a typical reduced basis, we have b * i / b * i+1 ≈ q where q depends on the reduction algorithm (see [START_REF] Gama | Predicting Lattice Reduction[END_REF]). The bound R = √ γ n vol(L) 1/n is optimal in the worst case. Since √ γ n = Θ( √ n), an elementary computation shows that (3) becomes:

H k ≈ b 1 n-k 2 O(n) q (n-1-k)(n-k)/2 vol(L) (n-k)/n = q (n-k)(n-1)/2 2 O(n) q (n-1-k)(n-k)/2 = q (n-k)k/2 2 O(n) ,
where the right-hand term is always less than

q n 2 /8 2 O(n) because (n -k)(k/2)
is maximized for k = n/2. Hence:

H k q n 2 /8 2 O(n) .
Thus, max k H k is super-exponential in n and is reached for k ≈ n/2, which is consistent with experiments (see Fig. 1 of Sect. 5.2). For small values of n, the term 2 O(n) is not negligible, and may shift a bit the maximum index k ≈ n/2. We note that if we make the (reasonable) assumption that the location of the leaf is uniform, the number of nodes scanned by the enumeration algorithm will only be N/2 in expectation, and not N . For simplicity, we ignore this factor 2 in the sequel.

Finally, we mention that rigorous bounds on N exist. For instance, if the basis (b 1 , . . . , b n ) is LLL-reduced, and R = b 1 , then it is well-known that N is at most 2 O(n 2 ) . Also, Hanrot and Stehlé [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)[END_REF] showed that if the basis (b 1 , . . . , b n ) is so-called quasi-HKZ-reduced, and R = b 1 , then N ≤ n n/(2e)+o(n) . See [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)[END_REF] for details.

Pruned Enumeration

Since enumeration is expensive, it is tempting not to enumerate all the tree nodes, by discarding certain branches. The idea of pruned enumeration goes back to Schnorr and Euchner [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF], and was further studied by Schnorr and Hörner [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF]. For instance, one might intuitively hope that π n/2 (v) 2 v 2 /2, which is more restrictive than the inequality π n/2 (v) 2 ≤ v 2 used by enumeration. Formally, pruning replaces each of the n inequalities

π n+1-k (v) ≤ R by π n+1-k (v) ≤ R k where R 1 ≤ • • • ≤ R n = R are n real
numbers defined by the pruning strategy. This means that one replaces R by R k in each of the n inequalities [START_REF] Aharonov | Lattice problems in NP intersect coNP[END_REF].

At the end of their paper [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF] , Schnorr and Euchner briefly proposed R k = R min(1, (1.05)k/n), but did not provide any analysis, only limited experiments. Schnorr and Hörner [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] later proposed another choice of R k 's, which we discuss in App. A: we show that this pruning has flaws, and that the analysis of [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] is mostly incorrect; in particular, if the heuristic analysis of [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] was correct, it would imply polynomial-time algorithms for the shortest vector problem, while the problem is NP-hard under randomized reductions.

We now provide what we believe is the first rigorous analysis of pruned enumeration: The next two subsections deal with the running time and the success probability. In principle, this analysis can be used to optimize the choice of the bounding function in the pruning algorithm. However, we did not attempt to do that since this is not the main focus of our paper. Instead, our analysis will be used in the next section to show how exponential speedups (both in theory and in practice) can be achieved through the use of extreme pruning.

Running time analysis

The running time of the pruned enumeration algorithm is given by

T node • N
where T node is the average amount of time spent processing one node in the enumeration tree, and N is the number of nodes in the pruned tree. In order to estimate N , we estimate the number of nodes at each level of the search tree using the Gaussian heuristic (Heuristic 1). As we shall see later, our estimates agree very nicely with the experiments, giving some further justification to the use of the Gaussian heuristic.

Our estimate is very similar to the one in Equation 3, except that instead of using balls of radius √ R, we use cylinder-

intersections of radii (R 1 , . . . , R k ) for 1 ≤ k ≤ n. More specifically, define the (k-dimensional) cylinder-intersection of radii R 1 ≤ • • • ≤ R k as the set C R1,...,R k = (x 1 , . . . , x k ) ∈ R k , ∀j ≤ k, j l=1 x 2 l ≤ R 2 j .
Notice that the set of vertices in level k of the pruned tree correspond exactly to the points of the projected lattice π n+1-k (L) that are inside C R1,...,R k . Therefore, using the Gaussian heuristic, we can estimate the number of nodes in the enumeration tree using

N = N R1,...,Rn ( b * 1 , . . . , b * n ) = 1 2 n k=1 V R1,...,R k n i=n+1-k b * i (4)
where V R1,...,R k denotes the volume of C R1,...,R k , and the factor half is as a result of the symmetry in the SVP problem. There are several ways to compute or approximate the volume of cylinder intersections V R1,...,R k . The simplest and most naïve method, which is the one we used at first in our numerical optimizations, is based on a Monte Carlo method. Namely, by observing that the cylinder intersection C R1,...,R k is contained in a ball of radius R k , we can write

V R1,...,R k = V k (R k ) • Pr u∼Ball k ∀j ∈ [1, k] , j i=1 u 2 i ≤ R 2 j R 2 k . (5)
The number of samples required to estimate the above probability by Monte Carlo sampling is proportional to its inverse. One can speed things up significantly by replacing the ball with a smaller containing body (such as another cylinder intersection) whose volume is known and from which we can sample uniformly.

For certain interesting choices of radii (R 1 , . . . , R k ), rigorous estimates can be obtained, as we shall see in Section 5. Moreover, one particular case in which we can compute the volume exactly is when R 1 = R 2 , R 3 = R 4 , etc. and k is even. This is because the distribution of the vector (u 2 1 + u 2 2 , u 2 3 + u 2 4 , . . . , u 2 k-1 + u 2 k ) when u is chosen from Ball k is given by a Dirichlet distribution with parameters (1, . . . , 1) (k/2 + 1 ones), which is simply a uniform distribution over the set of all vectors whose coordinates are non-negative and sum to at most 1 (see Page 593 of [START_REF] Devroye | Non-uniform random variate generation[END_REF]). This leads to an easy way to compute the probability in Eq. 5 exactly (as it amounts to computing the volume of a certain polytope). This calculation can also be combined with the Monte Carlo simulation above, leading to much faster running times.

Finally, let us also mention that there is a large body of work showing provably polynomial time algorithms that provide a good approximation to the volume of any convex body (see, e.g., [START_REF] Dyer | A random polynomial-time algorithm for approximating the volume of convex bodies[END_REF][START_REF] Lovász | Simulated annealing in convex bodies and an O * (n 4 ) volume algorithm[END_REF]). However, in practice these algorithms are rather slow and are therefore probably not too useful for our purposes.

Success probability analysis

We let p succ denote the "probability" that the target vector is still in the tree after the pruning. Prior to our work, the implicit assumption was that one should choose a bounding function so as to minimize the running time while keeping p succ reasonably high, say 95%. As we shall see in the next section, surprising speedups can be obtained through extreme pruning, i.e., when p succ is very small.

Before proceeding with the analysis, we must explain what we mean by "probability", since the pruning algorithm is entirely deterministic. (We note that in previous work this was often glossed over; see App. A). In order to meaningfully talk about the success probability p succ , we must assume some kind of distribution on the inputs (since the pruning algorithm is entirely deterministic). For that purpose, we make the following heuristic assumption on the input basis: We use here the imprecise term 'looks like' on purpose. It should be interpreted simply as saying that the estimate on p succ obtained by performing the analysis under the above assumption on the coordinates of the shortest vector corresponds to what one observes in practice on any reasonable distribution of inputs (see Sect. 6 for experiments). We note that Heuristic 2 would follow from a (stronger) natural heuristic on reduced bases: Here, we assume that the reduction is not too strong, that is, the reduced basis is made of vectors that are significantly longer than the shortest vector of the lattice. In typical randomly constructed lattices, the number of such vectors is exponential, 6 and hence, we may hope that the reduced basis is not oriented in any particular direction.

We now estimate the success probability p succ . Let v be the target vector, and let x = (x 1 , . . . , x n ) ∈ R n be its coordinates in the orthonormal basis

(b * n / b * n , . . . , b * 1 / b * 1
) (notice that the coordinates are reversed, with x 1 corresponding to b n etc.). By definition, v belongs to the pruned tree if and only if for all k = 1, . . . , n,

k j=1 x 2 j ≤ R 2 k
. By Heuristic 2, x is distributed like a uniform vector subject to the constraints that x = v . Hence, we can estimate p succ as

p succ = p succ (R 1 , . . . , R n ) = Pr u∼S n-1 v /R ∀j ∈ [1, n], j l=1 u 2 l ≤ R 2 j R 2 n ( 6
)
where S n-1 denotes the unit sphere in n dimensions. As before, one can estimate this probability through Monte Carlo simulation, or compute it exactly in certain cases (e.g., using the fact that if u is chosen from S n-1 for even n, then (u

2 1 + u 2 2 , . . . , u 2 n-3 + u 2 n-2
) is distributed uniformly over all vectors whose coordinates are non-negative and sum to at most 1).

Extreme Pruning

In this section we present our main contribution, the extreme pruning algorithm, whose main idea is to apply pruning using bounding functions whose p succ is very small. Our algorithm takes as input a lattice basis, as well as n real numbers

R 2 1 ≤ • • • ≤ R 2 n = R 2
(the bounding function) where R k corresponds to the pruning in depth k. The goal of the algorithm is to find a vector of length at most R, and is described in Algorithm 1.

Algorithm 1 Extreme Pruning

Repeat until a vector of length at most R is found:

1. Randomize the input basis, and apply basis reduction to it. 2. Run the enumeration on the tree pruned with radii R1, . . . , Rn, as explained in Sect. 4.

We are being deliberately imprecise in Step 1 of the algorithm. First, we do not know what the best method of randomization is, and it is quite likely that this does not matter much. In our experiments, we simply multiplied the input basis by some small unimodular matrix chosen at random, but one can also use other methods. Second, as we shall see in the analysis below, the choice of basis reduction has a great effect on the overall running time, and has to be set properly. The choice of basis reduction algorithm, as well as of the bounds R 1 , . . . , R n will be the topic of Sections 5.2 and 5.3. But first we analyze the expected running time of the algorithm.

Running time analysis

We now analyze the expected running time of the extreme pruning algorithm based on the analysis in Section 4.

First, we estimate the probability of success in each iteration of the algorithm by p succ (R 1 , . . . , R n ), as in Eq. 6, which is based on Heuristic 2. Here, we explicitly perform a randomization before reduction, and we stress that Heuristic 2 produces estimates on p succ that agree very nicely with our experiments (see Sect. 6 for more details).

Next, we estimate the running time of each iteration of the algorithm. Let us denote the (average) running time of Step 1 by T reduc . Once a choice of randomization and reduction algorithm is fixed, this time can be easily estimated experimentally. The running time of Step 2 can be estimated by N R1,...,Rn ( b * 1 , . . . , b * n ), as in Eq. 4. Notice that this running time depends on the Gram-Schmidt coefficients of the basis produced in Step 1, and might vary from one iteration to another. In order to simplify the analysis, we assume that these Gram-Schmidt coefficients are the same throughout all iterations, and denote them by b * 1 , . . . , b * n . This is partly justified by the observation that bases produced by known reduction algorithms have a clear shape that depends only on the reduction algorithm and not so much on the input basis. Alternatively, it should be straightforward to refine our analysis so that it takes into account the distribution of Gram-Schmidt coefficients produced in Step 1, as opposed just to their average. Yet another possibility is to modify the algorithm so that 'bad' bases (i.e., those that differ significantly from the average behavior) are discarded.

To summarize, we can estimate the expected time required to find the desired vector by

T extreme (R 1 , . . . , R n , b * 1 , . . . , b * n ) := T reduc + T node • N R1,...,Rn ( b * 1 , . . . , b * n ) p succ (R 1 , . . . , R n ) . (7)

Choosing Parameters for the Experiments

In order to optimize the running time of the extreme pruning algorithm, we need to choose the basis reduction algorithm used in Step 1, as well as the bounding parameters

R 1 ≤ • • • ≤ R n used in Step 2.
These choices are crucial in determining the running time of the algorithm. Since finding the exact optimum of the expression in Eq. ( 7) seems difficult, we decided to try numerical optimization. We wrote a program that starts from the linear bounding function R 2 k = ( k /n) • R 2 and successively tries to apply small random modifications to it. After each such modification it checks if the expression in Eq. ( 7) decreased or not, with an exact computation based on the Dirichlet distribution (as described in Sect. 4.1). If it did, the modification is accepted; otherwise it is rejected.

This yielded bounding functions whose predicted running time is only 62.1 CPU days (including reduction time) in dimension 110 for hard knapsack lattices, which is significantly better than the linear bounding function (see Figure 1). Fig. 1. On the left are the linear function and our best bounding function found by numerical optimization. On the right we compare the estimated expected number of nodes (with respect to the depth) visited in a run of full enumeration, extreme pruning with the linear function, and extreme pruning using our best bounding function. Note that basis reduction times are ignored here.

Asymptotic Analysis

In this section, we provide a rigorous justification to the effectiveness of extreme pruning. We do this through an analysis of three bounding functions, whose asymptotic behavior we can analyze (under our reasonable heuristic assumptions). The first is the linear bounding function. The speedup it offers over full enumeration is provably exponential, but it is not significantly better than what we can achieve using non-extreme pruning. This is perhaps not surprising since its success probability p succ is 1/n, which is relatively high (so this bounding function is not too 'extreme'). Our second example is a step bounding function. We show that this function obtains an exponential improvement over our best non-extreme bounding function in terms of the number of nodes scanned in the middle level of the tree. This function nicely highlights the reason extreme pruning is superior to non-extreme pruning. Our third bounding function is a piecewise linear bounding function. Its analysis combines the previous two analyses and leads to the best speedups we can rigorously demonstrate.

Throughout this section, we make the simplifying assumption that v = R (which, as discussed above, is the case in many scenarios, and is also the worst case for pruning algorithms). We also ignore the reduction time, which in practice might make the claimed speedups a bit smaller (but does not affect the asymptotics). Finally, instead of giving an absolute bound on the number of nodes in (each level of) the enumeration tree, we compare this number to that in the full enumeration tree. This allows us to focus on analyzing the volume of cylinder intersections, and ignore the properties of the given basis, which we leave for future work.

Linear pruning. We define the linear bounding function as R 2 k = ( k /n) • R 2 , for k = 1, . . . , n. The motivation for this setting comes from the fact that if v is a uniformly random vector of length R (as we assume in our heuristic), then the expectation of the squared norm of its projection on the first k coordinates is exactly ( k /n) • R 2 . Although this bounding function leads to running times that are far from optimal, it is interesting as it can be analyzed rigorously and shown to provide an exponential speedup over full enumeration. In the full version, we prove the following claim, which states that the success probability of linear pruning is exactly 1/n: Claim. Let u be a vector uniformly distributed in the unit sphere S n-1 . Then, Pr u ∀j ∈ {1, . . . , n},

j i=1 u 2 i ≤ j n = 1 n .
This also shows that linear pruning keeps an exponentially small proportion (between 1 /k ( k /n) k/2 and ( k /n) k/2 at each depth k) of nodes:

Corollary 1. For any integer n ≥ 1,

V n (1)/n ≤ vol u ∈ Ball n (1) : ∀j ∈ {1, . . . , n}, j i=1 u 2 i / u 2 ≤ j n ≤ V n (1). ( 8
)
Hence, compared to full enumeration, linear pruning reduces the number of nodes at depth k by the multiplicative factor (n/k) k/2 , up to some polynomial factor. As we saw in Section 3, for typical reduced bases, most of the nodes in the enumeration tree are concentrated around n/2, in which case the speedup is approximately 2 n/4 ≈ 1.189 n .

Step bounding function. We now present an example in which extreme pruning is significantly superior to non-extreme pruning, at least in the asymptotic sense. Consider the step bounding function given by R 2 k = αR 2 for 1 ≤ k ≤ n/2, and R k = R otherwise, where α > 0 is a constant to be determined later. (We fix the location of the step to n/2 for simplicity; the analysis can be easily extended to any step function.) With this bounding function, the number of nodes in the middle level of the pruned enumeration tree compared to that in the middle level of the full enumeration tree is smaller by a factor of α n 4 . We omit the analysis for other levels of the tree because our next bounding function will have a much better performance in this respect, and its analysis is not more complicated.

We now compute the success probability p succ . Eq. 6 tells us that p succ is equal to the probability that for a random point u = (u 1 , . . . , u n ) on the sphere S n-1 , we have n/2 i=1 u 2 i ≤ α. It follows from classical concentration inequalities (see, e.g., Lemma 2.2 in [START_REF] Dasgupta | An elementary proof of the Johnson-Lindenstrauss lemma[END_REF]) that this probability is 1 -2 -Ω(n) if α > 1/2, and 2 -Ω(n) if α < 1/2. Hence, for α > 1/2, we are in the non-extreme regime, and by choosing α close to 1/2 we obtain that the number of nodes in the middle level of the pruned enumeration tree is smaller by a factor of about 2 n/4 ≈ 1.189 n than that in the full enumeration tree. Since most of the nodes are located at depths around n/2, this is a good approximation of the speedup offered by non-extreme pruning using a step function.

Implementation. For lattice reduction, we used fplll [START_REF] Cadé | FPLLL library, version 3.0[END_REF]'s implementation of LLL, and NTL [START_REF] Shoup | Number Theory C++ Library (NTL) version 5[END_REF]'s implementation of BKZ [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]. We implemented our own enumeration algorithms (see App. B) in basic C++, using double and long arithmetic; we plan to release the source codes. The input basis and its Gram-Schmidt orthogonalization were pre-computed with NTL [START_REF] Shoup | Number Theory C++ Library (NTL) version 5[END_REF] in RR precision, and then rounded to double precision before entering the enumeration procedure. While floatingpoint arithmetic is known to cause stability problems during LLL reduction, we did not experience such problems during enumeration, even up to dimension 110; we note that a rigorous analysis of enumeration with floating-point arithmetic has recently been done in [START_REF] Pujol | Rigorous and efficient short lattice vectors enumeration[END_REF].

Lattices. It is important to test algorithms on lattices that do not have a special structure that can be exploited by standard reduction algorithms. On the other hand, we need to be able to decide if the algorithm was successful, therefore λ 1 (L) must be known. For concreteness, we performed all our experiments on hard knapsack lattices, namely the so-called CJLOSS lattices [START_REF] Coster | An improved low-density subset sum algorithm[END_REF] of density 0.94 where the knapsack solution was further chosen with exactly as many 0s as 1s. For these lattices, we can easily check whether the vector found is the shortest vector because it corresponds to knapsack solutions. It can also be checked experimentally that they are quite dense, in the sense that their first minimum λ 1 (L) is close to the Gaussian heuristic, which can be seen as an indication that they are hard instances of SVP (see [START_REF] Gama | Predicting Lattice Reduction[END_REF]). Moreover, these lattices, we believe, serve as a good representative of hard lattices that typically occur in practice. In particular, we believe that the results reported here are not limited to CJLOSS lattices, but in fact represent a general phenomenon. We are currently running new experiments on random lattices (as used in [START_REF] Gama | Predicting Lattice Reduction[END_REF]), for which we have a tight estimate on the first minimum λ 1 (L), but do not know shortest vectors in advance.

Rate of enumeration.

The amount of time an enumeration algorithm spends per node in the tree might depend slightly on the depth of that node in the tree. Luckily, this dependence is typically not too strong, and more importantly, most nodes are concentrated around the same depth of the tree (see, e.g., Fig. 1). In all our experiments in dimensions 100-110, the running time of the enumeration algorithm was directly proportional to the number of nodes in the tree, and the rate of enumeration was very close to 0.94 • 10 7 nodes per second, or equivalently 0.3•10 15 nodes per core-year. This is faster than fplll's [START_REF] Cadé | FPLLL library, version 3.0[END_REF] implementation (which is itself an improvement over NTL [START_REF] Shoup | Number Theory C++ Library (NTL) version 5[END_REF]) by about 40%. This is due to a code optimization described in App. B. Estimated running times. Table 1 compares the expected total number of nodes to be scanned under four different bounding functions for CJLOSS lattices in dimensions 90-120; this number of nodes is obtained by multiplying the expected number of nodes in the pruned tree (as estimated by the Gaussian heuristic) by 1/p succ . Recall that 0. bases. The second row corresponds to Schnorr-Hörner's pruning under BKZ-35 reduced bases with an optimal choice of parameter p so that the success probability is still greater than 90% (this corresponds to p = 48, 57, 67, 77 for dimensions 90, 100, 110, and 120 respectively). The third row corresponds to extreme pruning using the linear bounding function under BKZ-35 reduced bases. And the last row corresponds to extreme pruning using our best numerically optimized bounding function (which we computed only for dimensions 100 and 110) and the optimum BKZ-30 (resp. BKZ-32) in dim 100 (resp. 110).

Here we are only considering the number of nodes scanned, and ignoring the basis reduction time. Except our numerically optimized bounding function, it is negligible. For our best bounding function it adds about 50% to the total running time. Another caveat is that the number of nodes in full enumeration (as well as in Schnorr-Hörner pruning and linear pruning) decreases as we increase the block size of the reduction algorithm beyond 35. However, this does not decrease the overall running time by much since the running time of reduction algorithms depends exponentially on the block size.

Actual running time. The actual running times match the predictions well. In practice, extreme pruning is able to find the shortest vector of 0.94-density CJLOSS lattices of dimension 110 in less than 63 CPU days (including reduction time) of sequential computation on a single core, with a negligible amount of memory and in an easily parallelizable manner. With plain Schnorr-Euchner enumeration [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF] on a BKZ-35 reduced basis, it would have taken 1.38•10 9 (resp. 482000) CPU years, so the speedup is about 8.1 • 10 9 (resp. 1.0 • 10 8 ).

Verifying the Heuristics

In this section we report on some experiments meant to verify our heuristic assumptions.

The accuracy of the Gaussian heuristic. Although the Gaussian heuristic was already suggested as a useful heuristic for analyzing the running time of enumeration algorithms (see [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)[END_REF]), we are not aware of any published experimental verification of the heuristic. We therefore ran a significant number of experiments comparing the actual number of nodes in the enumeration tree to the prediction given by the Gaussian heuristic. We tried both CJLOSS lattices and random lattices with several different reduction algorithms and with either full enumeration or pruned enumeration. In all cases, the estimates given by the Gaussian heuristic were very precise, and typically matched the exact count of nodes to within an error of at most 5%.

Randomness of reduced bases. The success of our experiments gives some evidence to the validity of Heuristics 2 and 3. In the full version, we report on additional experiments whose goal is to validate these heuristics directly. We note that the heuristics cannot apply to very strong reduction notions, where the first basis vector is with very high probability the shortest lattice vector: in such cases, there is no need for enumeration since the shortest vector is already provided to us. But it seems to apply to weaker yet still strong reduction notions, such as BKZ-30 in dimension 100.

  an n × n lower-triangular matrix with unit diagonal, D an n-dimensional positive diagonal matrix and Q an n × m matrix with orthonormal row vectors. Then µD is a lower triangular representation of B (with respect to Q), B * = DQ = (b * 1 , . . . , b * n ) is the Gram-Schmidt orthogonalization of the basis, and D is the diagonal matrix formed by the b * i 's. For all i ∈ {1, . . . , n + 1}, we denote by π i the orthogonal projection on (b 1

Heuristic 2

 2 The distribution of the coordinates of the target vector v, when written in the normalized Gram-Schmidt basis(b * 1 / b * 1 , . . . , b * n / b * n )of the input basis, look like those of a uniformly distributed vector of norm v .

Heuristic 3

 3 The distribution of the normalized Gram-Schmidt orthogonalization (b * 1 / b * 1 , . . . , b * n / b * n ) of a random reduced basis (b 1 , . . . , b n ) looks like that of a uniformly distributed orthogonal matrix.

Table 1 .

 1 3 • 10 15 nodes represent one year of sequential computation. The first row corresponds to full enumeration under BKZ-35 reduced Full enumeration 1.2 • 10 17 1.6 • 10 20 4.0 • 10 23 1.9 • 10 27 Schnorr-Hörner 2.3 • 10 12 7.4 • 10 14 4.7 • 10 17 3.8 • 10 20 Linear pruning 1.1 • 10 11 2.6 • 10 13 1.0 • 10 16 8.3 • 10 18 Pruning vs. full enumeration.

	dim	90	100	110	120
	Extreme pruning	n/a	7.7 • 10 11 2.5 • 10 13	n/a

Making these notions precise requires care, as we shall see later.

In Appendix A, we show some flaws in the analysis of Schnorr and Hörner[START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF].

Moreover, for any c ≥ 1 and any n-dimensional lattice L, the number of lattice points of norm at most 2cVn(1) -1/n vol(L) 1/n is at least c n . But this bound only applies for radii above Minkowski's upper bound, which is twice the Gaussian heuristic.

Acknowledgements. Part of this work was supported by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 ECRYPT II, by the Binational Science Foundation, by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, by the Wolfson Family Charitable Trust, and by a European Research Council (ERC) Starting Grant.

Let us now consider what happens when we take α < 1/2 and move into the extreme pruning regime. By definition, n/2 i=1 u 2 i is distributed according to the beta distribution Beta( n 4 , n 4 ). Therefore, we can express p succ using the regularized incomplete beta function as:

where the inequality follows from integration by parts of the incomplete beta function. Hence, the total number of middle level nodes that will be scanned in the extreme pruning algorithm (which can be seen as an approximation of the overall running time) is smaller than that in full enumeration by a factor of

.

This expression is maximized for very small α > 0, in which case the speedup is asymptotically roughly 4 n 4 ≈ 1.414 n , which is greatly superior to the speedup of 1.189 n obtained with non-extreme pruning.

As this example nicely demonstrates, the advantage of extreme pruning comes from the fact that for small α > 0, although the success probability is exponentially small, the volume of the search region decreases by a stronger exponential factor.

Piecewise linear bounding function. Consider the bounding function defined as

, where we assume that 0 < α < 1/4 is a constant. In the full version, using similar arguments than for linear and step pruning, we show that:

. Ignoring polynomial factors, for sufficiently large n, the total number of level k nodes that will be scanned in the extreme pruning algorithm is shown to be smaller than that in full enumeration by a factor of

for k ≤ n/2 and by a factor of

for k > n/2. We see that for levels around n/2 (say, 0.49n ≤ k ≤ 0.51n), in order to maximize the expressions above, one should choose a small α, in which case the speedup is roughly of 2 n 2 ≈ 1.414 n . For other values of k, the number of nodes may actually increase, but typically these levels contain a small fraction of the nodes, and the global asymptotical speedup is not affected.

Experiments

The setup. All our experiments are run on 64-bit Xeon processors with frequency 1.86 GHz, and compiled with g++ version 4.2.4 x86 64 (options -O9 -ffast-math -funroll-loops -ftree-vectorize). Running times are provided for a single core.

A Schnorr-Hörner Pruning

Here we revisit the pruning strategy described by Schnorr and Hörner in [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF], and analyze it in our framework. Their pruning strategy is implemented in NTL [START_REF] Shoup | Number Theory C++ Library (NTL) version 5[END_REF] as a subroutine to BKZ [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]. It turns out that their bounding function suffers from some fundamental flaws and is clearly inferior to our proposed bounding functions. Furthermore, we show that the analysis of [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] is not satisfying.

A.1 Description

In more detail, given a basis B = (b 1 , . . . , b n ), the Schnorr-Hörner pruning strategy is defined by the following bounding function, which is parameterized by an integer p > 0,

where

is the volume of the unit ball in n -k dimensions. Note that [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] used a different description than the one we gave, but both descriptions can be shown to be equivalent.

In the full version, we rigorously analyze this pruning strategy, and show that it is inferior to our extreme pruning (see also Table 1). Here, we briefly mention several disadvantages. First, the fact that the bounding function depends on a parameter p is undesirable; the analysis of [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] does not give any clear indication on the optimal choice of p. Second, the bounding function may not be positive when p is too small, in which case failure is certain. Third, even for larger values of p, the bounding function may initially decrease, in which case some nodes enumerated in the top levels of the tree are guaranteed to lead to a dead end. In other words, by replacing their bounding function R 2 1 , . . . , R 2 n with the bounding function defined by R

n ), we obtain exactly the same success probability at a lower running time.

A.2 The Analysis of Schnorr and Hörner

We now present some of our observations regarding the original analysis given by Schnorr and Hörner [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF]Sect. 3] and why we believe it is flawed. It should be stressed that the analysis presented there is quite terse, and there is a possibility that our interpretation of it is not what the authors had in mind; yet we think that there is sufficient evidence to suggest that the use of their pruning function should be avoided and we feel that it is important to bring this to the community's attention.

The core of their analysis is [33, Thm. 2], which states that if x n+2-k , . . . , x n ∈ Z are fixed, and if (b 1 , . . . , b n ) is a random basis of L such that its Gram-Schmidt coefficients µ i,j are independent and uniformly distributed modulo 1, then the

is uniformly distributed modulo the lattice L spanned by b 1 , . . . , b n+1-k , which implies, by [33, Lemma 1], that the expectation E of the number of (x 1 , . . . ,

And [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] seems to interpret E as the expectation of the number of leaves (in the enumeration tree) which derive from the node π n+2-k (t) at depth k -1.

Then, [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] claims that Thm. 2 implies that the probability that the pruned enumeration misses the shortest vector is at most 2 -p c where c is said to be experimentally proportional to c p,n 2 p for random LLL-reduced bases, where c p,n decreases to 0 as p increases. The failure probability is claimed to be experimentally ≤ 0.9 for n < 30 and p = 7. Finally, [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] claims that under heuristic arguments, they can show that for p > log 2 n: given a random basis (b 1 , . . . , b n ) of L and a bound R ≤ b 1 , their pruned enumeration performs on the average only O(n 2 2 p ) arithmetic steps to output a lattice vector v ∈ L such that v ≤ R if R ≥ λ 1 (L), or nothing if R < λ 1 (L). However, no proof is provided, and the claim looks suspicious: indeed, by taking p = log 2 n , it would imply polynomial-time algorithms for the shortest vector problem (which is NP-hard under randomized reductions), because n 2 2 p is polynomial in n.

There are further problems in the analysis of [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF]. First of all, the assumption in Thm. 2 that the µ i,j 's of a random reduced basis are uniformly distributed is not supported by experiments: the experiments of [START_REF] Nguyen | LLL on the average[END_REF] show that the distribution of the coefficients µ i,i-1 of a random LLL-reduced basis is far from being uniform. More importantly, the use of Thm. 2 in [START_REF] Schnorr | Attacking the Chor-Rivest cryptosystem by improved lattice reduction[END_REF] to analyze the success probability of pruned enumeration is improper: if one selects (x n+2-k , . . . , x n ) as the last k -1 coordinates of a fixed lattice vector, then these coordinates depend on the random basis, and therefore Thm. 2 cannot be applied. Similarly, the expectation E cannot be viewed as the number of leaves in the enumeration tree which derive from the node π n+2-k (t) at depth k -1, because when the random basis varies, the tree varies too, so for any choice of x n+2-k , . . . , x n ∈ Z, the node π n+2-k (t) may appear in one tree, but not in other trees, so this expectation of the number of leaves cannot be properly defined.

B Pseudo-code of the pruned enumeration code

Here we provide the pseudo-code used to implement the enumeration algorithm in our experiments (see Algorithm 2): a detailed explanation appears in the full version. The code is based on the original Schnorr-Euchner enumeration algorithm [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF], with several minor modifications. The first easy modification (see Line 10) is that we support a general bounding function

The second modification (see Lines 1, 15-17, and 25) is a certain optimization that seems to give in practice a speedup by about 40%. To the best of our knowledge, this improvement has not appeared yet in the literature nor in any software package. Finally, another very minor modification is that we abort the procedure as soon as a vector shorter than R = R n is found.

Algorithm 2 Pruned Enumeration

Input: A basis B = (b1, . . . , bn)

The Gram-Schmidt coefficient matrix µ (a lower-triangular matrix with ones on the diagonal), together with the norms of the Gram-Schmidt vectors b *