Jianwei Li
email: jianwei.li@inria.fr.

Michael Walter
email: michael.walter@zama.ai.

Improving Convergence and Practicality of Slide-type Reductions

Keywords: Lattice Reduction, Slide Reduction, (H)SVP, Dynamical Systems, Gaussian Heuristic

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle.

A central lattice problem is the shortest vector problem (SVP): given a basis of a lattice L (endowed with the Euclidean norm), SVP is to find a shortest nonzero vector in L. There are two relaxations with factor δ ≥ 1:

-The δ-approximate variant of SVP (δ-SVP) is to find a non-zero vector v in L such that v ≤ δ • λ 1 (L), where λ 1 (L) := min x∈L =0 x denotes the length of the shortest nonzero vector in L.

δ-Hermite SVP (δ-HSVP) is to find a non-zero vector v in L such that v ≤ δ • vol(L) 1/n , where vol(L) denotes the volume of L. Solving δ-SVP is hard for any δ ≤ n c/ log log n with some constant c > 0 under reasonable complexity-theoretic assumptions [START_REF] Ajtai | The shortest vector problem in L 2 is NP-hard for randomized reductions (extended abstract)[END_REF][START_REF] Cai | Approximating the SVP to within a factor (1 + 1/dim ε ) is NP-hard under randomized reductions[END_REF][START_REF] Micciancio | The shortest vector in a lattice is hard to approximate to within some constant[END_REF][START_REF] Khot | Hardness of approximating the shortest vector problem in lattices[END_REF][START_REF] Haviv | Tensor-based hardness of the shortest vector problem to within almost polynomial factors[END_REF][START_REF] Micciancio | Inapproximability of the shortest vector problem: Toward a deterministic reduction[END_REF]. Lovász [START_REF] Lovász | An algorithmic theory of numbers, graphs and convexity[END_REF] showed that any δ-HSVP solver in rank n can be used to efficiently solve δ 2 -SVP in rank n. For random lattices L of rank n, the classical Gaussian heuristic claims λ 1 (L) ≈ n 2πe • vol(L)

1/n : hence, any δ-HSVP solver in rank n for δ ≥ √ n can possibly be used to solve (δ/ √ n)-SVP in the same rank in practice (see [START_REF] Gama | Predicting lattice reduction[END_REF]§3.2]). The output quality of a δ-HSVP solver in rank n is typically assessed with the so-called root Hermite factor (RHF) δ 1/(n-1) (see, e.g., [ABF + 20, ABLR21]).

Many cryptographic primitives base their security on the worst-case hardness of δ-SVP or related lattice problems [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF][START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract[END_REF]. Security estimates of these constructions depend on solving δ-HSVP, typically for δ = poly(n) [START_REF] Gama | Predicting lattice reduction[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF].

The standard approach for solving δ-(H)SVP is lattice reduction, which finds reduced bases consisting of reasonably short and relatively orthogonal vectors. Lattice reduction has numerous applications in mathematics and computer science, and especially is a key tool in cryptanalysis. So, it is interesting and important to understand its potential and its limitations.

Blockwise lattice reduction. The most widely used reduction algorithm is the simplest one: LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], which can solve both SVP and HSVP in polynomial time within exponential approximation factors. Such large approximation factors are not good enough for all applications, especially in cryptanalysis. This has led to the development of stronger blockwise reduction algorithms [Sch87, SE94, SH95, GHGKN06, GN08a, MW16, ALNS20, ABF + 20, ABLR21], which generalize LLL using a special subroutine parameterized by an additional input parameter -the block size k -which controls time/quality trade-offs: the larger k is, the more reduced the output basis, but the running time grows at least exponentially with k.

The execution of blockwise reduction consists of a sequence of tours: each tour modifies the basis using a subroutine which solves SVP (or other hard lattice problems) in a lattice of rank ≤ k. After each tour, all the basis vectors have been examined, and may have been modified.

In practice, BKZ [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF][START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF]-the simplest generalization of LLL -provides the best time/quality trade-offs for approximating (H)SVP. Most work in lattice reduction has focused on BKZ, see e.g. [GN08b, HPS11, CN11, Wal15, AWHT16, ADH + 19, ABF + 20, ABLR21, LN20]. Other blockwise reduction algorithms are known, like slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF][START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF] and DBKZ [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF], all of which have better proven tradeoffs (than BKZ) for approximating HSVP. In particular, slide reduction provides the best proven trade-offs for approximating SVP.

Slide reduction. The focus of this work is slide-type reductions (including slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF][START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF] and, to some degree, its generalization to block-Rankin reduction [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF]). When it was originally introduced by [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF], slide reduction restricts the block size k to divide the lattice rank n. This restriction was lifted in the slide reduction algorithm [START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF]Alg. 3]. At a high level, the algorithm [ALNS20, Alg. 3] simply repeats polynomially many slide tours (until no more progress is made) to output a so-called slidereduced basis: given a basis B for an n-rank lattice where n = pk + q ≥ 2k with 0 ≤ q < k, each slide tour uses an SVP oracle in rank k to modify the p disjoint (projected) blocks B [1,k+q] , B [k+q+1,2k+q] , . . ., B [(p-1)k+q+1,pk+q] of the basis (possibly in parallel), then to modify (in a dual way) the disjoint blocks B [2,k+q+1] , B [k+q+2,2k+q+1] , . . . , B [(p-2)k+q+2,(p-1)k+q+1] (possibly in parallel). This results in "primal" and "dual" blocks that overlap by 1 index (or (k -1) indices by duality when q = 0).

Its higher-dimensional generalization to block-Rankin reduction [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF] works similarly, but it solves a more general problem and uses a more general tool. It approximates the densest sublattice problem (DSP) [START_REF] Dadush | Algorithms for the densest sub-lattice problem[END_REF], by relying on an oracle that solves the r-DSP in rank k. (SVP corresponds to 1-DSP.) In this variant, the dual blocks are shifted by r resulting in overlaps of size r (or (k -r) by duality).

Initial experimental evaluations of slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF][START_REF] Gama | Predicting lattice reduction[END_REF] found it to be not competitive in practice with BKZ. To the best of our knowledge, so far there has been no research into practical variants of slide reduction and block-Rankin reduction. This is despite the fact that it offers some trivial parallelization on the disjoint blocks. This is not true for other reduction algorithms and in light of the fact that modern SVP solvers are hard to parallelize, could give slide reduction [GN08a, ALNS20] a considerable advantage in practice.

Potential analyses vs. dynamic analyses. Assuming an oracle in fixed block size, the running time of a blockwise reduction algorithm is dominated by the number of tours (or oracle calls).

The classical approach for bounding the number of tours mimics the analysis of LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], based on an always-decreasing potential function. It was also used to analyse slide reduction [GN08a, ALNS20] and block Rankin reduction [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF]. However, this type of analysis can only upper bound well (say,) b 1 for the final reduced basis (b 1 , . . . , b n ) output by the algorithm, not for the current basis during execution. Furthermore, it seems hard to find a suitable potential function for analysing BKZ and for a long time it was open if the number of oracle calls in BKZ may be polynomially bounded.

Hanrot, Pujol and Stehlé introduced at CRYPTO '11 [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] the use of discrete dynamical systems to analyse a certain variant BKZ' of BKZ and show that one can put a polynomial bound on the number of oracle calls for BKZ' while preserving its output quality. This dynamic analysis provides guarantees on the quality of the current basis during execution. Recently, [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s method was adapted and improved in [START_REF] Li | A complete analysis of the BKZ lattice reduction algorithm[END_REF] to (the genuine) BKZ [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF][START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF], together with slightly sharper bounds for both the output quality and the running time. In particular, [START_REF] Li | A complete analysis of the BKZ lattice reduction algorithm[END_REF] claimed a sufficient number of tours for BKZ independent of the input basis when being LLL-reduced. Interestingly, the time bound claimed in [START_REF] Li | A complete analysis of the BKZ lattice reduction algorithm[END_REF] for BKZ was stronger than the one proven for slide reduction (and block-Rankin reduction) using the potential function. [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s method was also used to analyse the DBKZ algorithm [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF], and the analysis was further simplified and completed by Neumaier [START_REF] Neumaier | Bounding basis reduction properties[END_REF]. Hanrot et al. made two suggestions:

-Suggestion 1: "It may be possible to obtain a similar bound for the slide reduction algorithm [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF] by adapting (their) analysis" [HPS11, p. 449].

-Suggestion 2: "Parts of the analysis might prove useful to devise reduction algorithms with improved practical time/quality trade-offs" [HPS11, p. 451].

Our results. This work aims to improve convergence and practicality of slide-type reductions. First, we present a generic slide reduction (GSR) algorithm in Sect. 3, which captures (natural variants of) slide reduction and block-Rankin reduction. Intuitively, GSR generalises the slide reduction algorithm [ALNS20, Alg. 3] by replacing the SVP-oracle in rank k with a generic (h, r)-reduction oracle in rank k.

Here, we say that a projected block (say,)

B [1,k] is (h, r)-reduced if vol(B [1,r] ) ≤ h (k-r)r • vol(B [1,k]
) r/k : For instance, any r-DSP solver, or even LLL or BKZ can do (h, r)-reductions (w.r.t. different h). The motivation behind introducing GSR is to provide universal time/quality analyses of slide-type reductions, and to reveal more practical variants.

By slightly adapting the potential function used in [START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF], we prove that given an LLL-reduced basis B 0 of a lattice L of rank n where n = pk + q ≥ 2k with 0 ≤ q < k and k > r ≥ 1, one can compute a so-called generalized slide reduced basis within at most O n 3 kε GSR tours for a slack factor ε ∈ (0, 1]. This improves the previous number of tours O n 2 log B0 kε claimed for slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF][START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF] and block Rankin reduction [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF]. This is because the term log B 0 might be arbitrarily large: e.g.,

