Yoshinori Aono

Phong Q Nguyen

Takenobu Seito

Junji Shikata

Lower Bounds on Lattice Enumeration with Extreme Pruning

At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.

Introduction

Among all the candidates submitted in 2017 to the NIST standardization of post-quantum cryptography, the majority are based on hard lattice problems, such as LWE and NTRU problems. Unfortunately, security estimates for lattice problems are known to be difficult: many different assessments exist in the research literature, which is reflected in the wide range of security estimates in NIST submissions (see [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes! Posted on the pqc-forum on Feb. 1[END_REF]), depending on the model used. One reason is that the performance of lattice algorithms depends on many parameters: we do not know how to select these parameters optimally, and we do not know how far from optimal are current parameter selections. The most sensitive issue is the evaluation of the cost of a subroutine to find shortest or nearly shortest lattice vectors in certain dimensions (typically the blocksize of blockwise reduction algorithms). In state-of-the-art lattice reduction software [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF][START_REF] Cadé | FPLLL library, version 3.0[END_REF], this subroutine is implemented by lattice enumeration with extreme pruning, introduced at Eurocrypt '10 by Gama, Nguyen and Regev [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] as a generalization of pruning methods introduced by Schnorr et al [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] in the 90s. Yet, most lattice-based

The views expressed in this paper are those of authors and do not necessarily reflect the official views of the Bank of Japan.

NIST submissions chose their parameters based on the assumption that sieving [START_REF] Ajtai | A sieve algorithm for the shortest 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] Laarhoven | Sieving for shortest vectors in lattices using angular locality-sensitive hashing[END_REF][START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] (rather than enumeration) is the most efficient algorithm for this subroutine. This choice goes back to the analysis of NewHope [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF]Sect. 6], which states that sieving is more efficient than enumeration in dimension ≥ 250 for both classical and quantum computers, based on a lower bound on the cost of sieving (ignoring subexponential terms) and an upper bound on the cost of of enumeration (either [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF]Table 4] or [START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF]Table 5.2]). In dimensions around 140 -150, this upper bound is very close to actual running times for solving the largest record SVP challenges [START_REF] Schneider | SVP challenge[END_REF], which does not leave much margin for future progress; and for dimensions ≥ 250, a numerical extrapolation has been used, which is also debatable.

It would be more consistent to compare the sieving lower bound by a lower bound on lattice enumeration with extreme pruning. Unfortunately, no such lower bound is known: the performances of extreme pruning strongly depends on the choice of bounding function, and it is unknown how good can be such a function. There is only a partial lower bound on the cost of extreme pruning in [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF], assuming that the choice of step bounding function analyzed in [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] is optimal. And this partial lower bound is much lower than the upper bound given in [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF].

Our results. We study the limitations of lattice enumeration with extreme pruning. We prove the first lower bound on the cost of extreme pruning, given a lower bound on the global success probability. This is done by studying the case of a single enumeration with cylinder pruning, and generalizing it to the extreme pruning case of multiple enumerations, possibly infinitely many. Our results are based on geometric properties of cylinder intersections and a probabilistic form of isoperimetry: usually, isoperimetry refers to a geometric inequality involving the surface area of a set and its volume.

Our lower bounds are easy to compute and appear to be reasonably tight in practice, at least in the single enumeration case: we introduce a cross-entropybased method which experimentally finds upper bounds somewhat close to our lower bounds.

Impact. By combining our lower bounds with models of strongly-reduced lattice bases introduced in [START_REF] Nguyen | Hermite's constant and lattice algorithms[END_REF][START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] and quantum speed-ups for enumeration [START_REF] Aono | Quantum lattice enumeration and tweaking discrete pruning[END_REF], we obtain more sound comparisons with sieving: see Fig. 1 for an overview. It suggests that enumeration is faster than sieving up to higher dimensions than previously considered by lattice-based submissions to NIST post-quantum cryptography standardization: the cost lower bound used by many NIST submissions is not as conservative as previously believed, especially in the quantum setting. Concretely, in the quantum setting, the lower bounds of enumeration and sieving cross in dimensions roughly 300-400 in the HKZ-basis model or beyond 500 in the Rankin-basis model, depending on how many enumerations are allowed. We note that in high dimension, our lower bound for enumeration with 10 10 HKZ bases is somewhat close to the numerical extrapolation of [17, (2)], called Core-Enum+O(1) in [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes! Posted on the pqc-forum on Feb. 1[END_REF].

Reduced Basis Model Simulated HKZ basis Rankin basis

Computing Model Classical Quantum Fig. 1. Upper/lower bounds on the classical/quantum cost of enumeration with cylinder pruning, using strongly-reduced basis models. See Sect. 5 for the exact meaning of these curves: the lower bounds correspond to ( 16) and ( 17) and the upper bounds are found by the algorithm in Sect. 4. For comparison, we also displayed several curves from [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes! Posted on the pqc-forum on Feb. 1[END_REF]: 2 0.292n and 2 0.265n as the simplified classical/quantum complexity of sieve algorithms, and the numerical extrapolation of enumeration cost of [17, (2)].

Technical overview. Enumeration is the simplest algorithm to solve hard lattice problems: it outputs L ∩ B, given a lattice L and an n-dimensional ball B ⊆ R n . It dates back to the early 1980s [START_REF] Pohst | On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications[END_REF][START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF][START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF] but has been significantly improved in practice in the past twenty years, thanks to pruning methods introduced by Schnorr et al. [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][START_REF] Schnorr | Lattice reduction by random sampling and birthday methods[END_REF], and later revisited and generalized as respectively cylinder pruning by Gama, Nguyen and Regev [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] and discrete pruning by Aono and Nguyen [START_REF] Aono | Random sampling revisited: Lattice enumeration with discrete pruning[END_REF]: pruning methods offer a trade-off by enumerating over a special subset S ⊆ B, at the expense of missing solutions. Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] introduced the idea of extreme pruning where one repeats pruned enumeration many times over different sets S: this can be globally faster than full enumeration, even if a single enumeration has a negligible probability of returning solutions. In the case of cylinder pruning, [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] showed that the speed-up can be asymptotically exponential for simple choices of the pruning subset S.

Cylinder pruning uses the intersection S of n cylinders defined by a lattice basis and a bounding function f : by using different lattice bases B, one obtains different sets S. The running time and the success probability of cylinder pruning depend on the quality of the basis, and the bounding function f . But when one uses different bases, these bases typically have approximately the same quality, which allows to focus on f , which determines the radii of S.

The probability of success of cylinder pruning is related to the volume of S, whereas its cost is related to the volumes of the 'canonical' projections of S. We show that if the success probability is lower bounded, that is, if S is sufficiently big (with respect to its volume, or its Gaussian measure for the case of solving LWE), then the function f defining S can be lower bounded: as a special case, if S occupies a large fraction of the ball, f is lower bounded by essentially the linear pruning function of [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]. This immediately gives lower bounds on the volumes of the projections of S, but we significantly improve these direct lower bounds using the following basic form of isoperimetry: for certain distributions such as the Gaussian distribution, among all Borel sets of a given volume, the ball centered at the origin has the largest probability. The extreme pruning case is obtained by a refinement of isoperimetry over finitely many sets: it is somewhat surprising that we obtain a lower bound even in the extreme case where we allow infinitely many sets S.

All our lower bounds are easy to compute. To evaluate their tightness, we introduce a method based on cross-entropy to compute good upper bounds in practice, i.e., good choices of f . This is based on earlier work by Chen [START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF].

Open problem. Our lower bounds are specific to cylinder pruning [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]. It would be interesting to obtain tight lower bounds for discrete pruning [START_REF] Aono | Random sampling revisited: Lattice enumeration with discrete pruning[END_REF].

Roadmap. In Section 2, we introduce background and notation on lattices, enumeration and its cost estimations. Section 3 presents our lower bounds as geometric properties of cylinder intersections. Section 4 shows how to obtain good upper bounds in practice, by finding nice cylinder intersections using crossentropy. Finally, in Section 5, we evaluate the tightness of our lower bounds and discuss security estimates for the hardness of finding nearly shortest lattice vectors. The appendix includes proofs of technical results. The full version of this paper on eprint also includes sage scripts to compute our lower bounds.

Background

Notation

Throughout the paper, we use row representations of matrices. The Euclidean

norm of a vector v ∈ R n is denoted v . The 'canonical' projection of u ∈ R n onto R k for 1 ≤ k ≤ n is the truncation τ k (u) = (u 1 , . . . , u k ).
Measures. We denote by vol the standard Lebesgue measure over R n . We denote by ρ n,σ the centered Gaussian measure of variance σ 2 , whose pdf over R n is (2πσ 2 ) -n/2 e -x 2 /(2σ 2 ) .

The standard Gaussian measure is ρ n = ρ n,1 .

Balls. We denote by Ball n (R) the n-dimensional zero-centered ball of radius R.

Let V n (R) = vol(Ball n (R))
. Let u = (u 1 , . . . , u n ) be a point chosen uniformly at random from the unit sphere S n-1 , e.g. u i = x i / ∑ n j=1 x 2 j , where x 1 , . . . , x n are independent, normally distributed random variables with mean 0 and variance

1. Then τ k (u) 2 = ∑ k i=1 x 2 i ∑ k i=1 x 2 i +∑ n i=k+1 x 2 i = X X+Y
, where X and Y have distributions Gamma(k/2, θ = 2) and Gamma((nk)/2, θ = 2) respectively. Here, we use the scale parametrization to represent Gamma distributions. Hence, τ k (u) 2 has distribution Beta(k/2, (nk)/2). In particular, τ n-2 (u) 2 has distribution Beta(n/2 -1, 1), whose pdf is x (n/2)-2 /B(n/2 -1, 1) = (n/2 -1)x (n/2)-2 . It follows that the truncation τ n-2 (u) is uniformly distributed over Ball n-2 [START_REF] Ajtai | A sieve algorithm for the shortest lattice vector problem[END_REF], which allows to transfer our results to random points in balls.

Recall that the cumulative distribution function of the Beta(a, b) distribution is the regularized incomplete beta function I x (a, b) defined as:

I x (a, b) = 1 B(a, b) x 0 u a-1 (1 -u) b-1 du, (1)
where B(a, b) = Γ(a)Γ(b) Γ(a+b) denotes the beta function. We have the following elementary bounds (by integrating by parts):

x a (1 -x) b-1 aB(a, b) ≤ I x (a, b) ∀a > 0, b ≥ 1, 0 ≤ x ≤ 1 (2)
I x (a, b) ≤ x a a • B(a, b) ∀a > 0, b ≥ 1, 0 ≤ x ≤ 1 (3) For z ∈ [0, 1] and a, b > 0, I -1 z (a, b) + I -1 1-z (b, a) = 1 which is immediate from the relation I x (a, b) + I 1-x (b, a) = 1.
Finally, P(s, x) = x 0 t s-1 e -t dt/Γ(s) is the regularized incomplete gamma function.