D = Diag( 1 n n 6 , 1, . . . , 1, n n 6 ) ∈ R n×n is LLL-reduced, but log D = n 6 log n. In particular, with O n 3 kε tours, [ALNS20, Alg. 3] can output a slide-reduced basis (b 1 , . . . , b n ), which approximates (H)SVP as follows: b 1 ≤ ((1 + ε) 2 γ k ) n-1 2(k-1) vol(L) 1/n and b 1 ≤ (1 + ε)((1 + ε) 2 γ k ) n-k k-1 λ 1 (L).
Here, γ k denotes as usual Hermite's constant.

Second, we adapt [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s dynamic analysis for BKZ' to our GSR in Sect. 4 and deduce a sharper polynomial bound on the number of oracle calls for GSR while preserving the similar output quality: with

O n 2 ln n ε (k-r)r
GSR tours on an LLL-reduced input basis, one can output a basis B with small vol(B [1,i] ) for all indices i ∈ {r, k + q, . . . , (p -1)k + q} (rather than a fully reduced basis). For instance, this implies that with O

n 3 ln n ε k 2 oracle calls, [GN08a, Alg. 1] can output a basis (b 1 , . . . , b n ) such that b 1 ≤ (1 + ε)γ n-1 2(k-1) k vol(L) 1/n .
This not only confirms [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s Suggestion 1, but also provides a better dependence of time/quality tradeoffs on ε than that achieved by the potential analyses.

Similar improvements for the block-Rankin reduction algorithm [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF] are notable if one is interested in computing a basis with small vol(B [1,r] ) (see Cor. 1 vs. Cor. 3).

Third, we introduce in Sect. 5 a cheaper analogue of the block-Rankin-reduction algorithm by replacing its expensive r-DSP oracle in rank k with any HKZ solver in rank k. We call this particular instantiation of GSR HKZ-slide reduction, which is inspired by the following three observations:

-Observation 1: It was observed in [ADH + 19] that modern SVP solvers do not only find the shortest vectors, but also approximately HKZ-reduce the head of the basis essentially for free. -Observation 2: HKZ-reduction approximates r-DSP quite well, especially for small r = O(1) (guaranteed by [HS07, Lem. 3]). -Observation 3: Experiments suggest that part of BKZ's efficiency in practice seems to be the fact that the blocks overlap maximally. Compared with slide reduction, increasing the overlap in HKZ-slide reduction decreases the number of tours at the cost of slightly increasing the length of the short vector found. All of our arguments (Cor. 5.2 and Sect. 5.1), experimental evidence (Sect. 5.2) and heuristic simulation (Sect. 6.2) demonstrate that this time/quality trade-off can be very favorable in practice. This somewhat confirms [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s Suggestion 2. A well chosen overlap yields a variant of slide reduction that we consider competitive with the state-of-the-art BKZ [ADH + 19]. When interpreting this result, it should be kept in mind that we did not explore all options to fine-tune the oracle to our algorithm and that BKZ has received considerable research effort to arrive at the performance level it is at now. This is not the case for slide reduction.

Finally, thanks to the dynamic analysis of GSR, we propose in Sect. 6 a simple and efficient simulator to heuristically model/trace the execution of (HKZ-)slide reduction with high block size. It can estimate both the output quality and the number of tours, once given parameters (k, r) for HKZ-slide reduction. This further highlights the usefulness of [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s dynamical systems technique.

In summary, we believe that our work is a step towards better understanding and improving the practical performance of slide reduction beyond speeding up the SVP oracle.

Technical overview. We first sketch [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s dynamic analysis for BKZ'. [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] used the profile function P(B) := (log vol(B [1,1] ), log vol(B [1,2] ) 1/2 , . . . , log vol(B [1,n] ) 1/n ) T to study the quality of the current basis B at the end of each tour, rather than just at the end of the algorithm.

Let B denote the basis at the end of the -th tour, and let B 0 be the input basis. [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] built a matrix M ∈ R n×n and a vector v ∈ R n such that component-wise:

P(B ) ≤ M • P(B -1 ) + v.
(1)

[HPS11] then analyzes a discrete-time dynamical system x ← xM + v. Its fixed point(s) and speed of convergence encode information on the output quality and runtime of BKZ', respectively. More specifically, if the dynamical system x ← M • x + v has a fixed point y ∈ R n , then Eq. (1) can be rewritten as

P(B ) -y ≤ M • (P(B -1 ) -y).
If all the entries of M are ≥ 0, this implies P(B ) -y ≤ M • (P(B 0 ) -y). [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] proved that M has spectral norm M < 1. Then M • (P(B 0 ) -y) converges to zero with an explicit vectorial upper bound: for any sufficiently large , we roughly have P(B ) ≤ y, i.e., the quality of B is guaranteed and upper bounded by the fixed point y.

In order to make [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s dynamic analysis work for GSR, we make the following three tweaks: -We study the quantity log

vol(B [1,j] )
vol(B) j/n for pivot indices j ∈ {ik + q : i = 1, . . . , p -1} (rather than for all indices j ∈ {1, . . . , n}). Here, the input lattice to GSR has rank n = pk + q w.r.t. block size k.

-To ensure the convergence of our dynamical system, we multiply each log vol(B [1,j] ) vol(B) j/n by calibration factor 1 (n-j)j , which eventually results in our profile function G(B):

G(B) = (G 1 (B), G 2 (B), . . . , G p-1 (B)) T ∈ R p-1 with each G i (B) = log vol(B [1,ik+q] ) vol(B) (ik+q)/n 1 (ik+q)(n-ik-q)
. We deduce that our dynamical system for GSR is x ← Ax + b with unique fixed point y ∈ R p-1 , where A ∈ R (p-1)×(p-1) is a tridiagonal matrix and b ∈ R p-1 is a vector. -Instead of using the spectral norm, it is more convenient for us to analyse the row sum norm A ∞ < 1, which implies the convergence of our dynamical system. As a result, similarly to [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF]'s analysis, we roughly have G(B ) ≤ y for any sufficiently large . In particular, we can upper bound vol((B ) [1,k+q] ) vol(B ) (k+q)/n w.r.t. the fixed point y. One more reduction on (B ) [1,k+q] allows us to measure the quality of (say,) its first basis vector.

Preliminaries

We denote column vectors x ∈ R m by bold lower-case letters. Matrices B ∈ R m×n are denoted by bold upper-case letters, and we often think of a matrix as a list of column vectors. We often implicitly assume that m ≥ n and that a basis matrix B = (b 1 , . . . , b n ) ∈ R m×n has (column) rank n, and write L(B) := For an n × n matrix M , we write M ≥ 0 if all the entries of M are ≥ 0. For two vectors u, v ∈ R n , we write u ≤ v if the inequalities hold componentwise. We will use the key elementary property: if u ≤ v and M ≥ 0, then M u ≤ M v.

{z 1 b 1 + • • • + z n b n : z i ∈ Z}
We

Lattices

Let B = (b 1 , . . . , b n ) ∈ R m×n be a basis of a lattice L and 1 ≤ r < n.

GSO. Lattice algorithms often use the orthogonal projections π

i : R m → span (b 1 , . . . , b i-1 ) ⊥ for i = 1, . . . , n. The Gram-Schmidt orthogonalisation (GSO) of B is B * = (b * 1 , . . . , b * n ), where the Gram-Schmidt vector b * i is π i (b i ). Then b * 1 = b 1 and b * i = b i - i-1 j=1 µ i,j • b * j for i = 2, . . . , n, where µ i,j = bi,b * j b * j ,b * j . The projected block (π i (b i ), π i (b i+1 ), . . . , π i (b j )) is denoted by B [i,j]
. Then the volume of the parallelepiped generated by

B [i,j] is vol(B [i,j] ) = j =i b * . In particular, B [1,j] = (b 1 , . . . , b j ) and vol(L) = vol(B) = n =1 b * . We will use the basic fact: vol(B [i,z] ) = vol(B [i,j] )•vol(B [j+1,z] ) for any integers 1 ≤ i ≤ j < z ≤ n.
Hermite's constant. Hermite's constant of dimension n is the maximum γ n = max λ 1 (Λ)/vol(Λ)1/n 2 over all n-rank lattices Λ, where λ 1 (Λ) = min v∈Λ\{0} v is the first minimum of Λ. The exact value of γ n is known for 1 ≤ n ≤ 8 and n = 24. It asymptotically satisfies [START_REF] Conway | Sphere packings, lattices and groups[END_REF][START_REF] Milnor | Symmetrie Bilinear Forms[END_REF]:

n 2πe + log(πn) 2πe ≤ γ n ≤ 1.744n 2πe +o(n).
Rankin's constant. We will use the following generalization of the first minimum λ 1 (L):

m r (L) := min x 1 ,...,xr ∈L vol(x 1 ,...,xr ) =0 vol(x 1 , . . . , x r ). Rankin's constant [Ran53] is γ n,r = max m r (Λ)/vol(Λ) r/n 2 over all n-rank lattices Λ. Clearly, γ n,1 = γ n .
DSP. The r-densest sublattice problem of L (r-DSP or (r, n)-DSP) is to find r linearly independent vectors v 1 , . . . , v r in L such that vol(v 1 , . . . , v r ) = m r (L) [START_REF] Dadush | Algorithms for the densest sub-lattice problem[END_REF]. Dadush and Micciancio [START_REF] Dadush | Algorithms for the densest sub-lattice problem[END_REF] showed that r-DSP is at least as hard as SVP and how to solve (r, n)-DSP exactly with r O(r•n) time and 2 n poly(n) space.

Duality. The dual basis of B is B × := B(B T B) -1 . The reversed dual basis of B is B -s := R m B × R n [GHGN06]
, where R n = (r i,j ) ∈ Z n×n is the reversed identity matrix: r i,j = 1 if i + j = n + 1 and r i,j = 0 otherwise. In lattice reduction, it is more convenient to consider B -s than to consider

B × [GN08a, LN14]. For instance, if the GSO of B -s is (d * 1 , . . . , d * n ), then b * i • d * n-i+1 = 1 for i = 1, . . . , n [Reg04, Claim 7]. Lattice reduction. B is size-reduced if |µ i,j | ≤ 1 2 for all 1 ≤ j < i ≤ n. B is LLL-reduced [LLL82] if it is size- reduced and every 2-rank projected block B [i,i+1] satisfies Lovász's condition: 3 4 • b * i 2 ≤ µ i+1,i •b * i +b * i+1 2 for 1 ≤ i < n.
In practice, the parameter 3 4 can be replaced with any constant in the interval

( 1 4 , 1). B is SVP-reduced if b 1 = λ 1 (L). There are two relaxations with δ ≥ 1: B is δ-SVP-reduced if b 1 ≤ δ • λ 1 (L); B is δ-HSVP-reduced if b 1 ≤ δ • vol(L) 1/n . B is δ-DSVP-reduced [GN08a] (where D stands for dual) if the reversed dual basis B -s is δ-SVP-reduced. Similarly, we say that B is δ-DHSVP-reduced if B -s is δ-HSVP-reduced, that is, vol(B) 1/n ≤ δ • b * n . B is HKZ-reduced if it is size-reduced and B [i,n] is SVP-reduced for i = 1, . . . , n. B is k-BKZ-reduced [Sch87] if it is size-reduced and B [i,min{i+k-1,n}] is SVP-reduced for i = 1, . . . , n. Gaussian heuristic. If L is a random lattice (cf. [CN11, §2] for the definition), the classical Gaussian heuristic claims λ 1 (L) ≈ GH(n) • vol(L)
1/n . Here, GH(n) denotes the radius of the unit-volume n-dimensional ball:

GH(n) = Γ (n/2+1) 1/n √ π ≈ n 2πe • (πn) 1 2n . It is known that GH (n) < √ γ n ≤ √ 2 • GH (n) if n > 24 [Bli14]
. Recently, Li and Nguyen [LN20, §4.1] established the following weak version of the Gaussian heuristic: for any ξ ∈ (0, √ 2 -1], there exists N > 0 such that if Λ is a random lattice of rank n ≥ N , then with high probability it satisfies

λ 1 (Λ) ≤ (1 + ξ) GH(n) • vol(Λ) 1/n .

The ALNS slide reduction algorithm for n ≥ 2k

We recall slide reduction and its algorithm for lattices with any rank n ≥ 2k presented in [START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF]. It uses the notion below:

A basis C of rank d is δ-twin-reduced [ALNS20] if C [1,d-1] is δ-HSVP-reduced and C [2,d] is δ-DHSVP-reduced. Definition 1 ([ALNS20, Def. 2]). Let n, k, p, q be integers s.t. n = pk + q ≥ 2k with 0 ≤ q < k and k ≥ 2, and let δ ≥ 1. A basis B ∈ R m×n is (δ, k)-slide-reduced if it
is size-reduced and satisfies the conditions below:

1. Twin condition: The block

B [1,k+q+1] is (δ 2 γ k ) k+q-1 2(k-1) -twin-reduced. 2. Primal conditions: for all i ∈ [1, p -1] Z , the block B [ik+q+1,(i+1)k+q] is δ-SVP-reduced. 3. Dual conditions: for all i ∈ [1, p -2] Z , the block B [ik+q+2,(i+1)k+q+1] is δ-DSVP-reduced. 1
If q = 0, it is essentially the original slide reduction (see [GN08a, Def. 1]). If q > 0, we can use any δ-SVP oracle in rank k to efficiently realize the twin condition, thanks to the DBKZ algorithm [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF] (see Alg. 4 revisited in App. A). By combining Alg. 4 with the original slide reduction algorithm [GN08a, Alg. 1], Alg. 1 computes slide-reduced bases by repeating polynomially many slide tours until no more progress is made. Here, a slide tour refers to a single execution of Steps 2-12 and uses a δ-SVP oracle in rank k.

As is common in the standard potential analyses of lattice reduction algorithms [LLL82, GN08a, LN14], using the integrality of the input lattice and the integral potential P (B) := p-1 i=1 vol(B [1,ik+q] ) 2 ∈ Z + , the authors showed the correctness and efficiency of Alg. 1:

Algorithm 1 The slide-reduction algorithm for n ≥ 2k [ALNS20, Alg. 3] Input: Block size k ≥ 2, slack ε > 0, approximation factor δ ≥ 1, a basis B = (b1, . . . , bn) ∈ Z m×n of a lattice L of rank n = pk + q ≥ 2k for 0 ≤ q < k, and access to a δ-SVP oracle for lattices with rank k. Output: A ((1 + ε)δ, k)-slide-reduced basis of L(B).

1: while vol(B [1,ik+q] ) 2 is modified by the loop for some

i ∈ [1, p -1] Z do 2: (1 + ε)η-HSVP-reduce B [1,k+q] using Alg. 4 for η := (δ 2 γ k ) k+q-1 2(k-1) . 3: for i = 1 to p -1 do 4: δ-SVP-reduce B [ik+q+1,(i+1)k+q] . 5:
end for 6:

if B [2,k+q+1] is not (1 + ε)η-DHSVP-reduced, then 7:

(1 + ε) 1/2 η-DHSVP-reduce B [2,k+q+1] using Alg. 4. 8: end if 9:

for i = 1 to p -2 do 10:

Find a new basis

C := (b1, . . . , b ik+q+1 , c ik+q+2 , . . . , c (i+1)k+q+1 , b ik+q+2 , . . . , bn) of L by δ-DSVP-reducing B [ik+q+2,(i+1)k+q+1] . 11: if (1 + ε) b * (i+1)k+q+1 < c * (i+1)k+q+1 then B ← C. 12:
end for 13: end while 14: return B.

Theorem 1 ([ALNS20, Th. 8]). For ε ∈ (0, 1], given as input a basis B 0 ∈ Z m×n of a lattice L of rank

n = pk + q ≥ 2k for 0 ≤ q < k, Alg. 1 makes at most (p-1)(n+q)•log B0 log(1+ε) (∈ O n 2 •log B0 kε ) slide tours,
and outputs a ((1 + ε)δ, k)-slide-reduced basis of L.

Remark 1. The potential D B used by Schnorr [START_REF] Schnorr | Fast factoring integers by SVP algorithms[END_REF] in the complexity analysis of the original slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF]

with blocksize k = n p ∈ Z is indeed D B = p-1 i=1 vol(B [1,ik] ) 2 vol(B) p-1
. We mention that D B ≤ 1 (cf. [Sch21, Th. 6.8]) is not enough to guarantee slide-reducedness. For instance, the LLL-reduced basis

C = Diag(1, 1, 1, 4 3 , 1, 1) ∈ R 6×6 satisfies D C ≤ 1 w.r.t. blocksize 3, but is not slide-reduced in the sense of [GN08a, Def. 1], because C [4,6] is not SVP/HKZ-reduced.

Generic slide reduction

In this section, we present a generic slide reduction algorithm, of which all of [GN08a, Alg. 1], [LN14, Alg. 3] and Alg. 1 are only particular instantiations. We aim to provide universal time/quality analyses of slide-type reductions: it allows to better understand which properties of slide reduction [GN08a, ALNS20] are essential for approximating HSVP, and to modify slide reduction while preserving its most important properties.

Definition and properties

In order to present our generic slide reduction, we first generalize the HSVP reduction, DHSVP reduction and the twin reduction used in slide reduction [START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF]. These generalizations are straightforward: Definition 2. Let B be a basis of rank n where n > r ≥ 1, and let h ≥ 1.

-

B is (h, r)-reduced if vol(B [1,r] ) ≤ h (n-r)r • vol(B) r/n ; -B is (h, r)-dual-reduced if the reversed dual basis B -s is (h, r)-reduced; -B is (h, r)-twin-reduced if B [1,n-r] is (h, r)-reduced and B [r+1,n] is (h, r)-dual-reduced.
(Here, we assume n > 2r.)

A typical reduced basis B is usually (h, r)-reduced for some constant h and some appropriate indices r, both of which depend on the lattice reduction algorithm. For example, if B is LLL-reduced, it follows from [PT08, Eq. (3)] that for any index r ∈

[1, n -1] Z , we have vol(B [1,r] ) ≤ 2 (n-r)r/4 • vol(B) r/n and hence B is (2 1/4 , r)-reduced. Consider a projected block B [i,j] of rank d = j -i + 1 > r. If B [i,j] is (h, r)-reduced, this implies: vol(B [i,j] ) 1/d ≤ h r • vol(B [i+r+1,j] ) 1/(d-r) . If B [i,j] is (h, r)-dual-reduced, then vol(B [i,j] ) r/d ≤ h (d-r)r • vol(B [j-r+1,j]
), which has two equivalent forms:

vol(B [i,j-r] ) 1/(d-r) ≤ h d • vol(B [j-r+1,j] ) 1/r and vol(B [i,j-r] ) ≤ h (d-r)r • vol(B [i,j] ) (d-r)/d .
Definition 3 (Generic slide reduction). Let n, k, p, q, r be integers such that n = pk + q ≥ 2k with 0 ≤ q < k and k > r ≥ 1, and let h ≥ 1. A basis B ∈ R m×n is (h, k, r)-slide-reduced if it is size-reduced and satisfies the following three sets of conditions. 1. Twin condition: The block B [1,k+q+r] is (h, r)-twin-reduced.

Primal conditions: for all

i ∈ [1, p -1] Z , the block B [ik+q+1,(i+1)k+q] is (h, r)-reduced. 3. Dual conditions: for all i ∈ [1, p -2] Z , the block B [ik+q+r+1,(i+1)k+q+r] is (h, r)-dual-reduced.
Notice that any (δ, k)-slide-reduced basis in the sense of Def. 1 is ((δ 2 γ k ) 1 2(k-1) , k, 1)-slide-reduced, while any (1+ε, r)-block-Rankin reduced basis with block size k in the sense of [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF]Def. 3

] is (((1+ε)γ k,r ) 1 2(k-r)r , k, r)- slide-reduced.
Some main properties of generic slide reduction are illustrated below.

Theorem 2. Let n, k, p, q, r be integers such that n = pk + q ≥ 2k with 0 ≤ q < k and k > r ≥ 1, and let

h ≥ 1. If B is a (h, k, r)-slide-reduced basis of an n-rank lattice L, then vol(B [1,r] ) ≤ h (n-r)r • vol(L) r/n , (2)
vol(B [1,ik+q] ) ≤ h (ik+q)(n-ik-q) • vol(L) (ik+q)/n for i = 1, . . . , p -1. (3)
We prove this theorem with the following simple fact: Proof of Th. 2. Since B [1,k+q+r] and each B [ik+q+1,(i+1)k+q+r] are (h, r)-twin-reduced, the primal conditions and Fact 3 allow to deduce:

Fact 3. Let d, k, r be integers such that d ≥ k > r ≥ 1, and let h ≥ 1. If C is a basis of rank (d + k) such that C [1,d+r] is (h, r)-twin-reduced and C [d+1,d+k] is (h, r)-reduced, then vol(C [1,d] ) 1/d ≤ h d+k • vol(C [d+1,d+k] ) 1/k . Proof. Since C [1,d] is (h, r)-reduced and C [r+1,d+r] is (h, r)-dual-reduced, we have vol(C [1,d] ) 1/d ≤ h r • vol(C [r+1,d] ) 1/(d-r) and vol(C [r+1,d] ) 1/(d-r) ≤ h d • vol(C [d+1,d+r] ) 1/r .
vol(B [1,k+q] ) 1/(k+q) ≤ h 2k+q • vol(B [k+q+1,2k+q] ) 1/k , vol(B [ik+q+1,(i+1)k+q] ) 1/k ≤ h 2k • vol(B [(i+1)k+q+1,(i+2)k+q] ) 1/k for i = 1, . . . , p -2. Now, let i ∈ [1, p -1] Z be
fixed. By combining the above inequalities, we have:

vol(B [1,k+q] ) 1/(k+q) ≤ h 2ik+q • vol(B [ik+q+1,(i+1)k+q] ) 1/k , vol(B [gk+q+1,(g+1)k+q] ) 1/k ≤ h 2(i-g)k • vol(B [ik+q+1,(i+1)k+q] ) 1/k for g = 1, , . . . , i -1, vol(B [ik+q+1,(i+1)k+q] ) 1/k ≤ h 2(j-i)k • vol(B [jk+q+1,(j+1)k+q] ) 1/k for j = i, . . . , p -1.
We make products of the above inequalities to deduce k+q) . Combining it with Eq.(3) for i = 1, this proves Eq.(2) and hence Th. 2.

vol(B [1,ik+q] ) 1/(ik+q) ≤ h (i+1)k+q • vol(B [ik+q+1,(i+1)k+q] ) 1/k , vol(B [ik+q+1,(i+1)k+q] ) 1/k ≤ h (p-i-1)k • vol(B [ik+q+1,n] ) 1/((p-i)k) .

This implies vol(B

[1,ik+q] ) 1/(ik+q) ≤ h n • vol(B [ik+q+1,n] ) 1/((p-i)k) , which is equivalent to Eq.(3). Since B [1,k+q] is (h, r)-reduced, we have vol(B [1,r] ) ≤ h (k+q-r)r • vol(B [1,k+q] ) r/(

A reduction algorithm

Our generic slide reduction algorithm is Alg. 2, which aims to provide a universal algorithmic framework of slide-type reductions.

Just like [GN08a, Alg. 1] and [LN14, Alg. 3], (h, r)-(dual-)reducing any projected block B [•,•] does not change the input lattice, and does not modify the basis vectors outside the block. Many lattice reduction algorithms (such as LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], BKZ [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF], and even slide-reduction itself) can be used to do (h, r)-(dual-)reductions (w.r.t. different h).

We remark that it is folklore to insert LLL-reductions in lattice reduction algorithms, because it cheaply guarantees that the final basis is "short" and that all intermediate entries during execution remain polynomially bounded (see, e.g., [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF] for details). Since LLL never increases vol(B [1,j] ) for any j ∈ [1, n] Z during execution, it can be checked that our analyses in both the proof of Th. 4 and Sect. 4 still work with LLL-reduction right after Step 5 or Step 11.

Algorithm 2 GSR: a generic slide reduction algorithm Input: Block size k > r ≥ 1, quality factor h ≥ 1, a basis B of a lattice L of rank n = pk + q ≥ 2k for 0 ≤ q < k, and two slack factors 0 ≤ εq, ε k ≤ 1. Output: A new basis of L.

1: repeat 2:

((1 + εq) 1/((k+q-r)r) h, r)-reduce B [1,k+q] . //A GSR tour refers to a single execution of Steps 2-11.

3:

for i = 1 to p -1 (possibly in parallel) do 4:

(h, r)-reduce B [ik+q+1,(i+1)k+q] . 5:

end for 6:

if B [r+1,k+q+r] is not ((1 + εq) 1/((k+q-r)r) h, r)-dual-reduced, then 7:

((1 + εq) 0.5/((k+q-r)r) h, r)-dual-reduce B [r+1,k+q+r] . 8:

end if 9: if B [ik+q+r+1,(i+1)k+q+r] is not ((1 + ε k ) 0.5/((k-r)r) h, r)-dual-reduced for some i ∈ [1, p -2] Z , then 10: (h, r)-dual-reduce B [ik+q+r+1,(i+1)k+q+r] . 11:
end if 12: until no change occurs or termination is requested, and return B.

By slightly adapting the standard integral potential used in [START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF], we show that within a sufficient number of GSR tours independent of the input LLL-reduced basis, Alg. 2 still outputs slide-reduced bases: Theorem 4. Let n, k, p, q, r be integers such that n = pk + q ≥ 2k with 0 ≤ q < k and 1 ≤ r < k. Let h ≥ 1 be the quality factor. Let ε q , ε k be two slack factors such that 0 < ε k ≤ 1, ε q = 0 if q = 0 and ε q = ε k otherwise. Given as input an LLL-reduced basis B 0 ∈ R m×n of a lattice L of rank n, Alg. 2 makes at most

(p-1)n 2 log(1+ε k ) (∈ O( n 3 kε k ))
GSR tours, and outputs a ((1 + ε k ) 1/((k-r)r) h, k, r)-slide-reduced basis of L.

Proof. First, notice that if Alg. 2 terminates, then its output must be ((1 + ε k ) 1/((k-r)r) h, k, r)-slide-reduced.

It remains to bound the number of GSR tours. Let B ∈ R m×n denote the current basis during the execution of Alg. 2 . We consider a ratio potential of the form

τ (B) := p-1 i=1 vol(B [1,ik+q] ) 2 m ik+q (L) 2 ≥ 1.
Since the input basis B 0 is LLL-reduced, the initial potential satisfies log τ (B 0 ) ≤ (p -1)n 2 (see [PT08, Eq. (2)]). Every operation in Alg. 2 either preserves or significantly decreases τ (B). In particular, the potential is unaffected by the primal steps (i.e., Steps 2 and 4), which leave vol(B [1,ik+q] ) unchanged for all i. The dual steps (i.e., Steps 7 and 10) either leave vol(B [1,ik+q] ) for all i or decrease τ (B) by a multiplicative factor of at least (1 + ε k ): for instance, if Step 9 occurs for some index i, namely vol(B [ik+q+r+1,(i+1

)k+q] ) > √ 1 + ε k h (k-r)r •vol(B [ik+q+r+1,(i+1)k+q+r] ) (k-r)/k , then
Step 10 will update b ik+q+r+1 , . . . , b (i+1)k+q+r such that the above inequality becomes vol(B [ik+q+r+1,(i+1)k+q] ) ≤ h (k-r)r • vol(B [ik+q+r+1,(i+1)k+q+r] ) (k-r)/k . Therefore, Alg. 2 updates vol(B [1,ik+q] ) for some i at most N times, where N := log τ (B0) log(1+ε k ) ≤ (p-1)n 2 log(1+ε k ) . This completes the proof.

Implications

Revisiting [LN14, Alg. 3]. Our Alg. 2 with (h, q, ε k ) = (γ Revisiting [ALNS20, Alg. 2]. The potential analysis used in Sect. 3.2 also works well for analyzing the ALNS slide reduction algorithm for n = k + q ∈ [k + 2, 2k] [ALNS20, Alg. 2]: under their notation and with the ratio potential τ (B) =

1 2(k-r)r k,r , 0, ε) is exactly [LN14,
vol(B [1,q] ) mq(L(B)) ≥ 1 (instead of their integral potential P (B) = vol(B [1,q] ) 2 ∈ Z + ), if the input basis B 0 is LLL-reduced, then [ALNS20, Alg. 2] makes at most qk log(1+ε) + k -q (∈ O( qk ε )
) calls to the SVP-oracle (rather than their claimed number qk log B0 log(1+ε)

(∈ O( qk log B0 ε
)) and outputs a slide-reduced basis of the input lattice.

Revisiting [ALNS20, Alg. 3]. Our Alg. 2 with (h, ε q , ε k ) = ((δ 2 γ k ) 1 2(k-1) , ε, ε) is essentially [ALNS20, Alg. 3] (i.e. Alg. 1). If the input basis B 0 is LLL-reduced, Th. 4 allows to remove the dependence on B 0 from the claimed number of tours in Th. 1: Corollary 2. For ε ∈ (0, 1], given as input an LLL-reduced basis B 0 ∈ R m×n of a lattice L of rank n = pk + q ≥ 2k for 0 ≤ q < k, Alg. 1 makes at most (p-1)n 2 log(1+ε) (∈ O( n 3 kε )) slide tours, and outputs a ((1 + ε)δ, k)slide-reduced basis of L.

Remark 2. When Alg. 1 terminates, it outputs a ((1 + ε)δ, k)-slide-reduced basis (b 1 , . . . , b n ) of the input lattice L. By directly applying [ALNS20, Th. 7], it has the following properties:

b 1 ≤ (((1 + ε)δ) 2 γ k ) n-1 2(k-1) vol(L) 1/n , (4)
and if λ 1 (L(B [1,k+q] )) > λ 1 (L) , then b 1 ≤ (1 + ε)δ(((1 + ε)δ) 2 γ k ) n-k k-1 λ 1 (L) . (5)
As mentioned in Sect. 1, if L is a random lattice, it follows from the Gaussian heuristic that Property (4) might imply Property (5) in practice. This is why current security estimates in lattice-based cryptographic constructions actually rely on HSVP estimates [START_REF] Gama | Predicting lattice reduction[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]. So, one may be interested to wonder whether Property (4) can be achieved with fewer slide tours. Besides, the potential analysis used in Sect. 3.2 can not analyse the current basis during the execution of Alg. 1. This is the topic of the next section.

Dynamic analysis of generic slide reduction

In this section, we adapt the discrete dynamical system analysis of Hanrot et al. [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] to GSR (Alg. 2). This allows to claim Property (4) with fewer slide tours. Furthermore, we may use this analysis to model the practical behaviour of slide-reductions [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF][START_REF] Aggarwal | Slide reduction, revisitedfilling the gaps in SVP approximation[END_REF]. Finally, this analysis provides guarantees on the quality of the current basis during execution (see Eq. (7) in Prop. 1). In Sect. 6, we develop Eq. ( 7) into a heuristic simulator, which can be used to predict the evolution of the RHF during execution.

The main result of this section is as follows:

Theorem 5. Let n, k, p, q, r be integers such that n = pk + q ≥ 2k with 0 ≤ q < k and 1 ≤ r < k. Let h ≥ 1 be the quality factor. Let ε q , ε k be two slack factors such that ε k = 0, ε q = 0 if q = 0 and ε q = ε otherwise, where 0 < ε ≤ 0.4. Given as input an LLL-reduced basis B 0 of an n-rank lattice L in R m , if terminated after

n 2 ln n-k-q 4 log(1+ε) 8(k-r)r (∈ O( n 2 ln n ε (k-r)r )) GSR tours, then Alg. 2 outputs a basis B of L such that vol(B [1,ik+q] ) ≤ (1 + ε) (ik+q)(p-i) p-1 h (ik+q)(n-ik-q) • vol(L) (ik+q)/n for i = 1, . . . , p -1,
where h = (1 + ε q ) 1/((k+q-r)r) h. One more execution of Step 2 yields

vol(B [1,r] ) ≤ (1 + ε) r h (n-r)r • vol(L)
) = (γ 1 2(k-r)r k,r
, 0) that with fewer tours, [LN14, Alg. 3] can obtain a basis whose bound on vol(B [1,r] ) is almost the same as that of full block-Rankin reduction: Corollary 3. Let n, k, p, r be integers such that n = pk ≥ 2k with k > r ≥ 1, and let 0 < ε ≤ 0.4. Given as input an LLL-reduced basis B 0 of an n-rank lattice L in R m , if terminated after

n 2 ln n-k 4 log(1+ε) 8(k-r)r (∈ O( n 2 (k-r)r • ln n ε )
) tours, then [LN14, Alg. 3] with one more execution to its Step 4 outputs a basis B of L such that

vol(B [1,r] ) ≤ (1 + ε) r γ n-r 2(k-r) k,r • vol(L) r n .
Revisiting [ALNS20, Alg. 3]. It follows from Th. 5 with (h, r) = ((δ 2 γ k ) 1 2(k-1) , 1) that with fewer tours, Alg. 1 can still obtain a basis whose RHF is almost the same as that in Property (4) for full slide-reduction.

Notice that the dynamic analysis for Th. 5 is agnostic to the quality factor h. Under the weak version of the Gaussian heuristic (cf. Sect. 2.1), Th. 5 can also be used to model the practical behaviour of slide-reductions [GN08a, ALNS20]: Corollary 4. Let n, k, p, q be integers such that n = pk + q ≥ 2k with 0 ≤ q < k and k ≥ 2. Let δ ≥ 1 and 0 < ε ≤ 0.4. Let ε q = 0 if q = 0 and ε q = ε otherwise. Given as input an LLL-reduced basis B 0 of an

n-rank lattice L in R m , if terminated after n 2 ln n-k-q 4 log(1+ε) 8(k-1) (∈ O( n 2 ln n ε k
)) slide tours, then Alg. 1 with one more execution to its Step 2 outputs a basis (b 1 , . . . , b n ) of L satisfying the following properties.

1. Worst-case: b 1 ≤ (1 + ε)(1 + ε q ) n-1 k+q-1 (δ 2 γ k ) n-1 2(k-1) vol(L) 1/n . 2. Average-case: Suppose that every projected lattice Λ of rank k passed to (D)(H)SVP-reductions of Alg. 1 satisfies λ 1 (Λ) ≤ (1 + ξ)GH(k) • vol(Λ) 1/k for some ξ ∈ (0, √ 2 -1], we have b 1 /vol(L) 1/n ≤ (1 + ε)(1 + ε q ) n-1 k+q-1 ((1 + ξ)GH(k)) n-1 k-1 ≈ k 2πe n-1 2(k-1)
.

Remark 3. 1. The output basis in Cor. 4 might not be slide-reduced in the sense of Def. 1: hence, it might not satisfy Property (5) and the twin-reducednesses of B [1,ik+q+1] for i = 1, . . . , p -1. 2. The dependence of time/quality trade-offs on ε in Cor. 4.1 is better than that in Cor. 2, especially for k = o(n). For instance, in order to claim b

1 ≤ (1 + ε) n-1 k-1 γ n-1 2(k-1) k vol(L) 1/n in the case q = 0, Cor. 2 requires at most (n-k)n 2 k log(1+ε) (∈ O( n 2 k • n ε )
) slide tours, while Cor. 4.1 requires at most

n 2 ln (k-1)(n-k) 4(n-1) log(1+ε) 8(k-1) (∈ O( n 2 k • ln n ε
)) slide tours. 3. Our estimate in the average-case of Cor. 4.2 (ignoring both ε and ξ) matches well with experiments in Sect. 5.2 (see Fig. (1c)).

A dynamical system for GSR tours

We use the following profile function to do the dynamic analysis of GSR: given a basis B of rank n = pk +q ≥ 2k for 0 ≤ q < k, its bit profile is:

G(B) = (G 1 (B), G 2 (B), . . . , G p-1 (B)) T ∈ R p-1 with each G i (B) = log vol(B [1,ik+q] ) vol(B) (ik+q)/n 1 (ik+q)(n-ik-q) .
In what follows, we also use the notations:

β = (k -r)r k 2 , θ = k + q -r k + q
and ω i = (ik + q)(n -ik -q) for i = 1, . . . , p.

Proposition 1. Let n, k, p, q, r be integers s.t. n = pk + q ≥ 2k with 0 ≤ q < k and 1 ≤ r < k. Let ε q , ε k be two slack factors such that ε k = 0, ε q = 0 if q = 0 and ε q ∈ (0, 1] otherwise. Let h ≥ 1 be the quality factor in Alg. 2 and h = (1 + ε q ) 1/((k+q-r)r) h. If a GSR tour transforms a basis B of L into another basis

C of L, then G(C) ≤ A • G(B) + b, (6)
where the matrix A ∈ Q (p-1)×(p-1) and vector b ∈ Q p-1 are defined by

A =                  r 2 (k+q) 2 + (k-r)θ k θ•r•ω2 k•ω1 βω1 ω2 1 -2β βω3 ω2 βω2 ω3 1 -2β βω4 ω3 . . . . . . . . . . . . . . . . . . . . . . . . . . . βωp-3 ωp-2 1 -2β βωp-1 ωp-2 βωp-2 ωp-1 1 -2β                  and b = (r log h) •                  (2k+q)θ ω1 2(k-r) ω2 2(k-r) ω3 . . . . . . . . . 2(k-r) ωp-2 2(k-r) ωp-1                  .
Moreover, let y ∈ R n be a fixed point of the dynamical system x ← Ax + b. If B 0 is the input basis of L to GSR and B is the current basis at the end of the -th GSR tour, then

G(B ) ≤ y + A • (G(B 0 ) -y) for ∀ ∈ Z + . ( 7
)
Proof. Let E be the current basis right after Step 5 of GSR such that Steps 2-5 transform the basis B into E and then Steps 6-11 transform the basis E into C. The main issue is to connect B with C.

To do so, we first establish the relation between B and E:

vol(E [1,r] ) ≤ h (k+q-r)r • vol(B [1,k+q] ) r/(k+q) , (8) vol
(E [1,ik+q+r] ) ≤ h (k-r)r • vol(B [1,ik+q] ) (k-r)/k • vol(B [1,(i+1)k+q] ) r/k for i = 1, . . . , p -1. ( 9
)
Proof of Eq. (8) and Eq. (9). Eq. ( 8) is ensured by Step 2. For i = 1, . . . , p -1, we have

vol(E [1,ik+q+r] ) = vol(B [1,ik+q] ) • vol(E [ik+q+1,ik+q+r] ) (Since vol(B [1,ik+q] ) = vol(E [1,ik+q] )) ≤ h (k-r)r • vol(B [1,ik+q] ) • vol(E [ik+q+1,(i+1)k+q] ) r/k (Due to Step 4) = h (k-r)r • vol(B [1,ik+q] ) • vol(B [ik+q+1,(i+1)k+q] ) r/k = h (k-r)r • vol(B [1,ik+q] ) (k-r)/k • vol(B [1,(i+1)k+q] ) r/k .
Thus, we proved Eq. ( 8) and Eq. ( 9). We next use Eq. ( 8) and Eq. ( 9) to establish the relation between B and C:

vol(C [1,k+q] ) ≤ h (2k+q)θr • vol(B [1,k+q] ) r 2 (k+q) 2 + (k-r)θ k • vol(B [1,2k+q] ) θ•r k , ( 10
) vol(C [1,ik+q] ) ≤ h 2(k-r)r • vol(B [1,(i-1)k+q] ) β • vol(B [1,ik+q] ) 1-2β • vol(B [1,(i+1)k+q] ) β for i = 2, . . . , p -1. ( 11
)
Proof of Eq. (10) and Eq. (11). Using the connection between E and C, we first argue Eq. (10):

vol(C [1,k+q] ) = vol(E [1,r] ) • vol(C [r+1,k+q] ) (Since vol(E [1,r] ) = vol(C [1,r] )) ≤ h (k+q-r)r • vol(E [1,r] ) • vol(C [r+1,k+q+r] ) θ (Due to Steps 6-8) = h (k+q-r)r • vol(E [1,r] ) • vol(E [r+1,k+q+r] ) θ (Since vol(E [r+1,k+q+r] ) = vol(C [r+1,k+q+r] )) = h (k+q-r)r • vol(E [1,r] ) 1-θ • vol(E [1,k+q+r] ) θ ≤ h (2k+q)θr • vol(B [1,k+q] ) r 2 (k+q) 2 + (k-r)θ k • vol(B [1,2k+q] ) θ•r
k . (Applying Eq. (8) and Eq. ( 9))

For i = 2, . . . , p -1, since vol(E [1,(i-1)k+q+r] ) = vol(C [1,(i-1)k+q+r] ), we have vol(C [1,ik+q] ) = vol(E [1,(i-1)k+q+r] ) • vol(C [(i-1)k+q+r+1,ik+q] ) ≤ h (k-r)r • vol(E [1,(i-1)k+q+r] ) • vol(C [(i-1)k+q+r+1,ik+q+r] ) (k-r)/k (Due to Steps 9-11) = h (k-r)r • vol(E [1,(i-1)k+q+r] ) • vol(E [(i-1)k+q+r+1,ik+q+r] ) (k-r)/k = h (k-r)r • vol(E [1,(i-1)k+q+r] ) r/k • vol(E [1,ik+q+r] ) (k-r)/k ≤ h 2(k-r)r • vol(B [1,(i-1)k+q] ) β • vol(B [1,ik+q] ) 1-2β • vol(B [1,(i+1)k+q] ) β .
(By Eq. ( 9)) Thus, we proved Eq. (10) and Eq. ( 11).

With the notation G i (•), Eq. (10) and Eq. ( 11) are respectively equivalent to the inequalities below:

G 1 (C) ≤ r 2 (k + q) 2 + (k -r)θ k G 1 (B) + θ • r • ω 2 k • ω 1 G 2 (B) + (2k + q)θr ω 1 log h, G i (C) ≤ βω i-1 ω i G i-1 (B) + (1 -2β)G i (B) + βω i+1 ω i G i+1 (B) + 2(k -r)r ω i log h for i = 2, . . . , p -1.
Their matrix form is exactly Eq. ( 6). It remains to show Eq. ( 7), which is done by induction on . First, since b = y -Ay, Eq. ( 6) implies Eq. ( 7) for = 1. Assume that Eq. ( 7) holds for some ∈ Z + .

The crucial fact A ≥ 0 allows us to deduce the following third row:

G(B +1 ) ≤ A • G(B ) + b (By Eq. (6)) = y + A(G(B ) -y) (Since b = y -Ay) ≤ y + A +1 (G(B 0 ) -y).
(By the induction hypothesis) Thus, we proved Eq. ( 7). This completes the proof of Prop. 1.

Properties of the dynamical system

Thanks to Eq. ( 6), the effect of a GSR tour on G(B) can be interpreted as the dynamical system

x ← Ax + b. (12)
Its fixed point(s) and speed of convergence encode information on the output quality and runtime of GSR, respectively, as illustrated by Eq. (7). The system (12) converges and has a unique fixed point:

Proposition 2. Under the notation of Sect. 4.1, we have:

1. A has row sum norm: A ∞ ≤ 1 -8(k-r)r n 2 . 2. The system x ← Ax + b has a unique fixed point: y = (log h) • (1, . . . , 1) T ∈ R p-1 . 3. The tail term in Eq. (7) converges to zero: if c is a positive real s.t. c ≥ max 1≤i<p G i (B 0 ), then A • (G(B 0 ) -y) ≤ c • A ∞ • (1, . . . , 1) T for any ∈ Z + .
Proof. We first show Item 1. For i = 2, . . . , p -2, the sum of the i-th row of A is

S i = 1 + β • ω i-1 + ω i+1 ω i -2 = 1 - 2k 2 β (ik + q)(n -ik -q) ≤ 1 - 8k 2 β n 2 = 1 - 8(k -r)r n 2 .
A direct calculation by hand shows: max{S

1 , S p-1 } ≤ 1 -8(k-r)r n 2
. This proves Item 1. We now show Item 2. A direct calculation by hand shows:

log h = r 2 (k + q) 2 + (k -r)θ k log h + θ • r • ω 2 k • ω 1 • log h + (2k + q)θr ω 1 log h, log h = βω i-1 ω i • log h + (1 -2β) log h + βω i+1 ω i • log h + 2(k -r)r ω i log h for i = 2, . . . , p -1.
Their matrix form is exactly y = Ay + b.

To show the unicity, we assume that y ∈ Q p-1 also satisfies y = Ay + b. Then yy = A(yy) implies yy ∞ ≤ A ∞ • yy ∞ . Since A ∞ < 1, we have yy ∞ = 0. Thus, y = y. This proves Item 2.

It remains to show Item 3. The crucial fact A ≥ 0 allows us to deduce the following inequalities:

A • (G(B 0 ) -y) ≤ A • G(B 0 ) (Since y ≥ 0) ≤ c • A • (1, . . . , 1) T (Since c ≥ max 1≤i<p G i (B 0 )) ≤ c • A ∞ • (1, . . . , 1) T ≤ c • A ∞ • (1, . . . , 1) T .
This proves Item 3 and completes the proof of Prop. 1.

Proof of Theorem 5

We now show Th. 5 under the notation of Sections 4.1-4.2. Let be any integer such that ≥

n 2 ln n-k-q 4 log(1+ε) 8(k-r)r . Since 1 -x ≤ e -x for 0 ≤ x ≤ 1, Prop. 2.1 implies 1 4 • A ∞ ≤ 1 4 1 - 8(k -r)r n 2 ≤ 1 4 e -8 (k-r)r n 2 ≤ log(1 + ε) n -k -q .
Let B be the current basis at the end of the -th GSR tour. Since the input basis B 0 is LLL-reduced, we have G(B 0 ) ≤ 1 4 • (1, . . . , 1) T (see [PT08, Eq. (3)]). Applying Prop. 2.2 to Eq. ( 7), we have:

G(B ) ≤ y + A • (G(B 0 ) -y) ≤ y + 1 4 • A ∞ • (1, . . . , 1) T (By Prop. 2.3) ≤ y + log(1 + ε) n -k -q • (1, . . . , 1) T = log (1 + ε) 1/(n-k-q) h • (1, . . . , 1) T .
By the definition of G(•), this implies the desired upper bounds of vol(B [1,ik+q] )/vol(L) (ik+q)/n in Th. 5. The remaining inequality is ensured by Step 2 of Alg. 2. This completes the proof of Th. 5.

HKZ-slide reduction

Notice that solving (r, k)-DSP for larger r ∈ [2, k -2] Z is much more expensive than solving SVP in rank k [START_REF] Dadush | Algorithms for the densest sub-lattice problem[END_REF]. Both Th. 4 and Th. 5 suggest that one might replace the exact (r, k)-DSP solver in block-Rankin reduction [LN14, Alg. 3] with cheaper procedures for approximating (r, k)-DSP.

Based on the three observations illustrated in Sect. 1, we replace the exact (r, k)-DSP solver in [LN14, Alg. 3] with any r-partial-HKZ solver in rank k: An n-rank basis B is r-partial-HKZ-reduced for r ∈ [1, n] Z if it is size-reduced and B [i,n] is SVP-reduced for i = 1, . . . , r. For r = O(1), it is cheaper than full HKZ-reduction (defined as in Sect. 2) in practice.

If a projected block B [i,j] of rank k = j -i + 1 > r is r-partial-HKZ-reduced, Hanrot and Stehlé [HS07, Lem. 3] proved that it approximates (r, k)-DSP quite well especially for small r = O(1):

vol(B [i,i+r-1] ) ≤ k i=k-r+1 γ k-r 2(i-1) i • vol(B [i,j] ) r/k .
We now present our cheaper analogue of block-Rankin-reduction [START_REF] Li | Approximating the densest sublattice from Rankin's inequality[END_REF]: Definition 4 (HKZ-slide reduction). Let n, k, p, r be integers such that n = pk ≥ 2k with k > r ≥ 1. A basis B ∈ R m×n is (r, k)-HKZ-slide-reduced if it is size-reduced and satisfies the following two sets of conditions. 1. Primal conditions: for all i ∈ [1, p -1] Z , the block B [ik+1,ik+k] is r-partial-HKZ-reduced.

Dual conditions: for all

i ∈ [1, p-2] Z , the reversed dual basis (B [ik+r+1,ik+k+r] ) -s of block B [ik+r+1,ik+k+r]
is r-partial-HKZ-reduced.

HKZ-slide reduction can be viewed a higher-dimensional generalization of the original slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF] (corr. to r = 1), and is also a particular instantiation of our generic slide reduction presented in Sect. 3. Therefore, we apply Th. 2 to deduce the following estimate for approximating HSVP: Theorem 6. Let n, k, p, r be integers such that n = pk ≥ 2k with k > r ≥ 1.

If B = (b 1 , . . . , b n ) ∈ R m×n is a (r, k)-HKZ-slide-reduced basis of a lattice L, then b 1 ≤ √ γ k k i=k-r+1 γ n-k 2(i-1)r i • vol(L) 1/n . Proof. Th. 2 with (h, q) = ( k i=k-r+1 γ 1 2(i-1)r i , 0) implies: vol(B [1,k] ) ≤ k i=k-r+1 γ (n-k)k 2(i-1)r i • vol(L) k/n . Since B [1,k] is r-partial-HKZ-reduced and hence SVP-reduced, we have b 1 ≤ √ γ k • vol(B [1,k] ) 1/k
. By combining the above two inequalities, Th. 6 follows.

Applying Th. 4, it is not hard to deduce that given as input an LLL-reduced basis B 0 ∈ R m×n of a lattice L of rank n = pk ≥ 2k, Alg. 2 makes at most (n-k)n 2 k log(1+ε) GSR tours, and can output a (r, k)-HKZ-slidereduced basis (b 1 , . . . , b n ) of L (up to a slack factor ε). In particular, we have:

b 1 ≤ (1 + ε) n-k (k-r)r √ γ k k i=k-r+1 γ n-k 2(i-1)r i • vol(L) 1/n . ( 13
)
It follows from Th. 5 that with fewer tours, Alg. 2 can still obtain a basis whose RHF is almost the same as that in Eq. ( 13) for full HKZ-slide-reduction. Under the weak version of the Gaussian heuristic (cf. Sect. 2.1), Th. 5 can also be used to model the practical behaviour of HKZ-slide-reduction:

Corollary 5. Let n, k, p, r be integers such that n = pk ≥ 2k with k > r ≥ 1. Let 0 < ε ≤ 0.4. Given as input an LLL-reduced basis B 0 of an n-rank lattice L in R m and access to an oracle for r-partial-HKZ-reducing any lattice of rank k, if terminated after

n 2 ln n-k 4 log(1+ε) 8(k-r)r (∈ O( n 2 ln n ε (k-r)r
)) GSR tours, then Alg. 2 with one more execution to its Step 2 outputs a basis (b 1 , . . . , b n ) of L satisfying the following properties.

1. Worst-case: b 1 ≤ (1 + ε) √ γ k k i=k-r+1 γ n-k 2(i-1)r i • vol(L) 1/n . 2. Average-case: Suppose that every projected lattice Λ of rank i ∈ [k -r + 1, k] passed to r-partial-HKZ- reductions satisfies λ 1 (Λ) ≤ (1 + ξ)GH(i) • vol(Λ) 1/i for some ξ ∈ (0, √ 2 -1], we have b 1 /vol(L) 1/n ≤ (1 + ε)(1 + ξ)GH(k) k i=k-r+1 ((1 + ξ)GH(i)) n-k (i-1)r ≈ k 2πe • k i=k-r+1 i 2πe n-k 2(i-1)r .
Proof. Applying Th. 5 with (h, q) = ( k i=k-r+1 γ 1 2(i-1)r i , 0) to the worst-case, we have

vol(B [1,k] ) ≤ (1 + ε) k k i=k-r+1 γ (n-k)k 2(i-1)r i • vol(L) k/n .
One more execution to Step 2 ensures that the first k-rank block

B [1,k] is SVP-reduced. Thus, b 1 ≤ √ γ k • vol(B [1,k] ) 1/k
. By combining the above two inequalities, this implies Item 1.

Thanks to the assumption, Item 2 follows from replacing each √ γ i in the worst-case with (1 + )GH(i).

This proves Cor. 5.

Theoretical comparison

Hermite's constant γ i satisfies Mordell's inequality [START_REF] Mordell | Observation on the minimum of a positive quadratic form in eight variables[END_REF] and Newman's inequality [START_REF] Newman | Bounds for cofactors and arithmetic minima of quadratic forms[END_REF]:

γ (i-1)/(k-1) k ≤ γ i ≤ γ k/i k
for any integers 2 ≤ i ≤ k. GH(i) satisfies similar inequalities (cf. [ABLR21, Fact 3] and [LN20, §4.2]): GH(k) (i-1)/(k-1) ≤ GH(i) ≤ GH(k) k/i for any integers 51 ≤ i ≤ k. Thus, for k ≥ 50 + r, the larger r is, the larger both

k i=k-r+1 γ 1 (i-1)r i and k i=k-r+1 GH(i) 1 (i-1)r : γ 1 k-1 k ≤ k i=k-r+1 γ 1 (i-1)r i ≤ γ 1 k-r k and GH(k) 1 k-1 ≤ k i=k-r+1 GH(i) 1 (i-1)r ≤ GH(k) 1 k-r .
Therefore, both HSVP estimates in Cor. 5 would not outperform those for the original slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF] with the same block size k (see Cor. 4 with (δ, q) = (1, 0)). 1d) respectively. They show that HKZ-slide reduction is able to clearly outperform the naive version of BKZ, but it also seems to be better than PnJ. However, while progressive PnJ is roughly on par with HKZ-slide reduction at the beginning, it seems to have the edge towards latter stages of the execution. We believe this is because just like naive BKZ, both our theoretical analyses and experiments show that much progress of HKZ-slide reduction is done at the beginning of the execution, and quickly the basis quality becomes excellent; the rest of the execution takes much longer, for a really minor quality improvement. At this stage, progressive BKZ switches to a block size > k, whereas our implementation of HKZ-slide reduction maintains the block size. This is a perfect example of the advantages that "progressiveness" adds to block reduction algorithms. But even without this, we consider HKZ-slide reduction at least competitive with progressive PnJ.

Caveats. We focused our attention in these experiments on the RHF that the different algorithms achieve in a given amount of time. This has been established as the main measure of output quality for lattice reduction, since they are usually used to find short vectors. When targeting a short vector, (HKZ-)slide reduction has the advantage that it is focusing on improving a set of pivot points distributed across the basis, while BKZ attempts to improve the entire basis. This seems to result in lower cost for slide reduction. But finding short vectors is not the only use case: often one is interested in a basis that is reduced according to a more global measure, e.g. one wants all basis vectors to be short or the GSO vectors should not drop off too quickly. In this case, BKZ seems to be the more natural choice.

Potential Improvements. We did not make any attempts to fine-tune the SVP oracle to HKZ-slide reduction and its parameters. The SVP-oracle itself has several parameters which potentially influence how well it performs as a r-partial-HKZ reduction oracle. We leave such a fine-tuning as interesting future work.

We also notice that applying BKZ/PnJ with increasing block sizes results in significant improvements. It stands to reason that including an element of "progressiveness" could significantly improve HKZ-slide reduction. However, the strength of HKZ-slide reduction of focusing its attention on pivot points instead of the entire basis could be a disadvantage here: it may not be as suitable as a preprocessing for other algorithms, possibly including itself. Still, finding an effective way of naturally progressing slide reduction might lead to improvements, but we believe simply increasing the block size is unlikely to be sufficient here. Finally, given the above observations, a natural approach seems to be to first use progressive BKZ/PnJ as a preprocessing and then run HKZ-slide reduction in the final step to find a short vector.