Lattices. A lattice L is a discrete subgroup of R m , or equivalently the set L(b 1 , . . . , b n ) = {∑ n i=1 x i b i : x i ∈ Z} of all integer combinations of n linearly independent vectors b 1 , . . . , b n ∈ R m . Such b i 's form a basis of L. All the bases of L have the same number n of elements, called the dimension or rank of L, and the same n-dimensional volume of the parallelepiped {∑ n i=1 a i b i : a i ∈ [0, 1)} they generate. We call this volume the co-volume, or determinant, of L, and denote it by covol(L). The lattice L is said to be full-rank if n = m. The most famous lattice problem is the shortest vector problem (SVP), which asks to find a non-zero lattice vector of minimal Euclidean norm. The closest vector problem (CVP) asks to find a lattice vector closest to a target vector.

Orthogonalization. For a basis B = (b 1 , . . . , b n ) of a lattice L and i ∈ {1, . . . , n}, we denote by π i the orthogonal projection on span(b 1 , . . . , b i-1 ) ⊥ . The Gram-Schmidt orthogonalization of the basis B is defined as the sequence of orthogonal vectors B = (b 1 , . . . , b n ), where b i := π i (b i ). We can write each b i as b i + ∑ i-1 j=1 µ i,j b j for some unique µ i,1 , . . . , µ i,i-1 ∈ R. Thus, we may represent the µ i,j 's by a lower-triangular matrix µ with unit diagonal. The projection of a lattice may not be a lattice, but

π i (L) is an n + 1 -i dimensional lattice gener- ated by π i (b i ), . . . , π i (b n ), with covol(π i (L)) = ∏ n j=i b j .
The Gaussian Heuristic. For a full-rank lattice L in R n and a measurable set C ⊂ R n , the Gaussian heuristic estimates the number of lattice points inside of C to be approximately vol(C)/vol(L). Accordingly, we would expect that λ 1 (L) might be close to GH(L) = V n (1) -1/n vol(L) 1/n , which holds for a random lattice L.

Cylinders. The performances of cylinder pruning are directly related to the following bodies. Define the (k-dimensional) cylinder-intersection of radii

R 1 ≤ • • • ≤ R k as the set C R 1 ,...,R k = (x 1 , . . . , x k ) ∈ R k , ∀j ≤ k, j ∑ =1 x 2 ≤ R 2 j ⊆ Ball k (R k ).
Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] showed how to efficiently compute tight lower and upper bounds for vol(C R 1 ,...,R k ), thanks to the Dirichlet distribution and special integrals.

Enumeration with Cylinder Pruning

To simplify notations, we assume that we focus on the SVP setting, i.e. to find short lattice vectors, rather than the more general CVP setting. Let L be a fullrank lattice in R n . Given a basis B = (b 1 , . . . , b n ) of L and a radius R > 0, Enumeration [START_REF] Pohst | On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications[END_REF][START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF][START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF] outputs L ∩ S where S = Ball n (R) by a depth-first tree search: by comparing all the norms of the vectors obtained, one extracts a shortest non-zero lattice vector. We follow the general pruning framework of [START_REF] Aono | Random sampling revisited: Lattice enumeration with discrete pruning[END_REF], which replaces S by a subset of S depending on B. Given a function f : {1, . . . , n} → [0, 1], Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] introduced the following set to generalize the pruned enumeration of [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]:

P f (B, R) = {x ∈ R n s.t. π n+1-i (x) ≤ f (i)R for all 1 ≤ i ≤ n}, (4)
where the π i is the projection over span(b 1 , . . . , b i-1 ) ⊥ . The set P f (B, R) should be viewed as a random variable. Note that P f (B, R) ⊆ Ball n (R) and if g is the constant function equal to 1, then P g (B, R) = Ball n (R).

Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] noticed that the basic enumeration algorithm can actually compute L ∩ P f (B, R) instead of L ∩ Ball n (R), just by changing its parameters. We call cylinder pruning this form of pruned enumeration, because P f (B, R) is an intersection of cylinders, since each equation π n+1-i (x) ≤ f (i)R defines a cylinder. Cylinder pruning was historically introduced in the SVP setting, but its adaptation to CVP is straightforward, as was shown by Liu and Nguyen [START_REF] Liu | Solving BDD by enumeration: An update[END_REF].

Complexity of Enumeration. The advantage is that for suitable choices of f , enumerating L ∩ P f (B, R) is much cheaper than enumerating L ∩ Ball n (R): indeed, [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] shows that cylinder pruning runs in ∑ n k=1 N k poly-time operations, where N k is the number of points of π n+1-k (L ∩ P f (B, R)): this is because N k is exactly the number of nodes at depth nk + 1 of the enumeration tree which is searched by cylinder pruning. By the Gaussian heuristic, we have heuristically N k ≈ H k where:

H k = vol(π n+1-k (P f (B, R))) covol(π n+1-k (L)) = vol(C R f (1),...,R f (k) ) covol(π n+1-k (L)) .
It follows that the complexity of cylinder pruning is heuristically:

N = n ∑ k=1 vol(C R f (1),...,R f (k) ) ∏ n i=n-k+1 b i (5)
This N is a heuristic estimate of the number of nodes in the tree searched by cylinder pruning. It depends on one hand on R and the bounding function f , but on the other hand on the quality of the basis B, because of the term ∏ n i=n-k+1 b i . In the SVP setting, one can further divide (5) by two, because of symmetries in the enumeration tree. Success Probability. We consider two settings: Approximation Setting: The algorithm is successful if and only if we find at least one non-zero point of

L ∩ P f (B, R), that is L ∩ P f (B, R) ⊆ {0}
. This is the situation studied in [START_REF] Aono | Random sampling revisited: Lattice enumeration with discrete pruning[END_REF] and corresponds to the use of cylinder pruning in blockwise lattice reduction. By the Gaussian heuristic, the number of points of L ∩ P f (B, R) is heuristically:

vol(P f (B, R)) covol(L) = vol(C R f (1),...,R f (n) ) covol(L) .
So we estimate the probability of success as:

Pr succ = min 1, vol(C R f (1),...,R f (n) ) covol(L) . ( 6
) Since covol(L) = V n (GH(L)), if R = βGH(L), then (6) becomes Pr succ = min 1, β n vol(C R f (1),...,R f (n) ) V n (R) . ( 7
)
Unique Setting: This corresponds to the situation studied in [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] and to bounded distance decoding (BDD). There is a secret vector v ∈ L, whose distribution is assumed to be the Gaussian distribution over R n of parameter σ. The algorithm is successful if and only if v is returned by the algorithm, i.e. if and only if v ∈ P f (B, R). So we estimate the probability of success as:

Pr succ = ρ n,σ (P f (B, R)) = ρ n,σ (C f (1)R,..., f (n)R ). ( 8
)

Lower Bounds for Cylinder Pruning

In this section, we prove novel geometric properties of cylinder intersections: if a cylinder intersection is sufficiently big (with respect to its volume or its Gaussian measure), we can lower bound the radii defining the intersection, as well as the volume of all its canonical projections, which are also cylinder intersections.

A basic ingredient behind these properties is a special case of cylinder intersections, corresponding to the step-bounding functions used in [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]. More precisely, we consider the intersection of a ball with a cylinder, which we call a ball-cylinder:

D k,n (R, R ) = (x 1 , . . . , x n ) ∈ R n , k ∑ l=1 x 2 l ≤ R 2 and n ∑ l=1 x 2 l ≤ R 2 .
In other words, D k,n (R, R ) = C R,...,R,R ,...,R where R is repeated k times, and R is repeated nk times. The following result is trivial:

Lemma 1. Let R 1 ≤ R 2 ≤ • • • ≤ R n and 1 ≤ k ≤ n. Then: C R 1 ,...,R n ⊆ D k,n (R k , R n ).
Note that for fixed k, n and R , vol

(D k,n (R, R )) is an increasing function of R.
The following lemma gives properties of the volume and Gaussian measures of ball-cylinders, based on the background:

Lemma 2. Let R ≤ R and 1 ≤ k ≤ n. Then: vol(D k,n (R, R )) = V n (R ) × I (R/R ) 2 (k/2, 1 + (n -k)/2) ρ k,σ (Ball k (R)) ≥ ρ n,σ (D k,n (R, R )) ≥ ρ k,σ (Ball k (R))ρ n,σ (Ball n (R )) ρ n,σ (Ball n (R)) = P(n/2, R 2 /(2σ 2 )) Proof. Because D k,n (R, R ) ⊆ Ball n (R ), vol(D k,n (R, R ))/V n (R )
is the probability that a random vector (x 1 , . . . , x n ) (chosen uniformly at random from the n-dimensional ball of radius R ) satisfies 2 . It follows that this probability is also the probability that a random vector (y 1 , . . . , y n ) (chosen uniformly at random from the n-dimensional unit ball) satisfies:

∑ k l=1 x 2 l ≤ R 2 , that is, ∑ k l=1 (x l /R ) 2 ≤ (R/R )
∑ k l=1 y 2 l ≤ (R/R ) 2 .
From the background, we know that ∑ k l=1 y 2 l has distribution Beta(k/2, (n + 2k)/2), which proves the first equality.

Note that D k,n (R, R ) ⊆ D k,n (R, +∞), which proves that ρ n,σ (D k,n (R, R )) ≤ ρ k,σ (Ball k (R))
. Furthermore, by the Gaussian correlation inequality on convex symmetric sets, we have:

ρ n,σ (D k,n (R, R )) ≥ ρ n,σ (Ball n (R )) × ρ n,σ {(x 1 , . . . , x n ) ∈ R n : k ∑ i=1 x 2 i ≤ R 2 } = ρ k,σ (Ball k (R))ρ n,σ (Ball n (R )) which proves that ρ n,σ (D k,n (R, R )) ≥ P(k/2, R 2 /(2σ 2 ))P(n/2, R 2 /(2σ 2 )).
Finally, let x 1 , . . . , x n be independent, normally distributed random variables with mean 0 and variance 1.

Then X = ∑ n i=1 x 2 i has the distribution Gamma(n/2, θ = 2) whose CDF is P(n/2, x/2). Therefore ρ n (Ball n (R)) = P(n/2, R 2 /2).

Lower Bounds on Cylinder Radii

The following theorem lower bounds the radii of any cylinder intersection covering a fraction of the ball:

Theorem 1. Let 0 ≤ R 1 ≤ • • • ≤ R n be such that vol(C R 1 ,...,R n ) ≥ αV n (R n ), where 0 ≤ α ≤ 1. If for all 1 ≤ k ≤ n, we define α k > 0 by I α k (k/2, 1 + (n -k)/2) = α, then vol(D k,n ( √ α k R n , R n )) ≤ vol(C R 1 ,...,R n ) and: R k ≥ √ α k R n .
Proof. Lemma 1 shows that:

vol(C R 1 ,...,R n ) ≤ vol(D k,n (R k , R n )).
On the other hand, Lemma 2 shows that by definition of α k :

vol(D k,n ( √ α k R n , R n )) = V n (R n ) × I α k k 2 , 1 + n -k 2 = αV n (R n ) ≤ vol(C R 1 ,...,R n ),
which proves the first statement. Hence:

vol(D k,n ( √ α k R n , R n )) ≤ vol(D k,n (R k , R n )), which implies that R k ≥ √ α k R n .
The parameter α in Th. 1 is directly related to our success probability [START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] in the approximation setting: indeed, if R n = βGH(L) and Pr succ ≥ γ, then α = γ/β n satisfies the condition of Th. 1. We have the following Gaussian analogue of Th. 1, where the lower bound on the volume is replaced by a lower bound on the Gaussian measure:

Theorem 2. Let 0 ≤ R 1 ≤ • • • ≤ R n be such that ρ n,σ (C R 1 ,...,R n ) ≥ β, where 0 ≤ β ≤ 1. If for all 1 ≤ k ≤ n we define β k > 0 by P(k/2, β k /(2σ 2 )) = β, then ρ n,σ (D k,n ( β k , R n )) ≤ ρ n,σ (C R 1 ,...,R n ) and R k ≥ β k .
Proof. On the one hand, Lemma 1 shows that:

ρ n,σ (C R 1 ,...,R n ) ≤ ρ n,σ (D k,n (R k , R n )).
On the other hand, Lemma 2 shows that by definition of β k :

ρ n,σ (D k,n ( β k , R n )) ≤ P(k/2, β k /2(σ 2 )) = β ≤ ρ n,σ (C R 1 ,...,R n ),
which proves the first statement. Hence:

ρ n,σ (D k,n ( β k , R n )) ≤ ρ n,σ (D k,n (R k , R n )), which implies that R k ≥ β k .
In Th. 2, β can be chosen as any lower bound on the success probability in the unique setting [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF].

Th. 1 allows to derive numerical lower bounds on the radii, from any lower bound on the success probability. However, there is a special case for which the lower bound has a simple algebraic form, thanks to the following technical lemma (proved in Appendix A):

Lemma 3. If 1 ≤ k ≤ n, then: 1 -P(1/2, 1/2) ≤ I k/n (k/2, (n -k)/2) ≤ P(1/2, 1/2) (9)
By coupling Th. 1 and Lemma 3, we obtain that the squared radii of any highvolume cylinder intersection are lower bounded by linear functions:

Theorem 3. Let 0 ≤ R 1 ≤ • • • ≤ R n such that vol(C R 1 ,...,R n ) ≥ P(1/2, 1/2) × V n (R n ). Then for all 1 ≤ k ≤ n: R k ≥ k n + 2 R n .
Proof. The assumption and (9) imply that

vol(C R 1 ,...,R n ) ≥ I k/(n+2) (k/2, 1 + (n -k)/2)V n (R n ).
Hence, we can apply Th. 1 with α k = k/(n + 2).

Note that P(1/2, 1/2) ≈ 0.683 . . . , so any bounding function with high success probability must have a cost lower bounded by that of some linear pruning, which means that its speed-up (compared to full enumeration) is at most singleexponential (see [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]).

Lower Bounds on Cylinder Volumes from Isoperimetry

The lower bounds on radii given by Th. 1 and 2 provide lower bounds on vol

(C R 1 ,...,R k ) for all 1 ≤ k ≤ n -1. Indeed, if R k ≥ √ α k R n , then: vol(C R 1 ,...,R k ) ≥ vol(C √ α 1 R n ,..., √ α k R n ).
Such lower bounds immediately provide a lower bound on the cost of enumeration with cylinder pruning, because of [START_REF] Aono | Random sampling revisited: Lattice enumeration with discrete pruning[END_REF].

In this subsection, we show that this direct lower bound can be significantly improved, namely it can be replaced by

V k ( √ α k R n ).
Our key ingredient is the following isoperimetric result, which says that among all Borel sets of given volume, the ball centered at the origin has the largest measure, for any isotropic measure which decays monotonically radially away : Theorem 4 (Isoperimetry). Let A be a Borel set of R k . Let D be a distribution over R k such that its probability density function f is radial and decays monotonically radially away: f (x) ≤ f (y) whenever x ≥ y . If a random variable X has distribution D, then:

Pr(X ∈ A) ≤ Pr(X ∈ B),
where B is the ball of R k centered at the origin such that vol(B) = vol(A).

Proof. The statement is proved in [38, p498-499] for the special case where D is the Gaussian distribution over R k . However, the proof actually works for any radial probability density function which decays monotonically radially away.

It implies the following:

Lemma 4. Let 1 ≤ k ≤ n. Let π = τ k be the canonical projection of R n over R k .
Let C be a subset of the n-dimensional ball of radius R such that both C and π(C) are measurable. If R is the radius of the k-dimensional ball of volume vol(π(C)), then:

vol(C) ≤ vol(D k,n (R, R )) and ρ n,σ (C) ≤ ρ n,σ (D k,n (R, R )).
Proof. Let B be the n-dimensional centered ball of radius R . Let B be the kdimensional centered ball of radius R. Let x be chosen uniformly at random from B . Since C ⊆ B , vol(C)/V n (R ) is exactly Pr(x ∈ C), and we have:

Pr(x ∈ C) ≤ Pr(π(x) ∈ π(C)).
Let D be the distribution of y = π(x) ∈ R k . Then by Th. 4,

Pr(y ∈ π(C)) ≤ Pr(y ∈ B).
Hence:

Pr(x ∈ C) ≤ Pr(y ∈ B) = vol(D k,n (R, R )) V n (R ) ,
which proves the first statement. Similarly, if x is chosen from the Gaussian distribution corresponding to ρ n,σ , then

ρ n,σ (C)/ρ n,σ (B ) = Pr(x ∈ C) ≤ Pr(π(x) ∈ π(C)).
Let D be the distribution of y = π(x) ∈ R k : this is a Gaussian distribution. Then by Th. 4,

Pr(y ∈ π(C)) ≤ Pr(y ∈ B) = ρ n,σ (D k,n (R, R )) ρ n,σ (B ) .
It has the following geometric consequence:

Corollary 1. Let R 1 ≤ R 2 ≤ • • • ≤ R n and 1 ≤ k ≤ n. Let R > 0 such that vol(C R 1 ,...,R n ) ≥ vol(D k,n (R, R n )) or ρ n,σ (C R 1 ,...,R n ) ≥ ρ n,σ (D k,n (R, R n ))
. Then:

vol(C R 1 ,...,R k ) ≥ V k (R). Proof. Let C = C R 1 ,...,R n and π = τ k be the canonical projection of R n over R k . Then π(C) = C R 1 ,...,R k . If r is the radius the k-dimensional ball of volume vol(π(C)), Lemma 4 implies that: vol(C) ≤ vol(D k,n (r, R n )) and ρ n,σ (C) ≤ ρ n,σ (D k,n (r, R n )). Thus, by definition of R, we have either vol(D k,n (R, R n )) ≤ vol(C) ≤ vol(D k,n (r, R n )) or ρ n,σ (D k,n (R, R n )) ≤ ρ n,σ (C) ≤ ρ n,σ (D k,n (r, R n )),
which each imply that r ≥ R.

Note that C R 1 ,...,R k and Ball k (R) are the projections of respectively C R 1 ,...,R n and D k,n (R, R n ) over R k . So the corollary is a bit surprising: if one particular body is "bigger" than the other, then so are their projections. Obviously, this cannot hold for arbitrary bodies in the worst case. This corollary implies the following lower bounds, which strengthens Theorem 1: Corollary 2. Under the same assumptions as Th. 1, we have:

vol(C R 1 ,...,R k ) ≥ V k ( √ α k R n ).
Proof. From Th. 1, we have: vol

(C R 1 ,...,R n ) ≥ vol(D k,n ( √ α k R n , R n )).
And we apply Cor. 1.

Similarly, we obtain: Corollary 3. Under the same assumptions as Th. 2, we have:

vol(C R 1 ,...,R k ) ≥ V k ( β k R n ).
It would be interesting to study if the lower bounds of the last two corollaries can be further improved.

Generalisation to Finitely Many Cylinder Intersections

In this section, we give an analogue of the results of Sect. 3.2 to finitely many cylinder intersections, which corresponds to the extreme pruning setting. The key ingredient is the following refinement of isoperimetry: Theorem 5 (Isoperimetry). Let A 1 , . . . , A m be Borel sets of R k . Let D be a distribution over R k such that its probability density function f is radial and decays monotonically radially away: f (x) ≤ f (y) whenever x ≥ y . If a random variable X has distribution D, then:

1 m m ∑ i=1 Pr(X ∈ A i ) ≤ Pr(X ∈ B),
where B is the ball of R k centered at the origin such that vol(B) = 1 m ∑ m i=1 vol(A i ).

Proof. The statement is proved in [38, p499-500] for the special case where D is the Gaussian distribution over R k . However, the proof actually works for any radial probability density function which decays monotonically radially away.

Lemma 5. Let 1 ≤ k ≤ n. Let π = τ k be the canonical projection of R n over R k . Let C 1 , . . . , C m ⊆ Ball n (R ) such that all the C i 's and π(C i )'s are measurable. If R is the radius of the k-dimensional ball of volume 1 m ∑ m i=1 vol(π(C i )), then: 1 m m ∑ i=1 vol(C i ) ≤ vol(D k,n (R, R )) and 1 m m ∑ i=1 ρ n,σ (C i ) ≤ ρ n,σ (D k,n (R, R )).
Proof. Let B be the n-dimensional centered ball of radius R . Let B be the kdimensional centered ball of radius R such that vol(B) = 1 m ∑ m i=1 vol(π(C i )). Let x be chosen uniformly at random from B . Since C i ⊆ B , vol(C i )/V n (R ) is exactly Pr(x ∈ C i ), and we have:

Pr(x ∈ C i ) ≤ Pr(π(x) ∈ π(C i )).
Let D be the distribution of y = π(x) ∈ R k . Then by Th. 5,

1 m m ∑ i=1 Pr(y ∈ π(C i )) ≤ Pr(y ∈ B). Hence: 1 m m ∑ i=1 Pr(x ∈ C i ) ≤ Pr(y ∈ B) = vol(D k,n (R, R )) V n (R ) ,
which proves the first statement.

It has the following geometric consequence:

Corollary 4. Let C 1 , . . . , C m ⊆ Ball n (R n ) be n-dimensional cylinder intersections. Let 1 ≤ k ≤ n and denote by π = τ k the canonical projection of R n over R k . Let R > 0 such that 1 m ∑ m i=1 vol(C i ) ≥ vol(D k,n (R, R n )) or 1 m ∑ m i=1 ρ n,σ (C i ) ≥ ρ n,σ (D k,n (R, R n )). Then: 1 m m ∑ i=1 vol(π(C i )) ≥ V k (R). Proof. If r is the radius of the k-dimensional ball of volume 1 m ∑ m i=1 vol(π(C i )), the Lemma 5 implies that: 1 m ∑ m i=1 vol(C i ) ≤ vol(D k,n (r, R n )) and 1 m ∑ m i=1 ρ n,σ (C i ) ≤ ρ n,σ (D k,n (r, R n )). Thus, by definition of R, we have either vol(D k,n (R, R n )) ≤ vol(C) ≤ vol(D k,n (r, R n )) or ρ n,σ (D k,n (R, R n )) ≤ ρ n (C) ≤ ρ n,σ (D k,n (r, R n )), which each imply that r ≥ R. Theorem 6. Let C 1 , . . . , C m ⊆ Ball n (R n ) be n-dimensional cylinder intersections such that ∑ m i=1 vol(C i ) ≥ mαV n (R n ), where 0 ≤ α ≤ 1. If for all 1 ≤ k ≤ n, we define α k > 0 by I α k (k/2, 1 + (n -k)/2) = α, then vol(D k,n ( √ α k R n , R n )) ≤ 1 m ∑ m i=1 vol(C i ) and: m ∑ i=1 vol(π(C i )) ≥ mV k ( √ α k R n ),
where π = τ k denotes the canonical projection of R n over R k .

Proof. Lemma 2 shows that by definition of α k :

vol(D k,n ( √ α k R n , R n )) = αV n (R n ) ≤ 1 m m ∑ i=1 vol(C i ),
which proves the first statement. And the rest follows by Lemma 4.

Again, the parameter α in Th. 6 is directly related to our global success probability [START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] in the approximation setting: the global success probability is ≤ ∑ m i=1 vol(C i )/covol(L) so if R n = βGH(L) and the global success probability is ≥ γ, then α = γ/(mβ n ) satisfies the condition of Th. 1.

We have the following Gaussian analogue of Th. 6:

Theorem 7. Let C 1 , . . . , C m ⊆ Ball n (R n ) be n-dimensional cylinder intersections such that ∑ m i=1 ρ n,σ (C i ) ≥ mβ, where 0 ≤ β ≤ 1/m. If for all 1 ≤ k ≤ n, we define β k > 0 by P(k/2, β k /(2σ 2 )) = β, then ρ n,σ (D k,n ( β k R n , R n )) ≤ 1 m ∑ m i=1 ρ n,σ (C i ) and: m ∑ i=1 vol(π(C i )) ≥ mV k (β k ),
where π = τ k denotes the canonical projection of R n over R k .

In the unique setting, the global success probability is ≤ ∑ m i=1 ρ n,σ (C i ), so if the global success probability is ≥ γ, then β = γ/m satisfies the condition of Th. 7.

Surprisingly, we will show that Th. 6 and 7 imply that we can lower bound the cost of extreme pruning, independently of the number m of cylinder intersections:

Lemma 6. Let the global probability 0 ≤ α ≤ 1 and 1 ≤ k ≤ n. Let α = α /m and α k > 0 such that I α k (k/2, 1 + (n -k)/2) = α. Then, mV k ( √ α k
) is strictly decreasing w.r.t. m, yet lower bounded by some linear function of α :

mV k ( √ α k ) > α • kV k (1) 2 • B k 2 , 1 + n -k 2 .
Furthermore, for fixed α , k and n, the left-hand side converges to the right-hand side when m goes to infinity and α k is defined as above.

Lemma 6 implies that the cost of enumeration decreases as the number of cylinder intersections increases, if the global probability α is fixed. However, there is a limit given by some linear function of α which depends only on n.

To prove the lemma, we use the following two lemmas: 3) we obtain:

Lemma 7. For a ≥ 0, b ≥ 1, 0 < z ≤ 1: ∂ ∂z I -1 z (a, b) ≥ 1 az I -1 z (a, b) Proof. Substituting x = I -1 z (a, b) in (
(1

-I -1 z (a, b)) b-1 (I -1 z (a, b)) a aB(a, b) ≤ z.
This implies that

∂ ∂z I -1 z (a, b) = B(a, b)(1 -I -1 z (a, b)) 1-b (I -1 z (a, b)) 1-a ≥ 1 az I -1 z (a, b). Lemma 8. For a ≥ 0, b ≥ 1: lim y→0+ y (I -1 y (a, b)) a = 1 a • B(a, b)
Proof. Bounding inequalities (2) and (3) from both sides implies that a,b) .

lim x→0+ I x (a, b) x a = 1 a • B(
Letting x = I -1 y (a, b), the claim holds.

Proof of Lemma 6

We have

I α k (k/2, 1 + (n -k)/2) = α /m and α k = I -1 α /m (k/2, 1 + (n -k)/2
). This gives:

mV k ( √ α k ) = V k (1)m • I -1 α /m (k/2, 1 + (n -k)/2) k/2
. Thus, to show the first claim, it suffices to prove that

g(y) = 1 y I -1 α y (k/2, 1 + (n -k)/2) k/2
is strictly increasing over 0 < y ≤ 1.

For simplicity, we write I := I -1 α y (k/2, 1 + (nk)/2) and we have:

g (y) = α k 2y I k/2-1 • ∂I ∂y - I k/2 y 2
By Lemma 7, we can see that ∂I ∂y ≥ 2 α ky > I and g (y) > 0 which proves the first claim. The lower bound can be derived by the limit of the function. By the relationship lim

m→∞ mV k ( √ α k ) = V k (1) • lim y→0+ g(y),
and the straightforward consequence of Lemma 8,

lim y→0+ g(y) = α • k 2 • B k 2 , 1 + n -k 2 ,
we obtain the second claim. By a similar technique, we can show a similar result for the Gaussian case: the proof is postponed to Appendix A.3.

Lemma 9.

Let the global probability 0 ≤ β ≤ 1 and 1 ≤ k ≤ n. Let β = β /m and β k > 0 such that P(k/2, β k /(2σ 2 )) = β. Then, mV k ( β k ) is strictly decreasing w.r.t. m, yet lower bounded by some linear function of β :

mV k ( β k ) > β (2πσ 2 ) k/2 .
Moreover, for fixed β , k and σ, the left-hand side converges to the right-hand side when m goes to infinity and β k is defined as above.

Efficient Upper Bounds based on Cross-Entropy

In order to guess how tight are our lower bounds in practice, we need to be able to find efficiently very good bounding functions for cylinder pruning. Different methods have been used over the years (see [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF][START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF][START_REF] Cadé | FPLLL library, version 3.0[END_REF]). In this section, we present the method that we used to generate bounding functions that try to minimize the enumeration cost, under the constraint that the success probability is greater than a given p 0 > 0. From our experience, different methods usually give rise to close bounding functions, but their running time can vary significantly.

Our Formulation and Previous Algorithms

Usually, the problem to find optimal cost has two formulations and our algorithm targets the first one:

1. [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] for a given basis B, radius R, and target probability p 0 , minimize the cost (5) subject to the constraint that the probability ( 6) is greater than p 0 . The variables are R 1 , . . . , R n . This kind of constrained optimization is known as monotonic optimization because the objective function and constraint functions are both monotonic, i.e., f (x 1 , . . . ,

x n ) ≤ f (x 1 , . . . , x n ) if x i ≤ x i for all i.
It is known that the optimal value is on the border (see, for example [START_REF] Cheon | Global Optimization of Monotonic Programs: Applications in Polynomial and Stochastic Programming[END_REF]). A heuristic random perturbation is implemented in the progressive BKZ library [START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF], and an outline of the cross-entropy method is mentioned in Chen's thesis [START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF]. 2. [START_REF] Cadé | FPLLL library, version 3.0[END_REF] for a given basis B and radius, minimize the expected cost of extreme pruning [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]:

m • EnumCost + (m -1)
• PreprocessCost where m is a variable defining the number of bases, and therefore the success probability of the enumeration. The variables are R 1 , . . . , R n and m. This is an unconstrained optimization problem. A heuristic gradient descent and the Nelder-Mead method are implemented in the fpLLL library [START_REF] Cadé | FPLLL library, version 3.0[END_REF].

We explain why we introduce a new approach. All the known approaches try to minimize an approximate upper bound of the enumeration cost: this approximation is the sum of n terms, where each term can be derived from the computation of a simplex volume (following [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]) which costs O(n 2 ), where the unit is number of floating-point operations and the required precision might be linear in n. Although there exists an O(n 2 ) algorithm to compute the approximate upper bound [4, Section 3.3], a naive random perturbation strategy is too slow to converge.

Besides, we think that the Nelder-Mead and gradient descent are not suitable for our optimization problem. If we want to apply such methods to the constrained problem, a usual approach converts the problem into a corresponding global optimization problem by introducing penalty functions. Then, we find a near-optimal solution to the original problem by using the optimized variable of the converted problem. However, we know that the optimal point is on the border at which the penalty functions must change drastically. It could make the optimal point of the new problem far from the original one. Hence, we need an algorithm to solve our constrained problem directly.

For this purpose, we revisit Chen's partial description [START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF] of the crossentropy method to solve the problem (i). In Section 4.2, we give a brief overview of the cross-entropy method, and in Section 4.3, we explain how we modify it for our purpose.

A Brief Introduction to the Cross Entropy Method

The original motivation of the cross entropy method is to speed up Monte-Carlo simulation for approximating a probability. If the target probability is extremely small, the number of sampling points must be huge. To solve this issue, Rubinstein [START_REF] Rubinstein | Optimization of computer simulation models with rare events[END_REF] introduced the cross entropy method and showed that the algorithm could be used for combinatorial optimization problems. This subsection gives a general presentation of the cross-entropy method: we will apply it to the optimization of pruning functions. For more information, see for example [START_REF] Rubinstein | Optimization of computer simulation models with rare events[END_REF][START_REF] De Boer | A tutorial on the crossentropy method[END_REF].

Let χ be the whole space of combinations and consider a cost function S : χ → R ≥0 that we want to minimize. Assume that we have a probability distribution D χ,u defined over χ and parametrized by a vector u. We fix the corresponding probability density function f u (x). A cross-entropy algorithm to find the optimal combination X * := argmin X∈χ S(X) is outlined in Algorithm 1; here we use the description in the textbook [14, Algorithm 2.3].

Algorithm 1 A Generic Framework of the Cross-Entropy Method

Input: Searching space χ,cost function S : χ → R ≥0 , initial parameter vector v 0 , algorithm parameter ρ, N, d;for example, N = 1000, ρ = 0.1 and d = 10. Output: An approximation S(x * ) of the minimal and corresponding x * .

1: t ← 1 2: According to D χ,v t-1 , sample X 1 , . . . , X N from χ 3: Let the threshold γ t be the ρN -th smallest value of S(X i ) 4: Solve the stochastic program [START_REF] Chen | Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe[END_REF] for the inputs (X 1 , . . . , X N , γ t , v t-1 ) and find the new parameter v t 5: if the found minimum S(X * ) during the execution of the algorithm is not updated in the last d loop then

v N ∑ i=1 I S(X i )≤γ t log f v (X i ) (10)
where

I S(X i )≤γ t = 1 if S(X i ) ≤ γ t 0 if S(X i ) > γ t
is the characteristic function. It is known that the new distribution D χ,v t derived from the solution is closer to the ideal distribution D χ,opt that outputs the optimal X opt = arg min X S(X) with probability 1, than the previous distribution D χ,v t-1 . In other words, the cost of sampled elements from D χ,v t are likely to smaller than that of samples from D χ,v t-1 . This is quantified by the function to measure the distance between two probability distributions:

D(g, f v ) := g(x) log g(x) f v (x) dx
which is known as the cross-entropy, or Kullback-Leibler distance. The above algorithm wants to minimize the distance from the optimal state g by changing the parameter vector v.

The stochastic program (10) can be easily solved analytically if the family of distribution function { f v (x)} v∈V is a natural exponential family (NEF) [START_REF] Rubinstein | The Cross-Entropy Method, A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning[END_REF]. In particular, if the function f v (x) is convex and differentiable with respect to v, the solution of ( 10) is obtained by solving the simultaneous equations

N ∑ i=1 I S(X i )≤γ t ∇ log f v (X i ) = 0. (11)
The Gaussian product (12) used in the next section is one of the simplest examples of such functions.

Our Algorithm

For the generic algorithm (Algorithm 1), we substitute our cost function and constraints. Then, we modify the sampler and introduce the FACE strategy as explained in this section. Recall that the input is a lattice basis and its Gram-Schmidt lengths, a radius R and a target probability p 0 . We mention that our algorithm follows [START_REF] Kroese | The cross-entropy method for continuous multi-extremal optimization[END_REF]Algorithm 2] for optimization over a subset of R m by Kroese, Porotsky and Rubinstein.