A simulator for predicting (HKZ-)slide reduction

We now present a simple and efficient simulator to predict the performances of (HKZ-)slide reduction with high block size k (≥ 50 + r) in high rank. It predicts the evolution of RHF with the number of tours. Our simulation is fairly consistent with experiments. We believe that our simulator can be used to explore the "optimal" parameters (k, r) in practice (dominating time/quality trade-offs), and predict approximately what can be achieved using much larger computational power than used in our experiments.

(HKZ-)slide simulator

Both Cor. 4 and Cor. 5 claim the worst-case number of tours for computing a basis of the desired quality. In practice, it may be of interest to estimate the actual number of tours more accurately, especially the impact of the parameter r.

The goal of our simulator is to predict the RHF depending on the number of tours during the execution of Alg. 2 for (HKZ-)slide-reduction. For simplicity, we just consider the case n = pk (i.e., q = 0) in what follows.

For = 0, 1, . . ., let B = (b

( ) 1 , . . . , b ( )
n ) be the current basis at the end of the -th tour of Alg. 2 and let RHF(B ) denote its RHF. Let A ∈ Q (p-1)×(p-1) and y ∈ R p-1 be respectively the matrix and vector defined as in Prop. 1 and Prop. 2.2. Let A 1 denote the first row of A. Then Eq. ( 7) implies: for

∈ Z + , G(B ) ≤ y + A • (G(B 0 ) -y), in particular, G 1 (B ) ≤ y 1 + A 1 • (A -1 ) • (G(B 0 ) -y).
Step 2 in the ( + 1)-th tour of Alg. 2 ensures: b

( +1) 1 ≤ √ γ k • vol((B ) [1,k] ) 1/k , or equivalently, log RHF(B +1 ) ≤ log γ k 2(n -1) + n -k n -1 • G 1 (B ) for each ≥ 0.
We notice a loop invariant: b 1 never increases during the execution of Alg. 2. This implies the following key relation between RHFs of two consecutive tours: for = 0, 1, . . .,

log RHF(B +1 ) ≤ min log RHF(B ), log γ k 2(n -1) + n -k n -1 y 1 + A 1 • (A -1 ) • (G(B 0 ) -y) ,
which is equivalent to the inequality below (with

h = k i=k-r+1 γ 1 2(i-1)r i ) RHF(B +1 ) ≤ min RHF(B ), γ 1 2(n-1) k • h n-k n-1 • 2 n-k n-1 •A 1 •(A -1 )•(G(B0)-(log h)•(1,...,1) T ) .
Cor. 5.2 and the weak version of the Gaussian heuristic suggest that when every projected lattice Λ of rank i ∈ [k -r + 1, k] passed to r-partial-HKZ-reductions is "random", one might replace each Hermite's constant γ i inside the above equation with its heuristic analog GH(i) 2 . This gives rise to a heuristic (HKZ-)slide simulator for predicting RHF especially with high block size, namely Alg. 3.