Modified sampler:

The sampling parameter is u = (c 1 , . . . , c n-1 , σ 1 , . . . , σ n-1 ) ∈ R 2n-2 ≥0 where c and σ correspond to the center and deviation respectively. Since the bounding radii must increase and the last coordinate is R n = 1, the searching space is

χ = {(x 1 , . . . , x n-1 ) ∈ (0, 1] n : x 1 ≤ x 2 ≤ • • • ≤ x n-1 } ⊂ R n-1 .
To sample from the space following the parameter u, define the corresponding probability distribution D χ,u as follows: sample each u i from N(c i , σ 2 i ) independently, if all u i ≥ 0, then let (x 1 , . . . , x n ) be (u 1 , . . . , u n ) sorted in increasing order and output it. We sort the output because because we do not know a suitable distribution from which the sampling from χ is easy. As we will see later, when the algorithm is about to converge, the Gaussian parameters σ i become small, and the distributions of u i 's and x i become close. Below we assume that the probability density function of D χ,u is sufficiently close to that of the Gaussian product

f u (X) = 1 (2π) n/2 n-1 ∏ i=1 1 σ i exp(-(x i -c i ) 2 /(2σ 2 i )) . ( 12
)
The gradients of log of the function are

∂ ∂c i log f u (X) = x i -c i σ 2 i , and
∂ ∂σ i log f u (X) = - 1 σ i + (x i -c i ) 2 σ 3 i .
Substituting them into [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF], we obtain the formulas to update c i and σ i as follows

c new i ← ∑ j:S(X j )≤γ t x j,i |{j : S(X j ) ≤ γ t }| σ new i ← ∑ j:S(X j )≤γ t (x j,i -c i ) 2 |{j : S(X j ) ≤ γ t }| (13)
where we denote x j,i for the i-th coordinate of X j .

The FACE strategy: For practical speedup, we can employ the fully-automated cross-entropy (FACE) strategy described in [START_REF] De Boer | A tutorial on the crossentropy method[END_REF]Section 4.2]. It simply replaces the full sampling in Step 2 in Figure 1 by a recycling strategy. Consider a list L = {X 1 , . . . , X N }. If the cost of a new sample is less than max i∈[N] S(X i ), replace the new sample to the maximum element in the list, and update the parameter vector by ( 13) using all items in the list, i.e., with γ t = +∞.

We did preliminary experiments on this strategy and found that our problem has a typical trend, i.e. if the size N of list is small (≈ 10), the minimum cost min i∈[N] S(X i ) decreases very fast but seems to stay near a local minimum. On the other hand, if we choose a large N (≈ 1000), the speed of convergence is slow, but the pruning function found is better than in the small case if we use many loop iterations. Hence, we start with a small N and increase it little by little.

Integrating the above, we give the pseudocode of our optimizing algorithm in Algorithm 2. We used a heuristic parameter set N init = 10 and N max = 50, and terminate the computation if v is not updated in the last 10 loop iterations.

Tightness and Applications to Security Estimates

In this section, we study the heuristic cost N of (5) divided by two (SVP setting).

Modeling Strongly Reduced Bases

The cost (5) of cylinder pruning over P f (B, R) depends both on the quality of the basis B, the radius R and the pruning function f . The results of Sect. 3 allow to lower bound the numerator of each term of ( 5), but we also need to lower bound the part depending on the basis B. This was already discussed in [START_REF] Nguyen | Public-key cryptanalysis[END_REF][START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] L ← L ∪ X 7: else 8:

X i ← argmax X i ∈L Cost(X i ) 9: end if 10: if Cost(X) < Cost(X i ) then 11:
Replace X i by X Update u by using list L 13: end if 14: if u is not updated in the last d loops then 15:

N ← N + 1 16: end if 17: if N > N max then 18:
output minimum among X 1 , . . . , X N-1 and exit 19: end if 20: goto Step 1 used in [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Nguyen | Public-key cryptanalysis[END_REF] which provides conservative bounds by anticipating progress in lattice reduction, and the HKZ model used in [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF] which is closer to the state-of-the-art. This part is more heuristic than Sect. 3.

The HKZ model. The BKZ algorithm tries to approximate HKZ-reduced bases, which are bases B such that b i = λ 1 (π i (L)) for all 1 ≤ i ≤ n. When running BKZ, an HKZ basis is the best output one can hope for. On the other hand, a BKZ-reduced basis with large blocksize will be close to an HKZ-basis, so this model is somewhat close to the state-of-the-art. It corresponds to an idealized Kannan's algorithm [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF] where enumerations are only performed over HKZreduced bases (see [START_REF] Micciancio | Fast lattice point enumeration with minimal overhead[END_REF] for more practical variants). Unfortunately, in theory, we do not know what the b i 's of an HKZ basis will look like exactly, except for i = 1, but we can make a guess. Following [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF][START_REF] Aono | Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[END_REF], we assume that for 1 ≤

i ≤ n -50, b i ≈ GH(π i (L)) = V n-i+1 (1) -1/(n-i+1) ∏ n k=i b k 1/(n-i+1) ,
which means that we assume that π i (L) behaves like a random lattice. Then we can simulate b i for 1 ≤ i ≤ n -50 by a simple recursive formula. We stop at n -50, because Chen and Nguyen [START_REF] Chen | BKZ 2.0: better lattice security estimates[END_REF] reported that the last projected lattices do not behave like random lattices. For the remaining indices, they proposed to use a numerical table from experimental results in low dimension: we use the same table. Note that for a large dimension such as 200, errors in the last coordinates are not an issue because the contribution of the terms k ≤ 50 in N is negligible.

The Rankin model. It is known that HKZ bases are not optimal for minimizing the running time of enumeration. For instance, Nguyen [START_REF] Nguyen | The LLL Algorithm: Survey and Applications[END_REF]Chapter 3] noticed a link between the cost of enumeration and the Rankin invariants of a lattice, which provides lower bounds on heuristic estimates of the number of nodes and identifies better bases than HKZ. However, finding these better bases is currently more expensive [START_REF] Dadush | Algorithms for the densest sub-lattice problem[END_REF] than finding HKZ-reduced bases. Recall that the Rankin invariants γ n,m (L) of an n-rank lattice L satisfy:

γ n,m (L) := min S: sublattice of L rank(S)=m vol(S) covol(L) m/n 2 ≤ ∏ m i=1 b i 2 covol(L) 2m/n , (14)
for any basis (b 1 , . . . , b n ) of L. We have the following lower bound [37, Cor. 1] for Rankin's constant γ n,m := max L γ n,m (L):

γ n,m ≥ n • ∏ n n-m+1 Z(j) ∏ m j=2 Z(j) 2/n where Z(j) := ζ(j)Γ(j/2)π -j/2 . ( 15
)
According to [START_REF] Shapira | A volume estimate for the set of stable lattices[END_REF], it seems plausible that most lattices come close to realizing Rankin constants: for any ε > 0 and sufficiently large n, most lattices L "should" verify γ n,m (L) ε for all m.

Ignoring ε, if we lower bound any term of the form ∏ m i=1 b i 2 covol(L) 2m/n in the simplified cost (5) by the right-hand side of (15), we obtain the following heuristic lower bound formula:

N = 1 2 n ∑ k=1 vol(C R 1 ,...,R k ) n-k ∏ i=1 b i vol(L) > 1 2 n ∑ k=1 vol(C R 1 ,...,R k ) vol(L) k/n        (n -k) n ∏ j=k+1 Z(j) n-k ∏ j=2 Z(j)        1 n-k
In both cases, substituting the volume lower bounds in Section 3.2 and 3.3, we obtain closed formulas to find the lower bound complexity which are suitable for numerical analyses.

On the other hand, for any n-rank lattice L, and any fixed m ∈ {1, . . . , n -1}, there is a basis

(b 1 , . . . , b n ) of L such that ∏ m i=1 b i 2 covol(L) 2m/n = γ n,m (
L). This existence would only be guaranteed for fixed m, such as for the m maximizing the corresponding number N n+1-m of nodes in the enumeration tree at depth m. By idealization, we call Rankin basis a basis such that for all m ∈ {1, . . . , n -1}, ∏ m i=1 b i 2 covol(L) 2m/n is approximately less than the right-hand side of ( 15): since such bases may not exist, this is an over-simplification to guess how much speed-up might be possible with the best bases. We use Rankin bases to compute speculative upper bounds, anticipating progress in lattice reduction.

Explicit Lower Bounds

We summarize the applications of the results of Section 3.2 and 3.3, to compute lower bounds on the number of nodes searched by cylinder pruning with lower bounded success probability.

Single Enumeration. By Corollary 2, if α is a lower bound on the success probability,

N ≥ 1 2 n ∑ k=1 V k ( √ α k R n ) ∏ n i=n-k+1 b i (16)
where α k is defined by