We make a remark on Step 3 of Alg. 3. In the real implementation of (HKZ-)slide-reduction, if the (i + 1)th tour does not update the first basis vector, then RHF(B i+1 ) = RHF(B i ); otherwise, the (i + 1)-th tour makes the first basis vector shorter, i.e., RHF(B i+1 ) < RHF(B i ). However, in the context of simulation, if the prediction value of RHF(B i ) is already less than the dynamical system prediction f (i) := GH(k)

1 n-1 • h n-k n-1 • 2 n-k n-1 •A 1 •(A i-1
)•(G(B0)-(log h)•(1,...,1) T ) , then the simulator predicts RHF(B i+1 ) = RHF(B i ); otherwise, the simulator predicts RHF(B i+1 ) = f (i). In brief, the minimum restriction at Step 3 of Alg. 3 ensures that the prediction value of RHF(B i ) never increases during the execution of Alg. 3, just like that in the real implementation of (HKZ-)slide-reduction. For example, consider an input basis B 0 which is already SVP-reduced and whose first vector is unusually short, the simulator without this minimum restriction at its Step 3 would predict RHF(B 1 ) = f (0) > RHF(B 0 ), which contradicts the fact "RHF(B 0 ) = RHF(B 1 ) = • • • = RHF(B i ) = • • • " during the real execution of (HKZ-)slide-reduction.

Algorithm 3 A simulator of (HKZ-)slide reduction Input: A block size k > r ≥ 1 such that k ≥ 50 + r, a number ≥ 1 of tours, and the bit profile G(B0) of an n-rank basis B0 where n = pk ≥ 2k. Output: A prediction for the RHF right after tours. 1: Compute the heuristic analog h of h = k i=k-r+1 γ 1 2(i-1)r i : h ← k i=k-r+1 GH(i) 1 (i-1)r 2: for i = 0 to -1 do 3: RHF(Bi+1) ← min RHF(Bi), GH(k)

1 n-1 • h n-k n-1 • 2 n-k n-1 •A 1 •(A i-1
)•(G(B 0 )-(log h)•(1,...,1) T ) 4: end for 5: return RHF(B ).

Verification and comparison

Consistency with experiments. To verify that the simulator predicts the output of the HKZ-slide algorithm accurately, we tested it against our experimental data from Sect. 5.2 for the larger set of experiments (k = 85). We disregarded the k = 60 parameterization here, since the Gaussian heuristic is less accurate in smaller ranks. (Note that we require the Gaussian heuristic to be fairly accurate starting from rank (k -r + 1).) The results are shown in Fig. (2a).

There are small discrepancies between the predicted and the actual behavior of the algorithm, but given the small range on the y-axis, this can be viewed as a rough match. The discrepancies may be explained similarly as the "head concavity phenomenon" in BKZ [START_REF] Bai | Measuring, simulating and exploiting the head concavity phenomenon in BKZ[END_REF]: if, by chance, the SVP oracle finds a vector shorter than expected in the first block, this vector is never displaced during the execution of the algorithm (unless for an even shorter vector). We leave a further analysis along the lines of [START_REF] Bai | Measuring, simulating and exploiting the head concavity phenomenon in BKZ[END_REF] to future work.