I α k (k/2, 1 + (n -k)/2) = α.
For the Gaussian case with success probability ≥ β, from Corollary 3,

N ≥ 1 2 n ∑ k=1 V k ( β k ) ∏ n i=n-
where α satisfies vol(∪ m i=1 C i ) ≥ α vol(R n ). Lemma 9 also implies a lower bound for the Gaussian setting with global success probability ρ n,σ (∪ m i=1 C i ) ≥ β :

N ≥ β 2 n ∑ k=1 (2πσ 2 ) k/2 ∏ n
i=n-k+1 b i .

Radii Tightness

To check tightness, we give two figures (Figure 2) that compare the lower bound of radii from Corollary 2, and the best radii generated by our cross entropy method. The comparison is for two regimes: high and low success probability. Note that the left probability 0.6827 is an approximation of P( 1 2 , 1 2 ) for which the linear pruning is the best known proved lower bound.

We see that the radii bounds are reasonably tight in both cases. We deduce that in these examples, the enumeration cost bounds will also be tight, because the cost is dominated by what happens around k ≈ n/2.

We note that it is to easier to compute lower bounds than upper bounds.

Security Estimates for Enumeration

Fig. 1 (in the introduction) displays four bounds on the cost of enumeration in several situations, for varying dimension and simulated HKZ bases and Rankin bases:

-The thin red curve is an upper bound of the enumeration cost using M = 10 10 bases with single success probability α = 10 -10 computed by the crossentropy method. -The bold red curve is a lower bound of the enumeration cost using M = 10 10 bases with single success probability α = 10 -10 computed by M times [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF].

-The thin green curve is an upper bound of the enumeration cost w.r.t. infinitely many bases with global success probability α = 1. This is computed by M times an upper bound of the enumeration cost with single success probability 1/M for a very large M where the single cost is greater than lattice dimension. -The bold green curve is a lower bound of the enumeration cost w.r.t. infinitely many bases with a large global success probability. This is computed by [START_REF] Rijneveld | NTRU-HRSS-KEM: Algorithm specifications and supporting documentation[END_REF] with α = 1.

In all experiments, we take the radius by R n = GH(L). The cost is the number of nodes of of the enumeration tree in the classical computing model. The security level is the base-2 logarithm of the cost, which is divided by two in the quantum computing model [START_REF] Aono | Quantum lattice enumeration and tweaking discrete pruning[END_REF][START_REF] Montanaro | Quantum walk speedup of backtracking algorithms[END_REF]. We also draw the curve of 2 0.292n and 2 0.265n which are simplified lower bounds of the cost for solving SVP-n used in [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes! Posted on the pqc-forum on Feb. 1[END_REF] for classical and quantum computers, respectively.

In all the situations where we use 10 10 bases, the upper bounds (thin red curve) and the lower bounds (bold red curve) are close to each other, which demonstrates the tightness of our lower bound.

In the classical setting, our lower bounds for enumeration are higher than sieve lower bounds. On the other hand, in the quantum setting, there are cases where enumeration is faster than quantum sieving. For instance, if an attacker could find many quasi-Rankin bases by some new lattice reduction algorithm, the claimed 2 128 quantum security might be dropped to about 2 96 security. In such a situation, the required blocksize would increase from about 480 to 580.

Experimental Environments

All experiments were performed by a standard server with two Intel Xeon E5-2660 CPUs and 256-GB RAM. We used the boost library version 1.56.0, which has efficient subroutines to compute (incomplete) beta, (incomplete) gamma and zeta functions with high precision.

To show the decreasing property, it suffices to show that g(y) = 1 y • (P -1 (k/2, β y)) k/2 is strictly increasing over 0 < y ≤ 1. We use the inequality ∂ ∂x P -1 (a, x) = Γ(a)e P -1 (a,x) P -1 (a, x)

5 :

 5 using two models of strongly reduced bases: the Rankin model Algorithm 2 Cross-Entropy Method for Optimizing Pruning Radii Input: Gram-Schmidt lengths ( b 1 , . . . , b n ), Radius of the ball R, Target probability p 0 , initial and maximum size of list N, N max , initial parameter vector u = (c, σ), parameter to increase list size d. Output: A near optimal cost and corresponding radii (R 1 , . . . , R n ) 1: Sample new X = (R 1 , . . . , R m ) from D χ,u 2: if Pr(X) < p 0 then if |L| < N then 6:

  k+1 b i where β k is defined by P(k/2, β k /(2σ 2 )) = β. Multiple Enumerations. For the situation where one can use m bases, let α be a lower bound on the global success probability. Then by Lemma 6, R n )B(k/2, 1 + (nk)/2) ∏ n i=n-k+1 b i

Fig. 2 .

 2 Fig. 2.Comparison of lower bound and near optimal radii; for the 150-dimensional simulated HKZ basis, compute near optimal radii and lower bound radii for α = 0.6827 P(12 , 1 2 ) (Top) and α = 10 -10 (Bottom).

  1-a ≥ P -1 (a, x) axwhich is immediate from the left hand side of (22) with z = P -1 (a, x).Hence, denoting P := P -1 (k/2, β y) for simplicity,

	g (y) =	β k 2y	P k/2-1 •	∂P ∂y	-	P k/2 y 2 >	β k 2y	P k/2-1 •	P (k/2)β y	P k/2-1 -	P k/2 y 2 = 0
	This completes the proof.

Acknowledgements

This work was supported by JSPS KAKENHI Grant Numbers 16H02780, 16H02830 and 18H03238, and JST CREST JPMJCR168A.

A Proof of Lemma 3

Let