Overall we believe that the results support the hypothesis that the simulator may be useful for the purposes we laid out in the preface of Sect. 6. We mention in passing that just like our (HKZ-)slide simulator (cf. Sect. 6.1), we can similarly develop a DBKZ simulator for predicting the RHF depending on the number of tours during the DBKZ execution, based on the dynamical system analysis in [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF].

  subgroups of R m . A lattice L in R m is represented as a set of all integer linear combinations of n linearly independent vectors b 1 , . . . , b n in R m : L = { n i=1 x i • b i , x i ∈ Z}. The matrix B := (b 1 , . . . , b n ) forms a basis of L, and the integer n is the rank of L.

  for the lattice generated by B and B = max{ b 1 , . . . , b n } for the maximum norm of a column.

  use the notations log(•) := log 2 (•), ln(•) := log e (•) and [a, b] Z := [a, b] Z for any integers a and b.

  By multiplying the above two inequalities together, this implies vol(C[1,d] ) r/d ≤ h (d+r)r • vol(C [d+1,d+r] ).The (h, r)-reducedness of C [d+1,d+k] ensures vol(C [d+1,d+r] ) ≤ h (k-r)r •vol(C [d+1,d+k] ) r/k . By multiplying the above two inequalities together, this proves Fact 3.

  Alg. 3]. The authors proved that given as input a basis B 0 , [LN14, Alg. 3] makes at most (p-1)n log B0 log(1+ε) (∈ O( n 2 log B0 kε )) tours for computing a (1 + ε, r)-block-Rankin reduced basis with block size k (see [LN14, Def. 3]). Th. 4 removes the dependence on the input LLL-reduced basis: Corollary 1. Let n = pk ≥ 2k and ε ∈ (0, 1]. Given as input an LLL-reduced basis B 0 ∈ R m×n of a lattice L of rank n, [LN14, Alg. 3] makes at most (p-1)n 2 log(1+ε) (∈ O( n 3 kε )) tours, and outputs a (1 + ε, r)-block-Rankin reduced basis with block size k of L.

  Comparison of HKZ-slide reduction and BKZ on a lattice with rank 170 and block size 85

Fig. 1 :

 1 Fig. 1: Comparison of HKZ-slide-reduction with different overlaps and with various BKZ variantsThe results are shown in Figures (1b) and (1d) respectively. They show that HKZ-slide reduction is able to clearly outperform the naive version of BKZ, but it also seems to be better than PnJ. However, while progressive PnJ is roughly on par with HKZ-slide reduction at the beginning, it seems to have the edge towards latter stages of the execution. We believe this is because just like naive BKZ, both our theoretical analyses and experiments show that much progress of HKZ-slide reduction is done at the beginning of the execution, and quickly the basis quality becomes excellent; the rest of the execution takes much longer, for a really minor quality improvement. At this stage, progressive BKZ switches to a block size > k, whereas our implementation of HKZ-slide reduction maintains the block size. This is a perfect example of the advantages that "progressiveness" adds to block reduction algorithms. But even without this, we consider HKZ-slide reduction at least competitive with progressive PnJ.

  Simulation vs. experimental results for rank 170 lattices with block size 85 and overlap 1 and 10. Black lines correspond to experimental data, blue lines to simulations on the same lattices, Solid and dotted horizontal lines correspond to expected upper bounds of RHFs in Cor. 4.2 and Cor. 5.2 (ignoring both ε and ξ) for overlap 1 and 10, respectively. (HKZ-)slide simulator vs. BKZ simulator on rank 170 lattices with block size 85. SVP calls in rank < 85 in BKZ are ignored for simplicity.

Fig. 2 :

 2 Fig. 2: Evaluation of HKZ-slide simulator

When p =

2, there are simply no dual conditions.

G6K [ADH + 19] calls fplll with default parameters to pre-reduce the lattice basis and stores it, so that future invocations do not need to redo that again.

This work was partly supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 885394). Zama, France. This work was supported by the European Research Council, ERC consolidator grant (682815 -TOCNeT). Part of this work was done while the second author was visiting the Simons Institute for the Theory of Computing at the University of California, Berkeley, for the Spring 2020

When r = O(1) > 1 is sufficiently small w.r.t. k, (r, k)-HKZ-slide-reduction can achieve almost the same HSVP estimates as those for the original slide reduction, but with fewer tours. This is because: 8(k -1) .

For instance, when (n, k, r) = (170, 85, 10), GH(k)

k-1 = 8.93. This means that with well-chosen constant r > 1, (r, k)-HKZ-slide-reduction might provide better time/quality trade-offs in practice than the original slide reduction. This hypothesis is confirmed by both our experiments in Sect. 5.2 and simulation in Sect. 6.2.

Experiments

We implemented HKZ-slide reduction in the G6K framework of [ADH + 19], which (among a lot of other things) provides an interface to an SVP algorithm based on sieving: their work shows that basic (called naive in [ADH + 19]) BKZ based on sieving starts outperforming state-of-the-art enumeration-based methods for block sizes below 80, and more carefully tuned variants well below 65. The authors observed that, in fact, the output of this algorithm seems to approximate partial-HKZ reduction. For our implementation we treated the SVP algorithm of G6K as a r-partial-HKZ reduction oracle for arbitrary integer r ≤ 15.

To confirm the hypothesis in Sect. 5.1, we tested (r, k)-HKZ-slide reduction for r ∈ {1, 5, 10, 15} and k ∈ {60, 85} on lattices from the lattice challenge [START_REF] Lindner | TU Darmstadt lattice challenge[END_REF]. To avoid issues with block-sizes not dividing the rank, we selected the rank as the largest integer multiple of k such that the algorithm did not run into numerical issues. For k = 60 and k = 85, this was n = 180 (i.e. p = 3 blocks) and n = 170 (i.e. p = 2 blocks), respectively. The results are shown in Figures (1a) and (1c). All datapoints are averaged (in both axes) over the same 10 lattices (challenge seeds 0 to 9), which were preprocessed using fplll [START_REF]FPLLL, a lattice reduction library[END_REF] with block size 45 (for k = 60) and 60 (for k = 85). 2 Fig.

(1a) demonstrates that for relatively small block sizes, (r, k)-HKZ-slide reduction actually behaves better than expected: not only does a larger r lead to a faster convergence (which is expected), all of the tested r also lead to better output quality. This can at least in part be explained by the relatively small block size and the corresponding approximation error of the Gaussian heuristic. This is somewhat supported by Fig. (1c), where at least the overlaps r = 5 and r = 15 behave as expected: faster convergence but poorer output quality. (Note though that the difference in output quality between overlaps 1 and 5 is minor.) However, the case of r = 10 seems to be a special case that behaves exceptionally well even for large block size. We cannot offer an explanation of this phenomenon beyond baseless speculation at this point and leave an in-depth investigation to future work.

In summary, we believe that the results give sufficient evidence that the time/quality trade-off achieved by HKZ-slide reduction can indeed be very favourable when considering overlaps larger than 1 (i.e. beyond slide reduction). HKZ-slide vs. BKZ. To put the results into context, we also compare HKZ-slide reduction with the BKZ variants implemented in G6K on the same lattices. For HKZ-slide reduction we chose r = 10 for the above reasons. We compared to three "standard" variants of BKZ:

-Naive BKZ, which treats the SVP algorithm as a black box; -The "Pump and Jump" (PnJ) variant, which recycles computation done during previous calls to the SVP algorithm to save cost in later calls; -A progressive variant of the PnJ strategy, which starts with smaller block sizes and successively runs BKZ tours with increasing block sizes. We left all parameters for the PnJ versions at their default. [ADH + 19] reported that some fine-tuning can improve the PnJ variant further, but since our goal is only to demonstrate competetiveness of HKZ-slide reduction rather than a fine-grained comparison, we do not believe such fine-tuning is necessary here. Naive BKZ and the PnJ variant were called with the same block size (on the same bases as HKZ-slide reduction) and the number of tours was chosen such that the running time was roughly in the ballpark of the HKZ-slide reduction experiments. For progressive PnJ, we ran 1 tour of each block size starting from k -10 up to k + 5, where k is the block size chosen for the other algorithms. This choice of block sizes is somewhat arbitrary, but was also made in an attempt to ensure that progressive PnJ has roughly the same running time as the other algorithms.