To prove Lemma 3, it suffices to show that: for any integers 1 ≤ k < n, p(n, k) ≤ P(

≈ 0.682689...

A.1 Formulas and Lemmas

We have Γ(a + 1) = aΓ(a) and B(a, b

The following recurrence formulas hold (see 8.17.18 and 8.17.21 of NIST Digital Library of Mathematical Functions http://dlmf.nist.gov/8.17 respectively):

We recall:

Theorem 8. (Chebyshev integral inequality) For any nonnegative, monotonically increasing function f (x) and monotonically decreasing function g(x), we have

a+b . Furthermore, it is strictly increasing over z ∈ [0, z max ] and strictly decreasing over z ∈ [z max , 1].

A.2 Proof Body

The proof of Lemma 3 can be derived from the following three lemmas.

Proof. By (21), we have

is equal to the last two terms. We will show that J < 0. From [START_REF] Kroese | The cross-entropy method for continuous multi-extremal optimization[END_REF], we have

and we get

of which we want to show negativeness.

Since the integral function

2 is strictly decreasing, the trivial bound

and it suffices to show that f (x) is strictly decreasing over the range x ∈ (n, n + 2). It is equivalent to check that the derivative of g

We have:

.

For 2 ≤ n ≤ 8, we can check it is smaller than 0.68 numerically, Also, for n ≥ 9, since the function (1 -1/x) x is monotonically increasing with x, we have

Proof. By definition and ( 20)

. Thus, it suffices to show

2 -1 which is strictly increasing over [0, k+2 n ]. Since z -2 is strictly decreasing, Chebyshev's integral inequality implies that

Therefore, we have I < J and it derives p(k + 2, n) < p(k, n).

A.3 Proof of Lemma 9

Recall that P(a, z) := z 0 x a-1 e -x dx Γ(a)

which implies:

e -z z a Γ(a + 1)

< P(a, z) < z a Γ(a + 1) for a > 0, z > 0.

Also, they imply the bound P -1 (a, x) > (Γ(a + 1)x) 1/a for a > 0, 0 < x < 1 [START_REF] Micciancio | Fast lattice point enumeration with minimal overhead[END_REF] and the limits lim

Hence, we have


Mathieu Guérin

Teckwyn Lim

Ange S L Tan

Ahimsa Campos-Arceiz

Mathieu Guerin

Theodore R Hubback

; Taiping

A favourable shift towards public acceptance of wildlife conservation in Peninsular Malaysia: comparing the findings of the Wild Life Commission of Malaya (1932) with a recent survey of attitudes in Kuala Lumpur and Taiping, Perak

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Malaysia is a biodiversity hotspot, rich in charismatic wildlife. Peninsular Malaysia in particular is one of the strongholds for the survival of Asia's elephants (Elephas maximus), tigers (Panthera tigris) and leopards (Panthera pardus; e.g. [START_REF] Rostro-Garciá | Endangered leopards: Range collapse of the Indochinese leopard (Panthera pardus delacouri) in Southeast Asia[END_REF]. Perhaps due to this abundant natural heritage, Malaysians are sometimes not fully appreciative of the value of conservation and face accusations of not caring enough for wildlife [START_REF] Nagulendran | A multi-stakeholder strategy to identify conservation priorities in Peninsular Malaysia[END_REF]. Opinion surveys can reveal the actual extent to which Malaysian attitudes towards nature varies according to ethnicity, along the urban-rural divide and with income. However, such surveys seldom look at how public attitudes have changed over time.

Here we take advantage of a historical dataset to examine people's attitudes towards wildlife in the 1930s. We then compare the results with recent datasets produced for similar purposes. Our aim is to understand the factors affecting local people's attitudes towards wildlife. Specifically, our objectives are to analyse the results of the report of the Wild Life Commission of Malaya (WLCM 1932), compare them with the findings of a recent survey, and identify any trends.

Background Hubback's Wildlife Commission

At the end of the 1920s, wildlife conservation in the Malay Peninsula was a highly controversial issue. In 1929, the colonial authorities supported the rapid expansion of rubber plantations by removing the legal protection for elephants and sambar deer (Rusa unicolor) as well as abolishing game reserves in Pahang and Negeri Sembilan (Kathirithamby-Wells 2005). These moves resulted in an outcry among conservationists who were led by Theodore Rathbone Hubback, Honorary Game Warden for the Sultanate of Pahang.

Hubback, himself an experienced planter and former big game hunter felt that there was a need for stronger protection for endangered wildlife by setting up a centralised game department and creating a large national park. On 28 July 1930, Hubback, after intense lobbying, managed to get himself commissioned by King George V to conduct an inquiry into (i) the existing regulations for the protection of wildlife in the Straits Settlements; (ii) the extent of damage done to agriculture by wildlife and suggesting methods for dealing with it; and (iii) the organisation required to manage wildlife preservation (Straits Settlements Gazette Notification No. S 1523/1930). Hubback later received a similar commission by the High Commissioner to the Federated Malay States (Selangor, Perak, Negeri Sembilan, and Pahang). This second commission also included the preliminary study of a project to establish a national park in the vicinity of Gunung Tahan. The administrations of the Unfederated Malay States (Johor, Kedah, Perlis, Kelantan and Terengganu) also agreed to be part of the Commission. Hubback found himself at the head of a commission to conduct an inquiry on the preservation of wildlife in the whole of British Malaya.

In order to conduct this inquiry, Hubback and an "independent and impartial Assessor", George Hawkins (a British civil servant also based in Pahang), launched a large public consultation on the relations between the people of Malaya and wildlife. They designed a questionnaire that was sent out to Europeans and a few high-ranking Malayans.

Between August 1930 to March 1931, Hubback and Hawkins conducted a series of 64 public meetings in different places across British Malaya in order to allow interested parties to make their views known to the authorities. In Selangor, for which the minutes of the Commission have been preserved, they held six meetings in Kajang, Banting, Klang, Kuala Selangor, Kuala Lumpur, and Ulu Selangor in January 1931. Before the meetings, posters in English, Chinese, Jawi and Tamil were put up in the villages, inviting people with a special interest in wildlife to come forward and to provide testimonies. The posters said: "A commission has been appointed to inquire about the Preservation of the Wild Life of Malaya. One of the terms of reference of this Commission is as follows: "to inquire into the allegations of damage done to agriculture by Wild Life, to call for and record evidence bearing on such matters and to suggest methods of dealing with any situations which may be revealed." Members of the Public of Malaya who are able to give evidence on the above matters, as well as on other subjects relating to the preservation of Wild Life, are requested to testify before the Commission, which desire to receive and record information, from all sources, which will be of value to this investigation."

People who wished to testify were invited to contact Hubback by letter. This approach gave ordinary Malayans an opportunity to meet the Commission, although the procedure was focused on the educated elite rather than the illiterate masses. Indigenous forest-dwelling communities and manual labourers were not the focus but from the report of the Commission, it seems that many Malay villagers actually attended the meetings, most of the time with village headmen leading them. Through the questionnaires or during the meetings, at least 722 people provided statements to the Commission that were recorded, translated into English and published.

The contents of the Hubback report

The final report -nearly 1000 pages in three volumes -was edited by Hubback and Hawkins and published in 1932. The submissions to the Commission show a wide variety of opinions, from strong supporters of conservation to those who considered wildlife mainly as pests and a danger to mankind and agriculture. [START_REF] Kathirithamby-Wells | Nature and Nation: Forests and Development in Peninsular Malaysia[END_REF] notes how the Commission "presented a remarkable and unprecedented account of the human-animal encounter in a variety of situations" and "press reports of the evidence of witnesses fanned passions".

From the minutes that survived and the content published, it seems that the report honestly represents the submissions received. The report includes opinions totally opposed to the ideas of Hubback right alongside those that supported his views.

The testimonies can be divided into four categories: (1) those that insist on the need to preserve the wildlife of Malaya, (2) those that acknowledge the importance of wildlife preservation but consider that it should not infringe on the interests of agriculturalists, (3) those that consider wildlife mainly as a pest, and (4) those that did not show any particular opinion on wildlife conservation.

Although the detailed results presented in the report seems accurate, the analysis and final conclusions reached by Hubback appear somewhat distorted. He claimed that "there was, throughout Malaya, a very strong consensus of support" for the preservation of wildlife through the methods that he advocated. He dismisses opposition to conservation as simply a misunderstanding by deluded peasants: "in a few places, chiefly in Pahang, peasant witnesses, who may have been labouring under the delusion that this inquiry was primarily appointed to deprive them of the admitted rights of protection, or who may have been afraid that they might be asked to pay for something which at present they take for nothing, were hostile towards any steps for conservation" (WLCM 1932).

It is true that a majority of the respondents supported Hubback's views on wildlife conservation (Fig. 1). Out of 722 respondents, 230 considered wildlife preservation as a priority, and 213 considered it as important as long as protection for agriculturalists was provided, totalling 61% of the testimonies. Those who primarily saw wildlife as pests were a minority, representing only 28% of the respondents. The testimonies of the other respondents did not provide information on their views on the issue of wildlife preservation. At any rate, having only 61% in favour of conservation is far from a "very strong consensus".

Hubback seemed unwilling to delve into the complexities of the impressive dataset that he had assembled. [START_REF] Tan | The Beastly Business of Regulating the Wildlife Trade in Colonial Singapore[END_REF] notes that several of Hubback's contemporaries respected his views on conservation "while deploring his lack of balance, misdirected enthusiasm and inability to give a true value to the real facts" (John Kempe of the Malayan Civil Service in a letter to the Colonial Office, 29 April 1934).

Importantly, Hubback failed to mention that the demographics of his respondents were not representative of the general population of British Malaya. The split by age group is not reported and only one respondent was a woman -Lady Colina Hussey, Vice-President, Society for the Prevention of Cruelty to Animals. Chinese and Indians were largely under-represented (6% and 1% of the respondents, respectively) while British and other Europeans were over-represented in the sample (24%).

Methods and Results

A window to Malayan attitudes towards wildlife in the 1930s

Making appropriate stratification to the data from the Hubback report allows us to draw a more accurate picture of the attitudes of the general population and several specific segments of society. In particular, by excluding the answers of the 171 European respondents the data can be used to gauge the opinion of Asian Malayans. This provides a more appropriate point of reference for comparison with the attitudes of the public in Peninsular Malaysia today.

Of the 551 Asians who testified in front of the Commission, 24% were in favour of the protection of wildlife, 28% considered it as important as long as protection for agriculturalists was provided, 36% saw wildlife primarily as pests, and 12% did not make any clear statement on how they viewed wildlife. We need to stress that the sample of Asians who responded to the survey was in no way representative of the Asian population of British Malaya.

Social status and attitudes towards wildlife

Further stratification of the sample yields additional insights. From the testimonies and the presentation of the witnesses, we were able to determine the social status of 467 of the Asian respondents, i.e. 85% of the sample. The social status of these respondents fell into three groups:

(1) the colonial elite (civil servants and dignitaries, merchants, physicians, etc.), people who were closely connected with the British; (2) the kampong elite (penghulus, village headmen, imams, etc.), people of influence in their own village community; and (3) farmers (including planters and agriculturalists). The result shows a strong correlation between the social status and the perception of wildlife: A majority of farmers, i.e. 60% of respondents, considered wildlife mainly as a pest and as a threat to their source of income. Some were very vocal in their detestation of wildlife. For example, H. Abdul Manan bin Hussin, planter at Kluang, Johor, testified that "the worst pest are pigs, the next are birds, the next sambhur, the next monkey. I require the right of defence of my crops." (WLCM 1932: I-81); and Muhammad Sidik bin Kadir from Negri Sembilan who "would like to see Malaya stripped of all its deer." (WLCM 1932: I-133).

One in four village headmen shared similar opinions, especially some who appeared as the spokesperson for their community. For example, Wan Aim bin Wan Lambut, penghulu of Gerik, Perak, said: "I would like to see elephant and deer exterminated. Wild animals used to do some damage and my people were frightened of getting mixed up in a law suit if they shot. If [the farmers] are clear that they can shoot animals doing damage they will be pleased to return to the old system of licenses. I don't think kampong people with inadequate weapons should shoot elephants and that if there is a rogue elephant, government should deal with it." (WLCM: I).

However, 35% of the village headmen emphasized the need to protect wildlife from extinction as long as it was no direct threat to crops, livestock, and human lives, and as many as 26% considered the protection of wildlife as a priority. Respectively, 21% and 12% of the planters and agriculturalists shared the same views. Some of them even considered that it was the responsibility of the farmers to keep their estate safe.

For example, Yeap Seng was a Chinese planter in Batu Pahat, Johor, who managed 2000 acres of rubber and coconut. He considered that "if we planters have a fence, the estate is reasonably safe, an owner is partly responsible for damage by Wild Life." (WLCM: I-79). The penghulu Abdul Kadir bin Rahmat shared a similar view: "Clean estates are reasonably safe".

We find that generally, the higher the social status and the closer the connection with the British, the more the respondent would support measures to protect wildlife. In the survey, 60% of the European respondents considered wildlife preservation as a priority and 34% that wildlife should be protected but the interests of the agriculturalists should be taken into account. The colonial elite, people who were working or interacting on a daily basis with the British, supported very similar views to those of the colonial masters sympathetic with wildlife conservation. Some of them, like Che Abdul Dahim bin Che Wik, Chief Kathi of Kedah, former district officers of Baling and Langkawi, have been quite active. Che Abdul Dahim said that he "addressed the government on the necessity of wild life preservation and asked that laws should be passed."

The stratification we use here manages to elucidate some interesting findings despite the inevitable bias of the approach of the Commission in that they only captured the views of those that actually came forward and testified to them. As mentioned, there was no special effort to seek the views of illiterate rural communities such as the Orang Asli. Also there was little effort to seek the input of labourers in plantations or in the tin mines and thus the proportion of Chinese and Indian respondents was far below that found in the wider population. There was also a bias towards those with views on wildlife strong enough to motivate them to attend the consultations.

Hunting and attitudes towards wildlife

The practice of hunting was strongly correlated with a positive perception of wildlife. Among the 98 respondents who mentioned that they hunted occasionally or regularly, 68% supported measures to protect wildlife, including the licensing of hunting; 24% favoured wildlife protection as long as it did not prevent agriculturalists to protect their crops and livestock; and only 7% considered wildlife primarily as pests that should be eradicated (Fig. 2). This profile was independent of social status and was also found among most farmers who hunted. Only 18% of farmers who hunted considered wildlife to be pests and 82% were in favour of wildlife protection.

In Malaya, as elsewhere in the British Empire and in the United States, hunters were largely sympathetic to the protection of wildlife [START_REF] Mackenzie | The Empire of Nature. Hunting, Conservation and British Imperialism[END_REF][START_REF] Reiger | American Sportsmen and the Origins of Conservation[END_REF]. They were the first to witness its disappearance. From their testimonies, we can see that it was not only a question of game management, but more of a will to preserve "the beauty of the world". The testimony of Haji Mohamed Khatib bin Aman, penghulu of Setul, is enlightening: "I used to do some [hunting] but now Sambhur are all gone. They have been wiped out since removal of protection [1929]. Some of my people go elsewhere to [hunt]. I think protection of Sambhur should be restored and that there should be prohibition of shooting for some years to let them breed. Deer used to [do] damage but my people did not fence. I would like to see the Deer back again so long as they did only a little damage. If the Wild Life is wiped out, the world will be as it were naked." (WLCM: I-128). Yahaya bin Abu Talib, a Major in the Johor military who used to hunt with the Sultan explained that "in the future, Wild Life will be extinguished. It would be a pity if the Wild Life were extinguished. I am fond of Wild Life." (WLCM: I-78). These views explain why some hunters joined the Game Department of their State as Game Rangers or even Honorary Game Rangers [START_REF] Guérin | Conserver la faune sauvage de la péninsule malaise: de la Malaya britannique à la Malaisie indépendante[END_REF]. Ahmad bin Lebai Jamal worked as Game Ranger in Pahang and Negri Sembilan for eight years when he testified in front of the Commission: "I have been a professional hunter, tracker and guide for the last 32 years and have hunted in Burma, Negri Sembilan, and Pahang, having shot everything but a Rhinoceros. I personally have shot 20 elephant, 1 seladang, 4 tiger, and about 20 sambhur. Deer have much decreased since the removal of protection. It is impossible to say how many have been shot, but I estimate that through the state three-quarters of the sambhur have been killed. Complete extermination is within sight. It would be a disgrace if the wild life of Malaya was lost. (…) Reserves for game ought to be made." (WLCM 1932: I-131).

Motivations to protect wildlife

The purpose of why wildlife should be protected varied widely among respondents. While for Hubback and many Europeans it was a question of progress and civilisation that perfectly fitted the colonial rhetoric, Malayan witnesses came forward with quite different reasons when they explained their point of view. For Tungku Abdul Muluk bin Tungku Yahaya, Penghulu of Ulu Klawang, "wild animals are pretty, in danger of extinction, a food supply, and a source of amusement". Abdul Kadir bin Rahmar praised the ecological role of animals, "Tiger are rare in my mukim, here they are not very dangerous to man and keep down Deer and Pig", while Yop bin H. Mohammad, a forest ranger in Johor emphasized their action as seed dispersers (WLCM 1932: I-83). Like many hunters, most of Malaysian respondents who supported actions to protect wildlife highlighted the fact that wildlife is part of the world and its disappearance would have an impact on its beauty. The phrase "Wild Life is an ornament to the country" appears in several testimonies (WLCM 1932: I -91, I-132). Its origin could not be traced. Some of the respondents even used religious reasons to justify the protection to wildlife such as "The Lord God created man and beast" (WLCM 1932: I-135).

Local attitudes towards wildlife in 2016

How do the attitudes towards wildlife of 1930s Malaya compare with those of present day Peninsular Malaysia? While we do not have data that allows us to make exact comparisons we do, however, have some recent data that suggests a favourable trend. In 2016, as part of a study about knowledge, attitudes, and practices towards wildlife conservation, we asked 525 Malaysian citizens whether they believed that tigers had the right to exist in their country. Our sample was from two urban locations in Peninsular Malaysia, including 246 respondents in Kuala Lumpur (the capital city of ~7.3 million people) and 279 respondents in Taiping (a town in Perak of ~215,000 people).

The overwhelming majority of our sample held positive values towards tigers, with 94% of the respondents either agreeing or agreeing strongly that tigers have the right to exist in the country (Fig. 3). We found no differences in attitudes between people in Kuala Lumpur and Taping (𝝌 2 =5.3, df=3, P=0.15; Fig. 3). When asked to justify positive responses, their comments included, "I love animals"; "My religion teaches me that all living things live with a reason"; "They have an important role in the food chain"; "For educational purposes, so that future generations can learn about them"; "To maintain the natural balance"; and, "We can make money with them from tourism". The most common rationale for negative responses was "For safety reasons". The attitudes of these urban populations in 2016 resemble those of the colonial elite surveyed by Hubback (Figs. 1 and3).

Discussion

The Hubback report provides us with an extraordinary glimpse at attitudes towards wildlife in the early 1930s, nearly fifty years after the first laws and regulations taken by the British and the Sultans to protect the Malaysian Wildlife were drawn up [START_REF] Kathirithamby-Wells | Nature and Nation: Forests and Development in Peninsular Malaysia[END_REF] and two decades before public awareness campaigns were launched by the Game Department, the Education Department, the Malayan Nature Society and later other NGOs. When Hubback conducted his inquiry, wildlife in the Peninsula (particularly rhinos, gaur, elephants and sambar deer) were on the decline due to the withdrawal of legal protection, increased hunting with firearms, deforestation and the development of the plantations and mines frontier. Many Asian Malayans, especially within the elite, were already concerned that wildlife could disappear and supported actions to protect it. It is actually worth emphasizing that more than a third of farmers -people whose livelihoods were often directly affected by wild animals -supported increased measures to protect wildlife.

The respondents to Hubback's inquiry raised a number of issues that are still very important today. These include recognising that locals have to take responsibility for the mitigation of human-wildlife conflict (e.g. farmers constructing and maintaining their own fences). Hubback's respondents also showed a good understanding of ecological interactions such as trophic cascades (e.g. that tigers are needed to keep deer populations in check) and the role of mammals in plant population dynamics through seed dispersal.

Stratification of Hubback's respondents makes it clear that people's attitudes towards wildlife conservation varied according to their social group. There were very few Asian urban respondents in Hubback's survey, and even those living in Kuala Lumpur and Singapore could experience the threat of animal raids1 . The farmers whose livelihood could be jeopardized by wildlife were much less keen on conservation than the elite. This is not surprising since wildlife poses much smaller a risk for the safety and livelihoods of the elite and urbanites.

This sympathetic attitude towards conservation among the 'sheltered' groups is reflected in the attitudes of present-day urban Malaysians. The respondents both in Kuala Lumpur and in a relatively small town (Taiping) showed attitudes with levels of favourability to wildlife comparable to those of the 1930s elite. The reasons provided to justify the importance of conserving wildlife are also remarkably similar, with people in the recent survey still considering that wildlife "Are God's creation", "Belong here", and "Are important for ecosystems".

Since the 1930s Malaya has undergone many changes. Plantations continued to expand and forest cover dropped from more than 80% in 1930 to around 44% in 2010 [START_REF] Miyamoto | Proximate and underlying causes of forest cover change in Peninsular Malaysia[END_REF]. There was a large increase in total population from around 3 million then to around 20 million today and there has also been a significant trend towards urbanisation. In 1930, the Malayan population was more than 80% rural but since 1990, the majority of the population has been urban and today less than 25% of the people lives outside town and cities in Peninsular Malaysia (Populstat 2017).

If the urban attitudes of wildlife in our survey are reflective of those of urban Malaysians throughout the Peninsula, we can tentatively say that favourable attitudes towards conservation have accompanied urbanisation in Malaysia. However, this is not enough to entirely explain the shift towards a more open mind-set in favour of conservation. Penghulu, Ketua Kampong, imams…, who in 1930 were much more in favour of the protection of wildlife than the other village dwellers, shared with them a very similar way of life. The main differences were their role as leaders and their access to education. The vast majority of the village elite mastered reading and writing, while literacy rate in British Malaya was only 32% for the overall population, 25% among the Malays, in 1947 [START_REF] Vandenbosch | Southeast Asia among the world powers[END_REF]. Literacy was most probably lower in the 1930s. In 2010, adults' literacy rate was 93% in Malaysia (Unesco Institute for Statistics). We can confidently come forward with the hypothesis that literacy and primary education had an impact on wildlife perception in Malaysia, even if this needs to be confirmed by further studies. Our results are in accordance with trends seen elsewhere. [START_REF] Manfredo | Why are public values toward wildlife changing?[END_REF], for example, found positive effects of income, education, and urbanization on positive shifts in values towards wildlife in the U.S. Urban dwellers in Croatia also show more positive towards wildlife (i.e. wolves; [START_REF] Majić | Attitudes of Rural and Urban Public toward Wolves in Croatia[END_REF], and the level of education has a positive influence on attitudes towards conservation among rural communities in Ecuador [START_REF] Fiallo | Local communities and protected areas: attitudes of rural residents towards conservation and Machalilla National Park, Ecuador[END_REF]. Moreover, public awareness campaigns can have positive effects on people's attitudes towards conservation (van der Ploeg et al. 2011), hence, the impact of the conservation campaigns and nature education conducted by environment orientated organisation such as the Malayan and then Malaysian Nature Society, the World Wild Fund for Nature, the Ministry of Education, etc. would also need to assessed.

The fact that urbanisation could result in a more sympathetic attitude towards conservation would not be surprising but it does have implications for the way wildlife is managed, particularly how the financial burden for conservation is shared between people living in the cities and those in the countryside. At present the rural population has to bear most of the cost of crop raiding by animals such as deer, pigs and elephants. This financial burden, which is often coupled with physical risks, has a direct influence on rural people's attitudes towards conservation. A more equitable split in the cost via subsidised insurance schemes [START_REF] Chen | Developing a spatially-explicit, sustainable and risk-based insurance scheme to mitigate human-wildlife conflict[END_REF] or electric fences [START_REF] Ponnusamy | Farmers' Perceptions and Attitudes towards Government-Constructed Electric Fences in Peninsular Malaysia[END_REF] would improve rural attitudes and ultimately increase the potential for effective conservation. Recent studies [START_REF] Kafashi | Exploring visitors' willingness to pay to generate revenues for managing the National Elephant Conservation Center in Malaysia[END_REF] suggest that Malaysians are willing to pay to see elephants in captivity and even to contribute to a trust fund for the protection of wild elephants [START_REF] Poh | Economic value of forest in elephant conservation[END_REF].

All in all, this study shows how adopting interdisciplinary approaches, in this case using methods from history and sociology can shed light on key aspects of conservation biology that would not be apparent to natural scientists working solely within their own disciplines such as zoology and ecology. The Hubback report deserves additional analysis and we hope to have shown how it can, when treated with the appropriate caveats, be used as a baseline for attitude surveys for many years to come.

Figure 1 .

 1 Figure 1. Attitudes towards wildlife among Asians in British Malaya according to social status.

Figure 2 .

 2 Figure 2. Attitudes towards wildlife among Asians in British Malaya: respondents who were hunters.

Figure 3 .

 3 Figure 3. Present-day attitudes towards tiger conservation in Peninsular Malaysia.

Peter Boomgaard and Cedric Tan &al. have shown that tigers' attacks in Singapore could occur in the city(Tan & al.

2015; Boomgaard 2001), while elephants were still raiding rubber plantations and gardens in Damansara, Bukit Kiara or Kuala Lumpur itself in the 1920s[START_REF] Guérin | Conserver la faune sauvage de la péninsule malaise: de la Malaya britannique à la Malaisie indépendante[END_REF].

Acknowledgements M.G.'s research was financed with support from the Soutien à la mobilité internationale (SMI) program of the Institut des Sciences humaines et sociales of the French National Center for Scientific Research (CNRS). The University of Nottingham Malaysia Campus, welcomed him as a visiting-scholar. Arkib Negara Malaysia gave M.G. access to their records and resource persons. The 2016 survey was carried out as part of Management & Ecology of Malaysian Elephants (MEME), a joint research project between the Department of Wildlife and National Parks (DWNP) Peninsular Malaysia and the University of Nottingham Malaysia Campus (UNMC).

MEME is partially funded by Yayasan Sime Darby (grant M0005.54.04), including an MSc scholarship to A.S.L.T. and a PhD scholarship to T.L. We are very grateful to all the people who entertained our questions, management of Zoo Negara, Taiping Sentral Mall and Zoo Taiping and volunteers who helped to conduct the survey in Kuala Lumpur and Taiping.