Quantum Lattice Enumeration and Tweaking Discrete Pruning

Abstract

Enumeration is a fundamental lattice algorithm. We show how to speed up enumeration on a quantum computer, which affects the security estimates of several lattice-based submissions to NIST: if T is the number of operations of enumeration, our quantum enumeration runs in roughly $\sqrt{T}$ operations. This applies to the two most efficient forms of enumeration known in the extreme pruning setting: cylinder pruning but also discrete pruning introduced at Eurocrypt ’17. Our results are based on recent quantum tree algorithms by Montanaro and Ambainis-Kokainis. The discrete pruning case requires a crucial tweak: we modify the preprocessing so that the running time can be rigorously proved to be essentially optimal, which was the main open problem in discrete pruning. We also introduce another tweak to solve the more general problem of finding close lattice vectors.

1 Introduction

The main two hard lattice problems are finding short lattice vectors (SVP) and close lattice vectors (CVP), either exactly or approximately. Both have been widely used in cryptographic design for the past twenty years: Ajtai’s SIS [2] and Regev’s LWE [38] are randomized variants of respectively SVP and CVP.

With the NIST standardization of post-quantum cryptography and the development of fully-homomorphic encryption, there is a need for convincing security estimates for lattice-based cryptosystems. Yet, in the past ten years, there has been regular progress in the design of lattice algorithms, both in theory (e.g. [1, 20, 31]) and practice (e.g. [10, 17, 19, 21, 25, 32, 35]), which makes security estimates tricky. Lattice-based NIST submissions use varying cost models, which gives rise to a wide range of security estimates [5]. The biggest source of divergence is the cost assessment of a subroutine to find nearly shortest lattice vectors in certain dimensions (typically the blocksize of reduction algorithms), which is chosen among two families: sieving [3, 15, 25, 32, 35] and enumeration.

Enumeration is the simplest algorithm to solve SVP/CVP: it outputs $L \cap B$, given a lattice L and an n-dimensional ball $B \subseteq \mathbb {R}^n$. Dating back to the early 1980s [24, 37], it has been significantly improved in practice in the past twenty years, thanks to pruning methods introduced by Schnorr et al. [40,41,42], and later revisited and generalized as cylinder pruning [21] and discrete pruning [10]: these methods offer a trade-off by enumerating over a subset $S \subseteq B$, at the expense of missing solutions. One may only be interested in finding one point in $L \cap S$ (provided it exists), or the ‘best’ point in $L \cap S$, i.e. a point minimizing the distance to a target. Enumeration and cylinder pruning compute $L \cap S$ by a depth-first search of a tree with super-exponentially many nodes. Discrete pruning is different, but the computation of S uses special enumerations.

The choice between sieving and enumeration for security estimates is not straightforward. On the one hand, sieving methods run in time $2^{O(n)}$ much lower than enumeration’s $2^{O(n \log n)}$, but require exponential space. On the other hand, until very recently [6], the largest lattice numerical challenges had all been solved by pruned enumeration, either directly or as a subroutine: cylinder pruning [21] for NTRU challenges [43] (solved by Ducas-Nguyen) and Darmstadt’s lattice challenges [28] (solved by Aono-Nguyen), and discrete pruning [10, 19] for Darmstadt’s SVP challenges [39] (solved by Kashiwabara-Teruya). Among all lattice-based submissions [5, 36] to NIST, the majority chose sieving over enumeration based on the analysis of NewHope [8, Sect. 6], which states that sieving is more efficient than enumeration in dimension $\ge 250$ for both classical and quantum computers. But this analysis is debatable: [8] estimates the cost of sieving by a lower bound (ignoring sub-exponential terms) and that of enumeration by an upper bound (either [17, Table 4] or [16, Table 5.2]), thereby ignoring the lower bound of [17] (see [11] for improved bounds).

The picture looks even more blurry when considering the impact of quantum computers. The quantum speed-up is rather limited for sieving: the best quantum sieve algorithm runs in heuristic time $2^{0.265n+o(n)}$, only slighty less than the best classical (heuristic) time $2^{0.292n+o(n)}$ [15, 25]. And the quantum speed-up for enumeration is unclear, as confirmed by recent discussions on the NIST mailing-list [4]. In 2015, Laarhoven et al. [26, Sect. 9.1] noticed that quantum search algorithms do not apply to enumeration: indeed, Grover’s algorithm assumes that the possible solutions in the search space can be indexed and that one can find the i-th possible solution efficiently, whereas lattice enumeration explores a search tree of an unknown structure which can only be explored locally. Three recent papers [7, 8, 18] mention in a short paragraph that Montanaro’s quantum backtracking algorithm [33] can speed up enumeration, by decreasing the number T of operations to $\sqrt{T}$. However, no formal statement nor details are given in [7, 8, 18]. Furthermore, none of the lattice-based submissions to NIST cite Montanaro’s algorithm [33]: the only submission that mentions enumeration in a quantum setting is NTRU-HSS-KEM [23], where it is speculated that enumeration might have a $\sqrt{T}$ quantum variant.

Our Results. We show that lattice enumeration and its cylinder and discrete pruning variants can all be quadratically sped up on a quantum computer, unlike sieving. This is done by a careful interpretation and analysis of enumeration as tree algorithms. Interestingly, we show that this speedup also applies to extreme pruning [21] where one repeats enumeration over many reduced bases: a naive approach would only decrease the classical cost mt (where m is the number of bases and t is the number of operations of a single enumeration) to $m \sqrt{t}$ quantum operations, but we bring it down to $\sqrt{mt}$.

First, we clarify the application of Montanaro’s algorithm [33] to enumeration with cylinder pruning: the analysis of [33] assumes that the degree of the tree is bounded by a constant, which is tailored for constraint satisfaction problems, but is not the setting of lattice enumeration. To tackle enumeration, we add basic tools such as binary tree conversion and dichotomy: we obtain that if a lattice enumeration (with or without cylinder pruning) searches over a tree with T nodes, the best solution can be found by a quantum algorithm using roughly $\sqrt{T}$ poly-time operations, where there is a polynomial overhead, which can be decreased if one is only interested in finding one solution. This formalizes earlier brief remarks of [7, 8, 18], and applies to both SVP and CVP.

Our main result is that the quantum quadratic speed-up also applies to the recent discrete pruning enumeration introduced by Aono and Nguyen [10] as a generalization of Schnorr’s sampling algorithm [40]. To do so, we tweak discrete pruning and use an additional quantum algorithm, namely that of Ambainis and Kokainis [9] from STOC ’17 to estimate the size of trees. Roughly speaking, given a parameter T, discrete pruning selects T branches (optimizing a certain metric) in a larger tree, and derives T candidate short lattice vectors from them. Our quantum variant directly finds the best candidate in roughly $\sqrt{T}$ operations.

As mentioned previously, we show that the quadratic speed-up of both enumerations also applies to the extreme pruning setting (required to exploit the full power of pruning): if one runs cylinder pruning over m trees, a quantum enumeration can run in $\sqrt{T}$ poly-time operations where T is the sum of the m numbers of nodes, rather than $\sqrt{mT}$ naively; and there is a similar phenomenon for discrete pruning.

As a side result, we present two tweaks to discrete pruning [10], to make it more powerful and more efficient. The first tweak enables to solve CVP in such a way that most of the technical tools introduced in [10] can be reused. This works for the approximation form of CVP, but also its exact version formalized by the Bounded Distance Decoding problem (BDD), which appears in many cryptographic applications such as LWE. In BDD, the input is a lattice basis and a lattice point shifted by some small noise whose distribution is crucial. We show how to handle the most important noise distributions, such as LWE’s Gaussian distribution and finite distributions used in GGH [22] and lattice attacks on DSA [34]. Enumeration, which was historically only described for SVP, can trivially be adapted to CVP, and so does [21]’s cylinder pruning [29]. However, discrete pruning [10] appears to be less simple.

The second tweak deals with the selection of optimal discrete pruning parameters, and is crucial for our quantum variant. Intuitively, given an integer $T>0$, the problem is to find the T “best” integral vectors ${\varvec{t}} \in \mathbb {N}^n$ which minimize some objective function $f({\varvec{t}})$. Aono and Nguyen [10] introduced a fast practical algorithm to do so for a very special useful choice of f, but the algorithm was heuristic: no good bound on the running time was known. We show that their algorithm can actually behave badly in the worst case, i.e. it may take exponential time. But we also show that by a careful modification, the algorithm becomes provably efficient and even optimal for that f, and heuristically for more general choices of f: the running time becomes essentially T operations.

Our theoretical analysis has been validated by experiments, which show that in practical BDD situations, discrete pruning is as efficient as cylinder pruning. Since discrete pruning has interesting features (such as an easier parallelization and an easier generation of parameters), it might become the method of choice for large-scale blockwise lattice reduction.

Impact. Figure 1 illustrates the impact of our quantum enumeration on security estimates: the red and yellow curves show $\sqrt{\#bases*N}$ where N is an upper bound cost, i.e., number of nodes of enumeration with extreme pruning with probability $1/\#bases$. The upper bounds for HKZ/Rankin bases are computed by the method of [11]. Here, we omitted the polynomial overhead factor because small factors in quantum sieve have also never been investigated. Note that the estimate $2^{(0.187\beta \log \beta - 1.019 \beta +16.1)/2}$ (called Q-Enum in  [5]) of a hypothetical quantum enumeration in NTRU-HSS-KEM [23], which is the square-root of a numerical interpolation of the upper bound of [16, 17], is higher than our HKZ estimate: however, both are less than $2^{128}$ until blocksize roughly 400.

Quantum enumeration with extreme pruning would be faster than quantum sieve up to higher dimensions than previously thought, around 300 if we assume that $10^{10}$ quasi-HKZ-bases can be obtained for a cost similar as enumeration, or beyond 400 if $10^{10}$ Rankin-bases (see [17]) can be used instead. Such ranges would affect the security estimates of between 11 and 17 NIST submissions (see Fig. 2), depending on which basis model is considered: these submissions state that the best attack runs BKZ with a blocksize seemingly lower than our threshold between quantum enumeration and quantum sieving, except in the case of S/L NTRU Prime, for which the blocksize 528 corresponds to less than $2^{200}$ in Fig. 1, whereas the target NIST category is 5.

Fig. 1.

Q-sieve vs Q-enum: (Left) Using HKZ bases (Right) Using Rankin bases

Fig. 2.

Lattice-based NIST submissions affected by quantum enumeration

Furthermore, we note that our quantum speedup might actually be more than quadratic. Indeed, the number T of enumeration nodes is actually a random variable: the average quantum running time is ${\mathbb {E}}(\sqrt{T})$, which is $\le \sqrt{{\mathbb {E}}(T)}$ and potentially much less (e.g. a log-normal distribution). It would be useful to identify the distribution of T: it cannot be log-normal for LLL bases (unlike what seems to be suggested in [44]), because it would violate the provable running time $2^{O(n^2)}$ of enumeration with LLL bases.

On the other hand, we stress that this is just a first assessment of quantum enumeration. If one is interested in more precise estimates, such as the number of quantum gates, one would need to assess the quantum cost of the algorithm of Montanaro [33] and that of Ambainis and Kokainis [9].

Related Work. Babai’s nearest plane algorithm [14] can be viewed as the first form of BDD discrete pruning, using only a single cell. Lindner-Peikert’s algorithm [27] generalizes it using exponentially many cells, and is the BDD analogue of Schnorr’s random sampling [40] (see [29]). But for both [27, 40], the selection of cells is far from being optimal. In 2003, Ludwig [30] applied Grover search to speed up [40] quantumly.

Roadmap. Section 2 provides background. Section 3 gives a general description of enumeration to find close lattice vectors. In Sect. 4, we speed up cylinder pruning enumeration on a quantum computer, using [33]. In Sect. 5, we adapt lattice enumeration with discrete pruning to CVP. In Sect. 6, we show how to efficiently select the best parameters for discrete pruning, by modifying the orthogonal enumeration of [10]. In Sect. 7, we speed up discrete pruning enumeration on a quantum computer, using [9, 33]. Supplementary material is given in the full version [12], including proofs and experimental results.

2 Preliminaries

We follow the notations of [10].

General. $\mathbb {N}$ is the set of integers $\ge 0$. For any finite set U, its number of elements is $\#U$. For any measurable subset $S \subseteq \mathbb {R}^n$, its volume is $\mathrm {vol}(S)$. We use row representations of matrices. The Euclidean norm of a vector ${\varvec{v}}\in \mathbb {R}^{n}$ is $\left\| {\varvec{v}}\right\|$. We denote by $\mathrm {Ball}_{n}({\varvec{c}},R)$ the n-dim Euclidean ball of radius R and center ${\varvec{c}}$, whose volume is $\mathrm {vol}(\mathrm {Ball}_{n}(R)) = R^n \frac{\pi ^{n/2}}{\Gamma (n/2+1)}$. If ${\varvec{c}}$ is omitted, we mean ${\varvec{c}}=0$.

Lattices. A lattice L is a discrete subgroup of $\mathbb {R}^{m}$, or equivalently the set $L({\varvec{b}}_{1},\dots ,{\varvec{b}}_{n})=\left\{ \sum _{i=1}^{n}x_{i}{\varvec{b}}_{i} ~:~ x_{i}\in \mathbb {Z}\right\}$ of all integer combinations of n linearly independent vectors ${\varvec{b}}_{1},\dots ,{\varvec{b}}_{n} \in \mathbb {R}^{m}$. Such ${\varvec{b}}_i$’s form a basis of L. All the bases have the same number n of elements, called the dimension or rank of L, and the same n-dimensional volume of the parallelepiped $\left\{ \sum _{i=1}^{n}a_{i}{\varvec{b}}_{i} ~:~ a_{i}\in [0,1) \right\}$ they generate. We call this volume the co-volume of L, denoted by $\mathrm {covol}(L)$. The lattice L is said to be full-rank if $n=m$. The shortest vector problem (SVP) 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=({\varvec{b}}_{1},\dots ,{\varvec{b}}_{n})$ of a lattice L and $i\in \{1,\ldots ,n\}$, we denote by $\pi _{i}$ the orthogonal projection on $\mathrm {span}({\varvec{b}}_{1},\dots ,{\varvec{b}}_{i-1})^{\perp }$. The Gram-Schmidt orthogonalization of the basis B is defined as the sequence of orthogonal vectors $B^{\star } = ({\varvec{b}}^{\star }_{1},\dots ,{\varvec{b}}^{\star }_{n})$, where ${\varvec{b}}^{\star }_i := \pi _i({\varvec{b}}_i)$. We can write each ${\varvec{b}}_i$ as ${\varvec{b}}^{\star }_{i}+\sum _{j=1}^{i-1}\mu _{i,j}{\varvec{b}}^{\star }_{j}$ for some unique $\mu _{i,1},\ldots ,\mu _{i,i-1} \in \mathbb {R}$. Thus, we may represent the $\mu _{i,j}$’s by a lower-triangular matrix $\mu$ with unit diagonal. $\pi _{i}(L)$ is a lattice of rank $n+1-i$ generated by $\pi _{i}({\varvec{b}}_{i}),\dots ,\pi _{i}({\varvec{b}}_{n})$, with $\mathrm {covol}(\pi _{i}(L))=\prod _{j=i}^{n}\big \Vert {\varvec{b}}^{\star }_{j} \big \Vert$.

Gaussian Heuristic. The classical Gaussian Heuristic provides an estimate on the number of lattice points inside a “nice enough” set:

Heuristic 1

Given a full-rank lattice $L \subseteq \mathbb {R}^n$ and a measurable set $S \subseteq \mathbb {R}^n$, the number of points in $S\cap L$ is approximately $\mathrm {vol}(S)/\mathrm {covol}(L)$.

Both rigorous results and counter-examples are known (see [10]). One should therefore experimentally verify its use, especially for pruned enumeration which relies on strong versions of the heuristic, where the set S is not fixed, depending on a basis of L.

Statistics. We denote by ${\mathbb {E}}()$ the expectation and ${\mathbb {V}}()$ the variance of a random variable. For discrete pruning, it is convenient to extend ${\mathbb {E}}()$ to any measurable set C of $\mathbb {R}^n$ by using the squared norm, that is ${\mathbb {E}}\{C\} := {\mathbb {E}}_{{\varvec{x}} \in C}(\Vert {\varvec{x}}\Vert ^2)$.

Gaussian Distribution.

The CDF of the Gaussian distribution of expectation 0 and variance $\sigma ^2$ is $\frac{1}{2}(1+\mathrm{erf}( \frac{x}{\sigma \sqrt{2}}))$ where the error function is $\mathrm{erf}(z) := \frac{2}{\sqrt{\pi }} \int _0^z e^{-t^2} dt.$ The multivariate Gaussian distribution over $\mathbb {R}^m$ of parameter $\sigma$ selects each coordinate with Gaussian distribution.

Quantum Tree Algorithms. Like in [9], a tree $\mathcal {T}$ is locally accessed given:

• 1. the root r of $\mathcal {T}$.

• 2. a black box which, given a node v, returns the number of children d(v) for this node. If $d(v)=0$, v is called a leaf.

• 3. a black box which, given a node v and $i\in [d(v)]$, returns the i-th child of v.

We denote by $V(\mathcal {T})$ its set of nodes, $L(\mathcal {T})$ its set of leaves, $d(\mathcal {T})=\max _{v \in V(\mathcal {T})} d(v)$ its degree and $n(\mathcal {T})$ an upper-bound of its depth. When there is no ambiguity, we use d and n directly without the argument $\mathcal {T}$. We also denote by $\#\mathcal {T}$ the number of nodes of the tree $\mathcal {T}$.

Backtracking is a classical algorithm for solving problems such as constraint satisfaction problems, by performing a tree search in depth-first order. Each node represents a partial candidate and its children say how to extend a candidate. There is a black-box function $\mathcal {P}: V(\mathcal {T})\rightarrow \{true, false, indeterminate\}$ such that $\mathcal {P}(v)\in \{true,false\}$ iff v is a leaf: a node $v\in V(\mathcal {T})$ is called marked if $\mathcal {P}(v)=true$. Backtracking determines whether $\mathcal {T}$ contains a marked node, or outputs one or all marked nodes. Classically, this can be done in $\#\mathcal {V}(\mathcal {T})$ queries. Montanaro [33] studied the quantum case:

Theorem 2

([33]). There is a quantum algorithm $\mathbf {ExistSolution}(\mathcal {T},T,\mathcal {P},n,\varepsilon )$ which given $\varepsilon >0$, a tree $\mathcal {T}$ such that $d(\mathcal {T})=O(1)$, a black box function $\mathcal {P}$, and upper bounds T and n on the size and the depth of $\mathcal {T}$, determines if $\mathcal {T}$ contains a marked node by making $O(\sqrt{Tn}\log (1/\varepsilon ))$ queries to $\mathcal {T}$ and to the black box function $\mathcal {P}$, with a probability of correct answer $\ge 1-\varepsilon$. It uses O(1) auxiliary operations per query and uses $\mathtt {poly}(n)$ qubits.

Theorem 3

([33]). There is a quantum algorithm $\mathbf {FindSolution}(\mathcal {T},\mathcal {P},n,\varepsilon )$ which, given $\varepsilon >0$, a tree $\mathcal {T}$ such that $d(\mathcal {T})=O(1)$, a black box function $\mathcal {P}$, and an upper bound n on the depth of $\mathcal {T}$, outputs x such that $\mathcal {P}(x)$ is true, or “not found” if no such x exists by making $O(\sqrt{\#\mathcal {V}(\mathcal {T})} n^{3/2}\log (n)\log (1/\varepsilon ))$ queries to $\mathcal {T}$ and to the black box function $\mathcal {P}$, with correctness probability at least $1-\varepsilon$. It uses O(1) auxiliary operations per query and uses $\mathtt {poly}(n)$ qubits.

Notice that Theorem 3 does not require an upper-bound on $\#\mathcal {V}(\mathcal {T})$ as input.

Ambainis and Kokainis [9] gave a quantum algorithm to estimate the size of trees, with input a tree $\mathcal {T}$ and a candidate upper bound $T_0$ on $\#\mathcal {V}(\mathcal {T})$. The algorithm must output an estimate for $\#\mathcal {V}(\mathcal {T})$, i.e. either a number of $\hat{T}\in [T_0]$ or a claim “$\mathcal {T}$ contains more than $T_0$ vertices”. The estimate is $\delta$-correct if:

• 1. the estimate is $\hat{T}\in [T_0]$ which satisfies $|T-\hat{T}|\le \delta T$ where T is the actual number of vertices;

• 2. the estimate is “$\mathcal {T}$ contains more than $T_0$ vertices” and the actual number of vertices T satisfies $(1+\delta )T>T_0$.

An algorithm solves the tree size estimation problem up to precision $1\pm \delta$ with correctness probability at least $1-\varepsilon$ if for any $\mathcal {T}$ and any $T_0$, the probability that it outputs a $\delta$-correct estimate is at least $1-\varepsilon$.

Theorem 4

([9]). There is a quantum algorithm $\mathbf {TreeSizeEstimation}(\mathcal {T}, T_0, \delta , \varepsilon )$ which, given $\varepsilon >0$, a tree $\mathcal {T}$, and upper bounds d and n on the degree and the depth of $\mathcal {T}$, solves tree size estimation up to precision $1\pm \delta$, with correctness probability at least $1-\varepsilon$. It makes $O\left( \frac{\sqrt{nT_0}}{\delta ^{1.5}}d\log ^2(\frac{1}{\varepsilon })\right)$ queries to $\mathcal {T}$ and $O(\log (T_0))$ non-query transformations per query. The algorithm uses $\mathtt {poly}(n,\log (d),\log (T_0),\log (\delta ),\log (\log (1/\varepsilon )))$ qubits.

3 Enumeration with Pruning

We give an overview of lattice enumeration and pruning, for the case of finding close lattice vectors, rather than finding short lattice vectors: this revisits the analysis model of both [21] and [10].

3.1 Finding Close Vectors by Enumeration

Let L be a full-rank lattice in $\mathbb {R}^n$. Given a target ${\varvec{u}} \in \mathbb {Q}^n$, a basis $B=({\varvec{b}}_1,\dots ,{\varvec{b}}_n)$ of L and a radius $R>0$, enumeration [24, 37] outputs $L \cap S$ where $S=\mathrm {Ball}_{n}({\varvec{u}},R)$: by comparing all the distances to ${\varvec{u}}$, one extracts a lattice vector closest to ${\varvec{u}}$. It performs a recursive search using projections, to reduce the dimension of the lattice: if $\Vert {\varvec{v}}\Vert \le R$, then $\Vert \pi _k({\varvec{v}})\Vert \le R$ for all $1 \le k \le n$. One can easily enumerate $\pi _n(L) \cap S$. And if one enumerates $\pi _{k+1}(L) \cap S$ for some $k \ge 1$, one derives $\pi _{k}(L) \cap S$ by enumerating the intersection of a one-dimensional lattice with a suitable ball, for each point in $\pi _{k+1}(L) \cap S$. Concretely, it can be viewed as a depth-first search of the enumeration tree $\mathcal {T}$: the nodes at depth $n+1-k$ are the points of $\pi _{k}(L) \cap S$. The running-time of enumeration depends on R and B, but is typically super-exponential in n, even if $L\cap S$ is small.

3.2 Finding Close Vectors by Enumeration with Pruning

We adapt the general form of enumeration with pruning introduced by [10]: pruned enumeration uses a pruning set $P \subseteq \mathbb {R}^n$, and outputs $L \cap ({\varvec{u}}+P)$. The advantage is that for suitable choices of P, enumerating $L \cap ({\varvec{u}}+P)$ is much cheaper than $L \cap S$, and if we further intersect $L \cap ({\varvec{u}}+P)$ with S, we may have found non-trivial points of $L \cap S$. Note that we use ${\varvec{u}}+P$ rather than P, because it is natural to make P independent of ${\varvec{u}}$, and it is what happens when one uses the pruning of [21] to search for close vectors. Following [21], we view the pruning set P as a random variable: it depends on the choice of basis B.

We distinguish two cases, which were considered separately in [10, 21]:  

Approximation setting: :

This was studied in [10], but not in [21]. Here, we are interested in finding any point in $L \cap S \cap ({\varvec{u}}+P)$ by enumerating $L \cap ({\varvec{u}}+P)$ then intersect it with the ball S, so we define the success probability as:

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} = \mathop {\Pr }\limits _{P,{\varvec{u}}} ( L \cap S \cap ({\varvec{u}}+P) \ne \emptyset ), \end{aligned}$$

(1)

which is the probability that it outputs at least one point in $L \cap S$. By (slightly) adapting the reasoning of [10] based on the Gaussian heuristic, we estimate that (1) is heuristically

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} \approx \min (1, \mathrm {vol}( S \cap ({\varvec{u}}+P))/ \mathrm {covol}(L)), \end{aligned}$$

(2)

and that the number of elements of $L \cap S \cap ({\varvec{u}}+P)$ is roughly $\mathrm {vol}(S \cap ({\varvec{u}}+P))/ \mathrm {covol}(L)$. This corresponds to approximating the closest vector problem in a lattice, whose hardness is used in most lattice-based signature schemes.

Unique setting: :

Here, we know that the target ${\varvec{u}}$ is unusually close to the lattice, that is $L \cap S$ is a singleton, and we want to find the closest lattice point to ${\varvec{u}}$: this is the so-called Bounded Distance Decoding problem (BDD), whose hardness is used in most lattice-based encryption schemes. Thus, ${\varvec{u}}$ is of the form ${\varvec{u}}={\varvec{v}}+{\varvec{e}}$ where ${\varvec{v}} \in L$ and ${\varvec{e}} \in \mathbb {R}^n$ is very short, and we want to recover ${\varvec{v}}$. This was implicitly studied in [21], but not in [10]: [21] studied the exact SVP case, where one wants to recover a shortest lattice vector (in our setting, if the target ${\varvec{u}}\in L$, the BDD solution would be ${\varvec{u}}$, but one could alternatively ask for the closest distinct lattice point, which can be reduced to finding a shortest lattice vector). We are only interested in finding the closest lattice point ${\varvec{v}} \in L$, so we define the success probability as:

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} = \mathop {\Pr }\limits _{P,{\varvec{u}}} ( {\varvec{v}} \in L \cap ({\varvec{u}}+P) ), \end{aligned}$$

(3)

because we are considering the probability that the solution ${\varvec{v}}$ belongs to the enumerated set $L \cap ({\varvec{u}}+P)$. Usually, the target ${\varvec{u}}$ is derived from the noise ${\varvec{e}}$, which has a known distribution, then we can rewrite (3) as:

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} = \mathop {\Pr }\limits _{P,{\varvec{e}}} ( 0 \in {\varvec{e}} + P ) = \mathop {\Pr }\limits _{P,{\varvec{e}}} ( -{\varvec{e}} \in P ) . \end{aligned}$$

(4)

In the context of SVP, we would instead define $\Pr _{\text {succ}} = \Pr _{P} ( {\varvec{v}} \in P )$ where ${\varvec{v}}$ is a shortest lattice vector. In general, it is always possible to make ${\varvec{u}}$ depend solely on ${\varvec{e}}$: one can take a canonical basis of L, like the HNF, and use it to reduce ${\varvec{u}}$ modulo L, which only depends on ${\varvec{e}}$. Whether $\Pr _{P,{\varvec{e}}} (- {\varvec{e}} \in P )$ can be evaluated depends on the choice of P and the distribution of the noise ${\varvec{e}}$. For instance, if the distribution of $-{\varvec{e}}$ is uniform over some measurable set E, then:

$$\mathop {\Pr }\limits _{P,{\varvec{e}}} ( -{\varvec{e}} \in P ) = \frac{\mathrm {vol}(E \cap P)}{\mathrm {vol}(E)}.$$

We discuss other settings in Sect. 5.6. This can be adapted to a discrete distribution. If the distribution of $-{\varvec{e}}$ is uniform over a finite set $E \cap \mathbb {Z}^n$, then:

$$ \mathop {\Pr }\limits _{P,{\varvec{e}}} (- {\varvec{e}} \in P ) = \frac{\#(E \cap P \cap \mathbb {Z}^n)}{\#(E \cap \mathbb {Z}^n)},$$

where $\#(E \cap P \cap \mathbb {Z}^n)$ is heuristically $\approx \mathrm {vol}(E \cap P)$ by the Gaussian heuristic, and $\#(E \cap \mathbb {Z}^n)$ is usually given by the specific choice of E.

 

When it fails, we can simply repeat the process with many different P’s until we solve the problem, in the approximation-setting or the unique-setting.

We have discussed ways to estimate the success probability of pruned enumeration. To estimate the running time of the full algorithm, we need more information, which depends on the choice of pruning:

• An estimate of the cost of enumerating $L \cap S \cap ({\varvec{u}}+P)$.

• An estimate of the cost of computing the (random) reduced basis B.

3.3 Cylinder Pruning

The first pruning set P ever used is the following generalization [21] of pruned enumeration of [41, 42]. There, P is defined by a function $f: \{1,\dots ,n\} \rightarrow [0,1]$, a radius $R>0$ and a lattice basis $B=({\varvec{b}}_1,\dots ,{\varvec{b}}_n)$ as follows:

$$\begin{aligned} P_f(B,R) = \{ {\varvec{x}} \in \mathbb {R}^n \,\,\text {s.t.}\,\, \Vert \pi _{n+1-i}({\varvec{x}})\Vert \le f(i) R \,\,\text {for all}\,\, 1 \le i \le n \}, \end{aligned}$$

(5)

where the $\pi _i$’s are the Gram-Schmidt projections defined by B. We call cylinder pruning this form of enumeration, because $P_f(B,R)$ is an intersection of cylinders: each inequality $\Vert \pi _{n+1-i}({\varvec{x}})\Vert \le f(i) R$ defines a cylinder. Cylinder pruning was introduced in the SVP setting, but its adaptation to CVP is straightforward [29].

Gama et al. [21] showed how to efficiently compute tight lower and upper bounds for $\mathrm {vol}(P_f(B,R))$, thanks to the Dirichlet distribution and special integrals. Then we can do the same for $\mathrm {vol}(P_f(B,R) \cap S)$ if S is any zero-centered ball. Using the shape of $P_f(B,R)$, [21] also estimated of the cost of enumerating $L \cap S \cap P_f(B,R)$, using the Gaussian heuristic on projected lattices $\pi _i(L)$: these estimates are usually accurate in practice, and they can also be used in the CVP case [29]. To optimize the whole selection of parameters, one finally needs to take into account the cost of computing the (random) reduced basis B: for instance, this is done in [13, 17].

4 Quantum Speed-Up of Cylinder Pruning

4.1 Tools

The analysis of quantum tree algorithms requires the tree to have constant degree $d=O(1)$. Without this assumption, there is an extra $\mathtt {poly}(d)$ term in the complexity bound like in Theorem 4. Instead, it is more efficient to first convert the tree into a binary tree, so that the overhead is limited to $\mathtt {poly}(\log d)$. We will use the following conversion (illustrated by Fig. 3):

Theorem 5

One can transform any tree $\mathcal {T}$ of depth n and degree d into a binary one $\mathcal {T}_2$ so that: $\mathcal {T}_2$ can be explored locally; $\mathcal {T}$ and $\mathcal {T}_2$ have roughly the same number of nodes, namely $\#\mathcal {T}\le \# \mathcal {T}_2 \le 2\#\mathcal {T}$; the leaves of $\mathcal {T}$ and $\mathcal {T}_2$ are identical; the depth of $\mathcal {T}_2$ is $\le n \log d$. Moreover, a black-box function $\mathcal {P}$ over $\mathcal {T}$ can be adapted a black box $\mathcal {P}_2$ for $\mathcal {T}_2$, so that the marked nodes of $\mathcal {T}$ and $\mathcal {T}_2$ are the same. One query to $\mathcal {P}_2$ requires at most one query to $\mathcal {P}$ with additional $O(\log d)$ auxiliary operations.

In the context of enumeration with pruning, instead of enumerating the whole set $L \cap S$, we may only be interested in the ‘best’ vector in $L \cap S$, i.e. minimizing some distance. In terms of tree, this means that given a tree $\mathcal {T}$ with marked leafs defined by a predicate $\mathcal {P}$, we want to find a marked leaf minimizing an integral function g which is defined on the marked leaves of $\mathcal {T}$. We know that $L(\mathcal {T})=L(\mathcal {T}_2)$. g is thus also defined on the marked leaves of $\mathcal {T}_2$. We denote by $g_V$ the predicate which returns true on a node $\mathcal {N}$ if and only if it is a marked leaf and $g(\mathcal {N})\le V$. We first find a parameter R such that there is at least one marked leaf $\mathcal {N}$ such that $g(\mathcal {N})\le R$. Then we decrease R by dichotomy using Theorem 3 with different marking functions. We thus obtain $\mathbf {FindMin1}(\mathcal {T},\mathcal {P},g,R,d,\varepsilon )$ (Algorithm 1), which is a general algorithm to find a leaf minimizing the function g with error probability $\varepsilon$, using the binary tree $\mathcal {T}_2$.¹

Fig. 3.

An example of the transformation in Theorem 5

Theorem 6

Let $\varepsilon >0$. Let $\mathcal {T}$ be a tree with its marked leaves defined by a predicate $\mathcal {P}$. Let d be an upper-bound on the degree of $\mathcal {T}$. Let g be an integral function defined on the marked leaves such that $g(\mathcal {N})\le R$ has at least one solution over all of the marked leaves. Then Algorithm 1 outputs $\mathcal {N}\in \mathcal {T}$ such that g takes its minimum on $\mathcal {N}$ among all of the marked leaves of $\mathcal {T}$, with probability at least $1-\varepsilon$. It requires $O(\sqrt{T}(n\log d )^{3/2}\log (n\log d )\log (\lceil \log _2 R \rceil /\varepsilon )\lceil \log _2 R \rceil )$ queries on $\mathcal {T}$ and on $\mathcal {P}$, where $T=\#\mathcal {T}$. Each query on $\mathcal {T}$ requires $O(\log d)$ auxiliary operations. The algorithm needs $\mathtt {poly}(n\log d,\log R)$ qubits.

Proof

Correctness is trivial. Regarding the query complexity, there are in total $Round=\lceil \log _2 R\rceil$ calls to $\mathbf {FindSolution}$. According to Theorem 3, each call requires $O(\sqrt{T}(n\log d )^{3/2}\log (n\log d )\log (Round/\varepsilon ))$ queries on the local structure of $\mathcal {T}_2$ and on g. Thus according to Theorem 5, in total, we need $O(\sqrt{T}(n\log d)^{3/2}\log (n\log d)\log (\lceil \log _2 R \rceil /\varepsilon )\lceil \log _2 R \rceil )$ queries on the local structure of $\mathcal {T}$ and on g. Each query on $\mathcal {T}$ requires $O(\log d)$ auxiliary operations. For each call, we need $\mathtt {poly}(n\log d)$ qubits. In total, we need $\mathtt {poly}(n\log d, \log R)$ qubits.    $\square$

If we know an upper-bound of T of the number of nodes in the tree $\mathcal {T}$, we can speed up the algorithm by replacing $\mathbf {FindSolution}$ by $\mathbf {ExistSolution}$ in lines 4, 5: the new algorithm $\mathbf {FindMin2}(\mathcal {T},\mathcal {P},g,R,d,T,\varepsilon )$ is given and analyzed in the full version [12].

4.2 Application to Cylinder Pruning

Lemma 1

Let $({\varvec{b}}_1,\cdots ,{\varvec{b}}_n)$ be an LLL-reduced basis. Let $\mathcal {T}$ be the backtracking tree corresponding to the cylinder pruning algorithm for SVP with radius $R\le \Vert {\varvec{b}}_1\Vert$ and bounding function f. Then the degree of the tree satisfies: $d(\mathcal {T}) \le 2^n$.

Proof

In $\mathcal {T}$, the number of children of a node $\mathcal {N}$ of depth k can be upper-bounded by $d_k=2f(k)\frac{\Vert {\varvec{b}}_1\Vert }{\Vert {\varvec{b}}^{\star }_{n-k+1}\Vert }+1\le 2^{(n-k)/2+1}+1$. The result follows from the fact that an LLL-reduced basis satisfies: $\frac{\Vert {\varvec{b}}_1\Vert ^2}{\Vert {\varvec{b}}^{\star }_i\Vert ^2 } \le 2^{i-1}$ for all $1\le i\le n$.    $\square$

Theorem 7

There is a quantum algorithm which, given $\varepsilon >0$, an LLL-reduced basis $B=({\varvec{b}}_1,\cdots ,{\varvec{b}}_n)$ of a lattice L in $\mathbb {Z}^n$, a radius $R\le \Vert {\varvec{b}}_1\Vert$ and a bounding function $f:\{1,\cdots ,n\}\rightarrow [0,1]$, outputs with correctness probability $\ge 1-\varepsilon$:

• 1. a non-zero vector ${\varvec{v}}$ in $L \cap P_f(B,R)$, in time $O(\sqrt{T}n^3\mathtt {poly}(\log (n),\log (1/\varepsilon ))))$, if $L \cap P_f(B,R)\not \subseteq \{ 0 \}$.

• 2. all vectors in $L \cap P_f(B,R)$, in time $O(\#(L \cap P_f(B,R))\sqrt{T}n^3\log (n)\mathtt {poly}(\log (\#(L \cap P_f(B,R)),\log (1/\varepsilon )))$.

• 3. a shortest non-zero vector ${\varvec{v}}$ in $L \cap P_f(B,R)$, in time $O(\sqrt{T}n^{3}\beta \mathtt {poly}(\log (n),\log (1/\varepsilon ),\log (\beta )))$, if $L \cap P_f(B,R)\not \subseteq \{ 0 \}$. Here $\beta$ is the bitsize of the vectors of B.

Here T is the total number of nodes in the enumeration tree $\mathcal {T}$ searched by the cylinder pruning algorithm over $P_f(B,R)$.

Proof

Let $\mathcal {T}$ be the enumeration tree searched by the cylinder pruning algorithm in which a node of depth i, where $1\le i \le n$, is encoded as $(*,\cdots ,*,x_{n-i+1},\cdots , \cdots ,x_n)$ and where the root is encoded as $(*,\cdots ,*)$. Let $\mathcal {T}_2$ be the corresponding binary tree. Let $\mathcal {P}$ be a predicate which returns true only on the nodes encoded as $(x_1,\cdots ,x_n)$ in $\mathcal {T}_2$ (i.e. the leaves of $\mathcal {T}_2$, where all the variables are assigned), such that $\Vert \sum _{i=1}^n x_i{\varvec{b}}_i\Vert ^2\le R^2$ and $(x_1,\cdots ,x_n)\ne (0,\cdots ,0)$.

For 1, if $L \cap P_f(B,R)\ne \emptyset$, we apply $\mathbf {FindSolution}(\mathcal {T}_2,\mathcal {P},n\log d,\varepsilon )$. For 2, we find all marked nodes by simply repeating the algorithm $\mathbf {FindSolution}$, modifying the oracle operator to strike out previously seen marked elements, which requires space complexity $O(\#(L \cap P_f(B,R)))$.

For 3, if $L \cap P_f(B,R)\ne \emptyset$, we apply Theorem 6 to $\mathbf {FindMin1}(\mathcal {T},\mathcal {P},\Vert \cdot \Vert ^2,R^2,2^{n}+1,\varepsilon )$. In $\mathcal {T}_2$, the height of the tree can be upper-bounded by $n\log d = O(n^2)$. We also have $Round=O(\beta )$. The time complexity is $O(\sqrt{T}n^{3}\beta \mathtt {poly}(\log (n),\log (1/\varepsilon ),\log (\beta )))$.    $\square$

As corollary, we obtain the following quantum speed-up of Kannan’s algorithm for the shortest vector problem:

Theorem 8

There is a quantum algorithm which, given $\varepsilon >0$, and a basis B of a full-rank lattice L in $\mathbb {Z}^n$, with entries of bitlength$\le \beta$, outputs a shortest non-zero vector of L, with error probability at most $\varepsilon$, in time $(n^{\frac{n}{4e}}+o(n))\cdot \mathtt {poly}(\log (n),\log (1/\varepsilon ),\beta )$ using $\mathtt {poly(n,\beta )}$ qubits.

We can also apply the quantum tree algorithms to extreme pruning. If we run cylinder pruning over m trees, we can combine these trees into a global one and apply the quantum tree algorithms on it.

Theorem 9

(Quantum speed-up for SVP extreme pruning). There is a quantum algorithm which, given $\varepsilon >0$, m LLL-reduced bases $B_1,\cdots B_m$ of a lattice L in $\mathbb {Z}^n$,a radius $R\le \min _i\Vert {\varvec{b}}_{1,i}\Vert$ where ${\varvec{b}}_{1,i}$ is the first vector of $B_i$ and a bounding function $f:\{1,\cdots ,n\}\rightarrow [0,1]$, outputs with correctness probability $\ge 1-\varepsilon$ a shortest non-zero vector ${\varvec{v}}$ in $L \cap (\cup P_f(B_i,R))$, in time $O(\sqrt{T}n^{3}\beta \mathtt {poly}(\log (n),\log (1/\varepsilon ),\log (\beta ),\log (m)))$, if $L \cap (\cup P_f(B_i,R)\not \subseteq \{ 0 \}$. Here $\beta$ is a bound on the bitsize of vectors of $B_i$’s, T is the sum of number of nodes in the enumeration trees $\mathcal {T}_i$ searched by cylinder pruning over $P_f(B_i,R)$ for all $1\le i\le m$.

In the case of CVP with target vector ${\varvec{u}}$, we use the cylinder pruning algorithm with radius $R\le \sqrt{\sum _{i=1}^n \Vert {\varvec{b}}^{\star }_i\Vert ^2}/2$ and bounding function f. The degree of the tree is now upper-bounded by $d=\max \sqrt{\sum _{i=1}^n \Vert {\varvec{b}}^{\star }_i\Vert ^2}/\Vert {\varvec{b}}^{\star }_j\Vert +1$. We have $\log d=O(\beta +n)$ where $\beta$ is the bitsize of the vectors of the basis B. We can obtain a similar theorem as Theorem 7 with different overheads. For exemple for the first case, the time complexity becomes $O(\sqrt{T}n^{3/2}(n+\beta )^{3/2}\mathtt {poly}(\log (n),\log (1/\varepsilon ),\log (\beta ))))$.

For the extreme pruning for CVP the time complexity is $O(\sqrt{T}n^{3/2}(n+\beta )^{3/2}\beta \mathtt {poly}(\log (n),\log (1/\varepsilon ),\log (\beta ),\log (m)))$.

5 BDD Enumeration with Discrete Pruning

We adapt Aono-Nguyen’s discrete pruning [10] to the BDD case.

5.1 Discrete Pruning for the Enumeration of Short Vectors

Discrete pruning is based on lattice partitions defined as follows. Let L be a full-rank lattice in $\mathbb {Q}^n$. An L-partition is a partition $\mathcal {C}$ of $\mathbb {R}^n$ such that:

• The partition is countable: $\mathbb {R}^n = \cup _{t \in T} \mathcal {C}(t)$ where T is a countable set, and $\mathcal {C}(t) \cap \mathcal {C}(t') = \emptyset$ whenever $t \ne t'$.

• Each cell $\mathcal {C}(t)$ contains a single lattice point, which can be found efficiently: given any $t \in T$, one can “open” the cell $\mathcal {C}(t)$, i.e. compute $\mathcal {C}(t) \cap L$ in polynomial time. In other words, the partition defines a function $g:T \rightarrow L$ where $\mathcal {C}(t) \cap L = \{ g(t) \}$, and one can compute g in polynomial time.

Discrete pruning is obtained by selecting the pruning set P as the union of finitely many cells $\mathcal {C}(t)$, namely $P=\cup _{t \in U} \mathcal {C}(t)$ for some finite $U \subseteq T$. Then $L \cap P = \cup _{t \in U} (L \cap \mathcal {C}(t))$ can be enumerated by opening each cell $\mathcal {C}(t)$ for $t \in U$.

[10] presented two useful L-partitions: Babai’s partition where $T=\mathbb {Z}^n$ and each cell $\mathcal {C}(t)$ is a box of volume $\mathrm {covol}(L)$; and the natural partition where $T=\mathbb {N}^n$ and each cell $\mathcal {C}(t)$ is a union of non-overlap** boxes, with total volume $\mathrm {covol}(L)$. The natural partition is preferable, and [10] explained how to select good cells for the natural partition. In theory, one would like to select the cells $\mathcal {C}(t)$ which maximize $\mathrm {vol}(\mathcal {C}(t) \cap S)$: [10] shows how to compute $\mathrm {vol}(\mathcal {C}(t) \cap S)$, but an exhaustive search to derive the best $\mathrm {vol}(\mathcal {C}(t) \cap S)$ exactly would be too expensive. Instead, [10] shows how to approximate efficiently the optimal selection, by selecting the cells $\mathcal {C}(t)$ minimizing ${\mathbb {E}}(\mathcal {C}(t))$: given m, it is possible to compute in practice the m cells which minimize ${\mathbb {E}}(\mathcal {C}(t))$.

5.2 Universal Lattice Partitions

Unfortunately, in the worst case, L-partitions are not sufficient for our framework: if $P=\cup _{t \in U} \mathcal {C}(t)$, then $L \cap (P+{\varvec{u}}) = \cup _{t \in U} (L \cap (\mathcal {C}(t)+{\varvec{u}}))$ but the number of elements in $L \cap (\mathcal {C}(t)+{\varvec{u}})$ is unclear, and it is also unclear how to compute in $L \cap (\mathcal {C}(t)+{\varvec{u}})$ efficiently. To fix this, we could compute instead $L \cap P \cap S = \cup _{t \in U} (L \cap \mathcal {C}(t)) \cap S$, but that creates two issues:

• In the unique setting, it is unclear how we would evaluate success probabilities. Given a tag t and a target ${\varvec{u}} = {\varvec{v}} + {\varvec{e}}$ where ${\varvec{e}}$ is the noise and ${\varvec{v}} \in L$, we would need to estimate the probability that ${\varvec{v}} \in \mathcal {C}(t)$, i.e. ${\varvec{u}}-{\varvec{e}} \in \mathcal {C}(t)$.

• We would need to select the tag set U depending on the target ${\varvec{u}}$, without knowing how to evaluate success probabilities.

BDD asks to find the lattice point ${\varvec{v}}\in L$ closest to some target vector ${\varvec{u}} \in \mathbb {Q}^n$, unusually close to L. To adapt discrete pruning to BDD, the most natural solution would be to subtract ${\varvec{u}}$ to the lattice L as follows.

Definition 1

Let L be a full-rank lattice in $\mathbb {Q}^n$. An L-partition $\mathcal {C}$ is universal if for all ${\varvec{u}} \in \mathbb {Q}^n$, the shifted partition $\mathcal {C}+{\varvec{u}}$ is an L-partition, i.e.:

• The partition is countable: $\mathbb {R}^n = \cup _{t \in T} \mathcal {C}(t)$ where T is a countable set, and $\mathcal {C}(t) \cap \mathcal {C}(t') = \emptyset$ whenever $t \ne t'$.

• For any ${\varvec{u}} \in \mathbb {Q}^n$, each cell $\mathcal {C}(t)$ contains a single point in $L-{\varvec{u}} = \{ {\varvec{v}}-{\varvec{u}}, {\varvec{v}} \in L\}$, which can be found efficiently: given any $t \in T$ and ${\varvec{u}} \in \mathbb {Q}^n$, one can “open” the cell ${\varvec{u}}+\mathcal {C}(t)$, i.e. compute $({\varvec{u}}+\mathcal {C}(t)) \cap L$ in polynomial time.

Unfortunately, an L-partition is not necessarily universal, even in dimension one. Indeed, consider the L-partition $\mathcal {C}$ with $T=\mathbb {Z}$ defined as follows: $\mathcal {C}(0) = [-1/2,1/2]$; For any $k >0$, $\mathcal {C}(k) = (k-1/2,k+1/2]$; For any $k <0$, $\mathcal {C}(k) = [k-1/2,k+1/2)$. It can be checked that $\mathcal {C}$ is not universal: the shifted cell $\mathcal {C}(0)+1/2$ contains two lattice points, namely 0 and 1. Fortunately, we show in the full version that the two L-partitions (related to Gram-Schmidt orthogonalization) introduced in [10] for discrete pruning are actually universal:

Lemma 2

Let B be a basis of a full-rank lattice L in $\mathbb {Z}^n$. Let $T = \mathbb {Z}^n$ and for any ${\varvec{t}} \in T$, $\mathcal {C}_{\mathbb {Z}}({\varvec{t}} ) = {\varvec{t}}B^{\star } + \mathcal {D}$ where $\mathcal {D}= \{\sum _{i=1}^n x_i {\varvec{b}}^{\star }_i \,\,\text {s.t.} \,\, -1/2 \le x_i < 1/2 \}$. Then Babai’s L-partition $(\mathcal {C}_{\mathbb {Z}}(),T)$ is universal.

Lemma 3

Let B be a basis of a full-rank lattice L in $\mathbb {Z}^n$. Let $T = \mathbb {N}^n$ and for any ${\varvec{t}}=(t_1,\dots ,t_n) \in T$, $\mathcal {C}_{\mathbb {N}}({\varvec{t}} ) = \{ \sum _{i=1}^n x_i {\varvec{b}}^{\star }_i \,\,\text {s.t.} \,\, -(t_i+1)/2< x_i \le -t_i/2 \,\,\text {or} \,\, t_i/2 < x_i \le (t_i+1)/2 \}$. Then the natural partition $(\mathcal {C}_{\mathbb {N}}(),T)$ is universal.

5.3 BDD Discrete Pruning from Universal Lattice Partitions

Any universal L-partition $(\mathcal {C},T)$ and any vector ${\varvec{u}} \in \mathbb {Q}^n$ define a partition $\mathbb {R}^n = \cup _{t \in T} ({\varvec{u}}+\mathcal {C}(t))$. Following the SVP case, discrete pruning opens finitely many cells ${\varvec{u}}+\mathcal {C}(t)$, as done by Algorithm 2: discrete pruning is parametrized by a finite set $U \subseteq T$ of tags, specifying which cells ${\varvec{u}}+\mathcal {C}(t)$ to open. It is therefore a pruned CVP enumeration with pruning set $P = \cup _{{\varvec{t}} \in U} \mathcal {C}({\varvec{t}}).$

The algorithm performs exactly k cell openings, where $k=\# U$ is the number of cells, and each cell opening runs in polynomial time. So the running time is $\#U$ poly-time operations: one can decide how much time should be spent.

Since the running time is easy to evaluate like in the SVP case, there are only two issues: how to estimate the success probability and how to select U, in order to maximize the success probability.

5.4 Success Probability

Following Sect. 3.2, we distinguish two cases:  

Approximation setting: :

Based on (2), the success probability can be derived from:

$$\begin{aligned} \mathrm {vol}(S \cap ({\varvec{u}}+P)) = \sum _{{\varvec{t}} \in U} \mathrm {vol}(\mathrm {Ball}_n(R) \cap \mathcal {C}({\varvec{t}})). \end{aligned}$$

(6)

This is exactly the same situation as in the SVP case already tackled by [10]. They showed how to compute $\mathrm {vol}( \mathrm {Ball}_n(R) \cap \mathcal {C}({\varvec{t}}))$ for Babai’s partition and the natural partition by focusing on the intersection of a ball with a box $H=\{ (x_1,\dots ,x_n)\in \mathbb {R}^n \,\,\text {s.t.}\,\, \alpha _i \le x_i \le \beta _i \}$:

 

• In the case of Babai’s partition, each cell $\mathcal {C}_\mathbb {Z}({\varvec{t}})$ is a box.

• In the case of the natural partition, each cell $\mathcal {C}_\mathbb {N}({\varvec{t}})$ is the union of $2^j$ symmetric (non-overlap**) boxes, where j is the number of non-zero coefficients of ${\varvec{t}}$. It follows that $\mathrm {vol}(\mathcal {C}_\mathbb {N}({\varvec{t}}) \cap \mathrm {Ball}_n(\mathbb {R})) = 2^j \mathrm {vol}( H \cap S)$, where H is any of these $2^j$ boxes.

And they also showed to approximate a sum $\sum _{{\varvec{t}} \in U} \mathrm {vol}(\mathrm {Ball}_n(R) \cap \mathcal {C}({\varvec{t}}))$ in practice, without having to compute separately each volume.  

Unique setting: :

Based on (4), if the noise vector is ${\varvec{e}}$, then the success probability is

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} = \mathop {\Pr }\limits _{P,{\varvec{e}}} ( -{\varvec{e}} \in P ) = \sum _{{\varvec{t}} \in U} \mathop {\Pr }\limits _{P,{\varvec{e}}} ( -{\varvec{e}} \in \mathcal {C}({\varvec{t}}) ) \end{aligned}$$

(7)

It therefore suffices to compute the cell probability $\Pr _{P,{\varvec{e}}} ( {\varvec{e}} \in \mathcal {C}({\varvec{t}}))$, instead of an intersection volume. Similarly to the approximation setting, we might be able to approximate the sum $\sum _{{\varvec{t}} \in U} \Pr _{P,{\varvec{e}}} ( {\varvec{e}} \in \mathcal {C}({\varvec{t}}) )$ without having to compute individually each probability. In Sect. 5.6, we focus on the natural partition: we discuss ways to compute the cell probability $\Pr _{P,{\varvec{e}}} ( {\varvec{e}} \in \mathcal {C}({\varvec{t}}))$ depending on the distribution of the noise ${\varvec{e}}$.

 

In both cases, we see that the success probability is of the form:

$$\begin{aligned} \mathop {\Pr }\limits _{\text {succ}} = \sum _{{\varvec{t}} \in U} f({\varvec{t}}), \end{aligned}$$

(8)

for some function $f():T\rightarrow [0,1]$ such that $\sum _{{\varvec{t}} \in T} f({\varvec{t}}) =1$, where (8) is rigorous for the unique setting, and heuristic for the approximation setting due to the Gaussian heuristic. If ever the computation of f() is too slow to compute individually each term of $\sum _{{\varvec{t}} \in U} f({\varvec{t}})$, we can use the statistical inference techniques of [10] to approximate (8) from the computation of a small number of $f({\varvec{t}})$. Note that if we know that the probability is reasonably large, say $>0.01$, we can alternatively use Monte-Carlo sampling to approximate it.

5.5 Selecting Parameters

We would like to select the finite set U of tags to maximize $\Pr _{\text {succ}}$ given by (8). Let us assume that we have a function $g:T \rightarrow \mathbb {R}^+$ such that $\sum _{{\varvec{t}} \in T} g(t)$ converges. If (8) provably holds, then $\sum _{{\varvec{t}} \in T} f(t)=1$, so the sum indeed converges. Since T is infinite, this implies that for any $B>0$, the set $\{ {\varvec{t}} \in T \,\,\text {s.t.}\,\, f({\varvec{t}}) > B \}$ is finite, which proves the following elementary result:

Lemma 4

Let T be an infinite countable set. Let $f:T \rightarrow \mathbb {R}^+$ be a function such that $\sum _{{\varvec{t}} \in T} f(t)$ converges. Then for any integer $m >0$, there is a finite subset $U \subseteq T$ of cardinal m such that $f({\varvec{t}}) \le \min _{{\varvec{u}} \in U} f({\varvec{u}})$ for all ${\varvec{t}} \in T \setminus U$. Such a subset U maximizes $\sum _{{\varvec{u}} \in U} f({\varvec{u}})$ among all m-size subsets of T.

Any such subset U would maximize $\Pr _{\text {succ}}$ among all m-size subsets of T, so we would ideally want to select such a U for any given m. And m quantifies the effort we want to spend on discrete pruning, since the bit-complexity of discrete pruning is exactly m poly-time operations.

Now that we know that optimal subsets U exist, we discuss how to find such subsets U efficiently. In the approximation setting of [10], the actual function f() is related to volumes: we want to select the k cells which maximize $\mathrm {vol}( \mathrm {Ball}_n(R) \cap \mathcal {C}({\varvec{t}}))$ among all the cells. This is too expensive to do exactly, but [10] provides a fast heuristic method for the natural partition, by selecting the cells $\mathcal {C}(t)$ minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$: given as input m, it is possible to compute efficiently in practice the tags of the m cells which minimize

$${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2.$$

In other words, this is the same as replacing the function f() related to volumes by the function

$$h({\varvec{t}}) = e^{-\sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2},$$

and it can be verified that $\sum _{{\varvec{t}} \in \mathbb {N}^n} h({\varvec{t}})$ converges. In practice (see [10]), the m cells maximizing $h({\varvec{t}})$ (i.e. minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$) are almost the same as the cells maximizing $\mathrm {vol}( \mathrm {Ball}_n(R) \cap \mathcal {C}({\varvec{t}}))$.

However, the method of [10] was only heuristic. In Sect. 6, we modify that method to make it fully provable: for any integer $m>0$, we can provably find the best m cells in essentially m polynomial-time operations and polynomial space (the m solutions are output as a stream).

5.6 Noise Distributions in the Unique Setting

We discuss how to evaluate the success probability of BDD discrete pruning in the unique setting for the natural partition. This can easily be adapted to Babai’s partition, because it also relies on boxes. Following (7), it suffices to evaluate:

$$\begin{aligned} p({\varvec{t}})=\mathop {\Pr }\limits _{P,{\varvec{e}}} ( {\varvec{e}} \in -\mathcal {C}({\varvec{t}})), \end{aligned}$$

(9)

where P is the (random) pruning set, ${\varvec{e}}$ is the BDD noise and $\mathcal {C}({\varvec{t}})$ is the cell of the tag ${\varvec{t}}$. We now analyze the most frequent distributions for ${\varvec{e}}$.

LWE and Gaussian Noise. The most important BDD case is LWE [38]. However, there are many variants of LWE using different distributions of the noise ${\varvec{e}}$. We will use the continuous Gaussian distribution over $\mathbb {R}^n$, like in [38]. Many schemes actually use a discrete distribution, such as some discrete Gaussian distribution over $\mathbb {Z}^n$ (or something easier to implement): because this is harder to analyze, cryptanalysis papers such as [27, 29] prefer to ignore this difference, and perform experiments to check if it matches with the theoretical analysis. The main benefit of the Gaussian distribution over $\mathbb {R}^n$ is that for any basis, each coordinate is a one-dimensional Gaussian.

Lemma 5

Let ${\varvec{t}}=(t_1,\dots ,t_n) \in \mathbb {N}^n$ be a tag of the natural partition $\mathcal {C}_{\mathbb {N}}()$ with basis $B=({\varvec{b}}_1,\dots ,{\varvec{b}}_n)$. If the noise ${\varvec{e}}$ follows the multivariate Gaussian distribution over $\mathbb {R}^n$ with parameter $\sigma$, then:

$$\begin{aligned} p({\varvec{t}}) = \prod _{i=1}^n \left( \mathrm{erf}\left( \frac{1}{\sqrt{2}\sigma }\cdot \frac{t_i+1}{2} \cdot \Vert {\varvec{b}}^{\star }_i\Vert \right) - \mathrm{erf}\left( \frac{1}{\sqrt{2}\sigma }\cdot \frac{t_i}{2} \cdot \Vert {\varvec{b}}^{\star }_i\Vert \right) \right) \end{aligned}$$

(10)

Spherical Noise. If the noise ${\varvec{e}}$ is uniformly distributed over a centered ball, we can reuse the analysis of [10]:

Lemma 6

Let $(\mathcal {C},T)$ be a universal L-partition. Let ${\varvec{t}} \in T$ be a tag. If the noise ${\varvec{e}}$ is uniformly distributed over the n-dimensional centered ball of radius R, then:

$$\begin{aligned} p({\varvec{t}}) = \frac{\mathrm {vol}( \mathcal {C}({\varvec{t}}) \cap \mathrm {Ball}_n(R))}{\mathrm {vol}(\mathrm {Ball}_n(R))} \end{aligned}$$

(11)

For both Babai’s partition $\mathcal {C}_{\mathbb {Z}}$ and the natural partition $\mathcal {C}_{\mathbb {N}}$, $\mathcal {C}({\varvec{t}})$ is the union of disjoint symmetric boxes, so the evaluation of (11) is reduced to the computation of the volume of a ball-box intersection, which was done in [10].

Product of Finite Distributions. We now consider a general distribution $\mathcal {D}$ for the noise ${\varvec{e}}$ where each coordinate $e_i$ is independently sampled from the uniform distribution over some finite set. This includes the box distribution, which is the uniform distribution over a set of the form $\prod _{i=1}^n \{a_i, \dots ,b_i\}$. The continuous Gaussian distribution and the uniform distribution over a ball are both invariant by rotation. But if the noise distribution $\mathcal {D}$ is not invariant by rotation, the tag probability $p({\varvec{t}})$ may take different values for the same $(\Vert {\varvec{b}}^{\star }_{1}\Vert ,\ldots ,\Vert {\varvec{b}}^{\star }_{n}\Vert )$, which is problematic for analysing the success probability. To tackle this issue, we reuse the following heuristic assumption introduced in [21]:

Heuristic 10

([21, Heuristic 3] ) The distribution of the normalized Gram-Schmidt orthogonalization $({\varvec{b}}^{\star }_{1}/||{\varvec{b}}^{\star }_{1}||,\ldots ,{\varvec{b}}^{\star }_{n}/||{\varvec{b}}^{\star }_{n}||)$ of a random reduced basis $({\varvec{b}}_{1},\dots ,{\varvec{b}}_{n})$ looks like that of a uniformly distributed orthogonal matrix.

We obtain:

Lemma 7

Let $\mathcal {C}_{\mathbb {N}}$ be the natural partition. Let ${\varvec{t}} \in \mathbb {N}^n$ be a tag. If the distribution of the noise ${\varvec{e}}$ has finite support, then under Heuristic 10:

$$\begin{aligned} p({\varvec{t}}) = \sum _{r \in E} \mathop {\Pr }\limits _{{\varvec{e}}}(\Vert {\varvec{e}}\Vert =r) \times \mathop {\Pr }\limits _{{\varvec{x}} \leftarrow S_n} ({\varvec{x}} \in \mathcal {C}({\varvec{t}})/r) \end{aligned}$$

(12)

where $E \subseteq \mathbb {R}_{\ge 0}$ denotes the finite set formed by all possible values of $\Vert {\varvec{e}}\Vert$ and $S_n$ denotes the n-dimensional unit sphere.

6 Linear Optimization for Discrete Pruning

We saw in Sect. 5.6 how to compute or approximate the probability $p({\varvec{t}})$ that the cell of the tag ${\varvec{t}}$ contains the BDD solution. From Lemma 4, we know that for any integer $m>0$, there are m tags which maximize $p({\varvec{t}})$ in the sense that any other tag must have a lower $p({\varvec{t}})$. To select optimal parameters for BDD discrete pruning, we want to find these m tags as fast as possible, possibly in m operations and polynomial-space (by outputting the result as a stream).

6.1 Reduction to Linear Optimization

We distinguish two cases:

• Selection based on expectation. Experiments performed in [10] show that in practice, the m tags ${\varvec{t}}$ which maximize $\mathrm {vol}(\mathcal {C}_{\mathbb {N}}({\varvec{t}}) \cap \mathrm {Ball}_n(R))$ are essentially the ones which minimize the expectation ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$ where ${\mathbb {E}}\{C\} := {\mathbb {E}}_{{\varvec{x}} \in C}(\Vert {\varvec{x}}\Vert ^2)$ over the uniform distribution. Cor. 3 in [10] shows that this expectation is:

  $${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2.$$

  So we can assume that for a noise uniformly distributed over a ball (see Lemma 6), the m tags ${\varvec{t}}$ maximizing $p({\varvec{t}})$ are the tags minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$.

• Gaussian noise. If the noise distribution is the continuous multivariate Gaussian distribution, Lemma 5 shows that $p({\varvec{t}})$ is given by (10). This implies that the m tags ${\varvec{t}}$ which maximize $p({\varvec{t}})$ are the ones which minimize $- \log p({\varvec{t}})$

In both cases, we want to find the m tags ${\varvec{t}} \in \mathbb {N}^n$ which minimize an objective function g of the form $g({\varvec{t}}) = \sum _{i=1}^n f(i,t_i),$ where $f(i,t_i)\ge 0$. The fact that the objective function can be decomposed as a sum of individual positive functions in each coordinate allows us to view this problem as a linear optimization. We will see that in the case that g has integral outputs, it is possible to provably find the best m tags which minimize such a function g in essentially m operations. If g is not integral, it is nevertheless possible to enumerate all solutions such that $g({\varvec{t}}) \le R$ where R is an input, in time linear in the number of solutions. A special case is the problem of enumerating smooth numbers below a given number.

In practice, it is more efficient to rely on the expectation, because it is faster to evaluate. Figure 4 shows how similar are the best tags with respect to one indicator compared to another: to compare two sets A and B formed by the best M tags, the graph displays $\#(A \cap B)/M$. For instance, the top curve confirms the experimental result of [10] that the m tags ${\varvec{t}}$ which maximize $\mathrm {vol}(\mathcal {C}_{\mathbb {N}}({\varvec{t}}) \cap \mathrm {Ball}_n(R))$ are almost the same as the ones which minimize the expectation ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$. The top second curve shows that the best tags that maximize the LWE probability are very close to those minimizing the expectation. The bottom two curves compare with the finite noise distribution arising in GGH challenges [22] (see the full version for details). In all cases, at most 10% of the best tags are different, and more importantly, we report that the global success probabilities are always very close, with a relative error typically $\le 1\%$.

Fig. 4.

Similarity between optimal sets of tags, depending on the objective function.

We conclude that in practice, the expectation is a very good indicator to select the best tags for the distributions studied in Sect. 5.6.

6.2 Limits of Orthogonal Enumeration

Aono and Nguyen [10, Sect. 6] presented a heuristic method to solve this linear optimization problem in the special case: $g({\varvec{t}})= {\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2,$ by noticing that ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$ was the squared distance between a target point and a special lattice with a known orthogonal basis. This allowed to find all ${\varvec{t}} \in \mathbb {N}^n$ such that ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} \le R$ for any R, using a variant [10, Alg. 6] of enumeration. And by using a binary search based on an early-abort variant, it was also possible to find an R yielding slightly more than m solutions.

[10, Sect. 6] reported that this algorithm worked very well in practice: if $\ell$ is the number of ${\varvec{t}} \in \mathbb {N}^n$ such that ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} \le R$, the number of nodes L of the enumeration algorithm [10, Alg. 6] seemed to be bounded by $O(\ell n)$, perhaps even $\ell \times n$. This was in contrast with the usual situation where the number of nodes of the enumeration tree is exponentially larger than the number of solutions. However, no rigorous result could be proved in [10], leaving it as an open problem to show the efficiency of [10, Alg. 6].

Surprisingly, we solve this open problem of [10] in the negative. More precisely, we show that there are cases where the number of nodes L of enumeration [10, Alg. 6] is exponentially larger than the number of solutions $\ell$. To see this, consider the orthogonal lattice $\mathbb {Z}^n$ with the canonical basis. Then: ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) .$ But we have:

Lemma 8

Let $R=\frac{n}{12}+\frac{1}{2}$ and $n'=\lfloor n/10 \rfloor$. Then the number $\ell$ of ${\varvec{t}} \in \mathbb {N}^n$ such that $\sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \le R$ is exactly $n+1$. But the number $\ell '$ of $(x_{n-n'+1},\dots ,x_n) \in \mathbb {N}^{n'}$ such that $\sum _{i=n-n'+1}^{n} \left( \frac{x_i^2}{4} + \frac{x_i}{4} + \frac{1}{12} \right) \le R$ is $\ge 2^{n'}$.

Proof

For the choice $R=\frac{n}{12}+\frac{1}{2}$, we have $\sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \le R$ if and only if all the $t_i$’s are equal to zero, except at most one, which must be equal to one.

Furthermore, for any $(x_{n-n'+1},\dots ,x_n) \in \{0,1\}^{n'}$, we have:

$$ \sum _{i=n-n'+1}^{n} \left( \frac{x_i^2}{4} + \frac{x_i}{4} + \frac{1}{12} \right) \le n' \left( \frac{1}{2}+ \frac{1}{12} \right) \le \frac{n}{10} \frac{7}{12} = \frac{7n}{120} < R.$$

   $\square$

It follows in this case that the number of nodes L of the enumeration algorithm [10, Alg. 6] for that R is at least exponential in n, though the number of solutions is linear in n.

6.3 Solving Linear Optimization

We show that a slight modification of orthogonal enumeration can solve the more general problem of linear optimization essentially optimally. This is based on two key ideas. The first idea is that when solving linear optimization, we may assume without loss of generality that each function f(i, ) is sorted by increasing value, with a starting value equal to zero, which changes the tree: $f(i,0)=0$ and $f(i,j) \le f(i,j')$ whenever $j \le j'$. Indeed, it suffices to sort the values of f(i, ) if necessary and subtract the minimal value: however, note that for both the expectation ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2$ and for $- \sum _{i=1}^n \log \left( \mathrm{erf}\left( \frac{1}{\sqrt{2}\sigma }\cdot \frac{t_i+1}{2} \cdot \Vert {\varvec{b}}^{\star }_i\Vert \right) - \mathrm{erf}\left( \frac{1}{\sqrt{2}\sigma }\cdot \frac{t_i}{2} \cdot \Vert {\varvec{b}}^{\star }_i\Vert \right) \right)$, the values of f(i, ) are already sorted. For instance, $\frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12}$ is an increasing function of $t_i$.

The second idea is that we may assume to simplify that f has integral values, which allows us to bound the running time of dichotomy. This is not directly true for the expectation ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2$. However, because we deal with integer lattices, the basis B is integral, the $\Vert {\varvec{b}}^{\star }_i\Vert ^2$’s are rational numbers with denominator $\mathrm {covol}(L({\varvec{b}}_1,\dots ,{\varvec{b}}_{i-1}))^2$, so we can transform the expectation into an integer, by multiplying with a suitable polynomial-size integer.

First, we present a slight modification Algorithm 3 of [10, Alg. 6], whose running time is provably essentially proportional to the number of solutions:

Theorem 11

Assume that $f: \{1,\ldots ,n \} \times \mathbb {N}\rightarrow \mathbb {R}$ satisfies $f(i,0)=0$ and $f(i,j) \ge f(i,j')$ for all i and $j>j'$. Given as input a number $R > 0$, Algorithm 3 outputs all $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R$ using $O(nN+1)$ arithmetic operations and $\le (2n-1)N+1$ calls to the function f(), where the number N is the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R$.

Proof

To analyze the complexity of Algorithm 3, let $n_k$ denote the number of times we enter Lines 3–18, depending on the value of k, which is $\ge 1$ and $\le n$ at each Line 3. Then $n_k$ can be decomposed as $n_k = a_k+b_k$, where $a_k$ (resp. $b_k$) denotes the number of times we enter Lines 5–10 (resp. Lines 12–17). Notice that $a_{n+1}=0$ and $a_1$ is exactly the number N of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R$. And if $1 < i \le n$, then $a_i$ is the number of times that the variable k is decremented from i to $i-1$. Similarly, $b_{n} = 1$, and if $1 \le i \le n$, then $b_i$ is the number of times that the variable k is incremented from i to $i+1$. By Line 1 (resp. 14), the initial (resp. final) value of k is n (resp. $n+1$). Therefore, for any $1 \le i \le n-1$, the number of times k is incremented from i to $i+1$ must be equal to the number of times k is decremented from $i+1$ to i, in other words: $b_i = a_{i+1}.$ Thus, the total number of loop iterations is:

$$ \sum _{i=1}^{n} n_i = \sum _{i=1}^{n} (a_i+b_i) = N + 1 + 2 \sum _{i=2}^{n} a_i.$$

Note that because $f(i,0)=0$, any partial assignment $\sum _{i=i_0}^n f(i,v_i) \le R$ can be extended to a larger partial assignment $\sum _{i=1}^n f(i,v_i) \le R$, which implies that $a_1 \ge a_2 \ge \dots a_{n}$. It follows that the total number of loop iterations is:

$$ \sum _{i=1}^{n+1} n_i \le N+1+ 2(n-1) N = (2n-1)N+1.$$

For each loop iteration (Lines 3–18), the number of arithmetic operations performed is O(1) and the number of calls to f() is exactly one. It follows that the total number of arithmetic operations is $O(nN+1)$ and the number of calls to f() is $\le (2n-1)N+1$.    $\square$

We showed that the number of nodes in the search tree is linear in the number of solutions. Next, we present Algorithm 4, which is a counting version of Algorithm 3:

Theorem 12

Assume that $f: \{1,\ldots ,n \} \times \mathbb {N}\rightarrow \mathbb {R}$ satisfies $f(i,0)=0$ and $f(i,j) \ge f(i,j')$ for all i and $j>j'$. Given as input two numbers $R > 0$ and $M > 0$, Algorithm 4 decides if is $N \ge M$ or $N <M$, where N is the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R$. Furthermore, if $N \ge M$, the number of arithmetic operations is O(N), and otherwise, the number of arithmetic operations is $O(nN+1)$, and the algorithms outputs N.

Proof

Similarly to the proof of Theorem 11, let $n_k$ denote the number of times we enter Lines 3–17, depending on the value of k, which is $\ge 1$ and $\le n$ at each Line 3. Then $n_k$ can be decomposed as $n_k = a_k+b_k$, where $a_k$ (resp. $b_k$) denotes the number of times we enter Lines 5–9 (resp. Lines 11–16).

Let M be the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R$. If $M \le N$, then Algorithm 4 will perform the same operations as Algorithm 3 (except Line. 6), so the cost is $O(nM+1) \le O(nN+1)$ arithmetic operations. Otherwise, $M > N$, which means that the while loop will stop after exactly N iterations, and the total number of operations is therefore O(N).    $\square$

Our main result states that if the function f is integral, given any M, Algorithm 5 finds the best N assignments in time M where $M \le N \le (n+1)M$:

Theorem 13

Assume that $f: \{1,\ldots ,n \} \times \mathbb {N}\rightarrow \mathbb {N}$ satisfies $f(i,0)=0$ and $f(i,j) < f(i,j')$ for all i and $j>j'$. Assume that $f(i,j) \le j^{O(1)} 2^{n^{O(1)}}$. Given as input a number $M > 1$, Algorithm 5 outputs the N assignments $(v_1,\dots ,v_n) \in \mathbb {N}^n$ which minimize $\sum _{i=1}^n f(i,v_i)$ in time $O(n(n+1)M)+n^{O(1)}+ O(\log _2 M)$, where the number N satisfies: $M \le N \le (n+1)M$.

Proof

We have the following invariant at the beginning of each loop iteration: the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R_0$ is $< M$, and the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R_1$ is $\ge M$. Initially, this holds because the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le 0$ is 1 and the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le \sum _{i=1}^n f(i,\lceil M^{1/n} \rceil )$ is $\ge (M^{1/n})^n=M$. Furthermore, the loop preserves the invariant by definition of the loop. Since the length $R_1-R_0$ decreases by a factor two, it follows that the number of loop iterations is $\le \log _2(\sum _{i=1}^n f(i,\lceil M^{1/n} \rceil ))$.

After the loop, we must have $R_0 = R_1-1$. Let $N_1$ (resp. $N_0$) be the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) \le R_1$ (resp. $R_0$) after the loop. By the invariant, we know that $N_0 < M \le N_1$. We claim that $(N_1-N_0) \le nM$, which implies that $N_1 \le (n+1)M$. Notice that $N_1-N_0$ is the number of $(v_1,\dots ,v_n) \in \mathbb {N}^n$ such that $\sum _{i=1}^n f(i,v_i) = R_1$. For any such assignment, one of the $v_i$’s must be $\ge 1$: if we decrement that $v_i$, we get a cost $< R_1$, so it must be $\le R_0$ because $R_0 = R_1-1$, which means that this assignment is counted by $N_0$. Since we have at most n possibilities for i, it follows that $N_1-N_0 \le nM$.    $\square$

Furthermore, Algorithm 5 uses negligible space, except that the output is linear in M: the best tags are actually output as a stream. If we sort the N tags, which requires space, we could output exactly the best M tags.

7 Quantum Speed-Up of Discrete Pruning

We present a quadratic quantum speed-up for discrete pruning, namely:

Theorem 14

There is a quantum algorithm which, given $\varepsilon >0$, a number $M>0$, and an LLL-reduced basis B of a full-rank lattice L in $\mathbb {Z}^n$, outputs the shortest non-zero vector in $L \cap P$ in time $O(n^2\sqrt{M}) \mathtt {poly}(\log (n),\log (M),\log (1/\epsilon ),\beta )$ with error probability $\varepsilon$. Here, $\beta$ denotes the bitsize of the vectors of B, $P = \cup _{{\varvec{t}} \in U} \mathcal {C}_{\mathbb {N}}({\varvec{t}})$ where $\mathcal {C}_{\mathbb {N}}()$ is the natural partition with respect to B, U is formed by the N tags ${\varvec{t}}$ minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$, for some $M \le N \le 32n^2 M$ with probability at least $1-\varepsilon /2$. If the algorithm is further given a target ${\varvec{u}} \in \mathbb {Z}^n$, it also outputs the shortest vector in $(L-{\varvec{u}}) \cap P$.

By comparison, opening all the cells returned by Algorithm 5 of Sect. 6 does the same in O(M) poly-time operations, except that the upper bound on N is slightly lower. The proof of Theorem 14 has two parts: first, we show how to determine the best N cells without computing them, for some N close to M, with high probability; then we find the best candidate inside these N cells. Both rely on a tree interpretation. Algorithm 3 can be seen as a backtracking algorithm on a tree $\mathcal {T}(R)$, where each node can be encoded as $(*,\cdots ,*,v_k,\cdots ,v_n)$. The root is encoded as $(*,\cdots ,*)$. Given a node $(*,\cdots ,*,v_k,\cdots ,v_n)$, if $k=1$, then it is a leaf. If $\sum _{i=k}^n f(i,v_i)>R$, then it is also a leaf. If $\sum _{i=k}^n f(i,v_i)\le R$, then its children are $(*,\cdots ,*,v_{k-1},v_k,\cdots ,v_n)$, where $v_{k-1}$ can take all integer values between 0 and $\rho _{v_k,\cdots ,v_n}$. Here $\rho _{v_k,\cdots ,v_n}$ is the smallest integer such that $f(i-1,\rho _{v_k,\cdots ,v_n})+\sum _{i=k}^n f(i,v_i)>R$. In case of discrete pruning, f is quadratic. We can compute $\rho _{v_k,\cdots ,v_n}$ and build the black-box on $\mathcal {T}(R)$.

7.1 Determining the Best Cells Implicitly

Given a number $M > 0$, Algorithm 5 finds (in time essentially M) the best N vectors ${\varvec{t}} \in \mathbb {N}^n$ (for some N close to M) minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \} = \sum _{i=1}^n \left( \frac{t_i^2}{4} + \frac{t_i}{4} + \frac{1}{12} \right) \Vert {\varvec{b}}^{\star }_i\Vert ^2$ by minimizing instead the function:

$$g(v_1,\cdots ,v_n)=\sum _{i=1}^{n} f(i,v_i)= \sum _{i=1}^{n}v_i(v_i+1) \Vert {\varvec{b}}^{\star }_i\Vert ^2=\sum _{i=1}^{n}\alpha _i v_i(v_i+1).$$

This is done by finding a suitable radius R by dichotomy, based on logarithmically many calls to Algorithm 4 until the number of solutions is close to M, and eventually enumerating the marked leaves of a search tree by Algorithm 3. Both Algorithm 3 and Algorithm 4 can be viewed as algorithms exploring a tree $\mathcal {T}(R)$ depending on a radius $R>0$: Algorithm 4 decides if the number $\#S(\mathcal {T}(R))$ of marked leaves (i.e. the number of outputs returned by Algorithm 3) is $\ge$ or < than an input number; Algorithm 3 returns all the marked leaves.

This tree interpretation gives rise to Algorithm 6, which is our quantum analogue of Algorithm 5 with the following differences: we are only interested in finding a suitable radius R such that $N=\#S(\mathcal {T}(R))$ is close to M up to a factor of $32n^2$, with correctness probability at least $1-\varepsilon /2$, because enumerating all the marked leaves would prevent any quadratic speed up. We replace Algorithm 4 by the quantum tree size estimation algorithm of [9]: this gives a quadratic speed up, but approximation errors slightly worsens the upper bound on N. The input $(\alpha _1,\cdots ,\alpha _n)$ of Algorithm 6 corresponds to $(\Vert {\varvec{b}}^{\star }_1\Vert ^2,\cdots ,\Vert {\varvec{b}}^{\star }_n\Vert ^2)$, where $({\varvec{b}}_1,\cdots ,{\varvec{b}}_n)$ is an integer basis. We know that $(\Vert {\varvec{b}}^{\star }_1\Vert ^2,\cdots ,\Vert {\varvec{b}}^{\star }_n\Vert ^2)\in \mathbb {Q}^n$, but by suitable multiplication preserving polynomial sizes, we may assume that $(\Vert {\varvec{b}}^{\star }_1\Vert ^2,\cdots ,\Vert {\varvec{b}}^{\star }_n\Vert ^2)\in \mathbb {N}^n$. The order between the $\Vert {\varvec{b}}^{\star }_i\Vert ^2$’s doesn’t matter in our analysis. We can assume that $\Vert {\varvec{b}}^{\star }_1\Vert ^2\le \cdots \le \Vert {\varvec{b}}^{\star }_n\Vert ^2$. We show that Algorithm 6 finds a radius R corresponding to the best M cells in approximately $\sqrt{M}$ quantum operations:

Theorem 15

The output R of Algorithm 6 satisfies $M \le \#S(\mathcal {T}(R))\le 32n^2M$ with probability $\ge 1-\varepsilon /2$. Algorithm 6 runs in quantum time $O(n^2\sqrt{M}\mathtt {poly}(\log (n),\log (M),\log (1/\varepsilon ),\beta ))$ where $\beta$ is the bitsize of the basis vectors $(\mathbf {b}_1,\cdots ,\mathbf {b}_n)$. The algorithm needs $O(\mathtt {poly}(n,\log (M),\log (1/\epsilon )))$ qubits.

7.2 Finding the Best Lattice Vector

We now know R such that the number N of $(v_1,\cdots ,v_n) \in \mathbb {N}^n$ which satisfies $\sum _{i=1}^{n}f(i,v_i)\le R$ is in $[M,32n^2M]$ with probability at least $1-\varepsilon /2$. All these solutions are leaves of the tree $\mathcal {T}(R)$ and they form the set U of the best N tags minimizing ${\varvec{t}}$ minimizing ${\mathbb {E}}\{ \mathcal {C}_{\mathbb {N}}({\varvec{t}} ) \}$. Let $P = \cup _{{\varvec{t}} \in U} \mathcal {C}_{\mathbb {N}}({\varvec{t}})$ where $\mathcal {C}_{\mathbb {N}}()$ is the natural partition with respect to the input basis B. We would like to find a shortest non-zero vector in $L \cap P$ for the SVP setting, or the shortest vector in $(L-{\varvec{u}}) \cap P$ in the CVP setting, when we are further given target ${\varvec{u}} \in \mathbb {Z}^n$. To do this, we notice that it suffices to apply $\mathbf {FindMin2}$ (in App), provided that the basis $(\mathbf {b}_1,\cdots ,\mathbf {b}_n)$ is LLL-reduced. More precisely, we call $\mathbf {FindMin2}(\mathcal {T}(R),\mathcal {P},h,\Vert \mathbf {b}_1\Vert ^2,d,32n^2M,\varepsilon /2)$. Here $\mathcal {P}$ is the predicate which returns true on a node iff it is a leaf encoded as $(x_1,\cdots ,x_n)$ such that $g(x_1,\cdots ,x_n)=\sum _{i=1}^n f(i,x_i) \le R$. $h_V(x_1,\cdots ,x_n)$ is the predicate which indicates if the square of the norm of the lattice vector in the cell of tag $(x_1,\cdots ,x_n)$ is $\le V$. The time complexity is $O(n^2\sqrt{M}\mathtt {poly}(\log (n),\log (M),\log (1/\varepsilon ),\beta ))$.

Since the subroutine of determining the best cells and the one of finding a shortest non-zero vector, both have an error probability $\varepsilon /2$, by union bound, the total error probability is $\varepsilon$. We thus have proved Theorem 14.

7.3 The Case of Extreme Pruning

In this section, we explain how to tackle the extreme pruning case, where one wants to run discrete pruning over many reduced bases. Due to space limitations, we only give a proof sketch, but the main ideas are the same.

Given m LLL-reduced bases $(\mathbf {B}_1,\cdots ,\mathbf {B}_m)$ of the same integer lattice L of rank n, we define for each basis $\mathbf {B}_i$ a function $g_i:\mathbb {N}^n\rightarrow \mathbb {Q}$ such that $g_i(x_1,\cdots ,x_n)=\sum _{j=1}^n \Vert {\varvec{b}}^{\star }_{i,j}\Vert ^2x_i(x_i+1)$, where $({\varvec{b}}^{\star }_{i,1},\cdots ,{\varvec{b}}^{\star }_{i,n})$ is the Gram-Schmidt orthogonalization of the basis $\mathbf {B}_i$. Here, we want to first find the $\mathtt {poly}(n)*M$ best cells with respect to all of the functions $g_i$ altogether, and then find the shortest vector in these cells. Both steps have complexity $O(\sqrt{M}\mathtt {poly}(n,\log {M},\log {1/\varepsilon },\beta ))$, where $\varepsilon$ is the total error probability and where $\beta$ is the bitsize of the vectors of the input bases.

Theorem 16

There is a quantum algorithm which, given $\varepsilon >0$, a number $M>0$, and m LLL-reduced bases $(\mathbf {B}_1,\cdots ,\mathbf {B}_m)$ of an n-rank integer lattice L, outputs the shortest non-zero vector in $L\cap P$ in time $O(\sqrt{M}\mathtt {poly}(n,\log {M},\log {1/\varepsilon },\beta ))$ with error probability $\varepsilon$. Here, $\beta$ denotes the maximum bitsize of the vectors of all given bases, $P = \cup _{(i,{\varvec{t}}) \in U} \mathcal {C}_{\mathbb {N}}(i,{\varvec{t}})$ where $\mathcal {C}_{\mathbb {N}}(i,\cdot )$ is the natural partition with respect to $B_i$, U is formed by the N tuples $(i,{\varvec{t}})\in \{1,\cdots ,m\}\times \mathbb {N}^n$ minimizing $g_i({\varvec{t}})$ among all tuples, for some $N=\mathtt {poly}(n)*M$ with probability at least $1-\varepsilon /2$. If the algorithm is further given a target ${\varvec{u}} \in \mathbb {Z}^n$, it also outputs the shortest vector in $(L-{\varvec{u}}) \cap P$.

The main idea of the proof is the following. For each basis $\mathbf {B}_i$, there is a backtracking tree with respect to the function $g_i$ as we explained in the previous section. We put all these trees together and obtain one single tree. We first apply the $\mathbf {TreeSizeEstimation}$ algorithm several times to find a good common radius R for all functions $g_i$ by dichotomy, such that the total number of good cells in all trees is $\mathtt {poly}(n)*M$. After that, we apply $\mathbf {FindMin2}$ to find the shortest vector among all these cells. Remark that in the previous section, we required the function g to have integral values, and this was achieved by multiplying all $\Vert {\varvec{b}}^{\star }_i\Vert ^2$ by a common denominator. Instead, we here want to keep the output rational, which is proved sufficient by the following lemma:

Lemma 9

Given a basis $(\mathbf {b}_1,\cdots ,\mathbf {b}_n)$ of an integer lattice L, $g:\mathbb {N}^n\rightarrow \mathbb {Q}$ such that $g(x_1,\cdots ,x_n)=\sum _{i=1}^n\Vert {\varvec{b}}^{\star }_i\Vert ^2x_i(x_i+1)$, we denote $\mathcal {T}(R)$ the backtracking tree for finding all solutions of $g(x_1,\cdots ,x_n)\le R$, $\mathcal {T}_2(R)$ the corresponding binary tree. For all $R\in \mathbb {R}^+$, $\#S(\mathcal {T}_2(R+\delta ))\le 2n\#S(\mathcal {T}_2(R))$, where $\delta =\frac{1}{\prod _{i=1}^n \varDelta _i}$ and $\varDelta _i=\mathrm {covol}(\mathbf {b}_1,\cdots ,\mathbf {b}_i)^2=\prod _{j=1}^i \Vert {\varvec{b}}^{\star }_i\Vert ^2$.

The proof of this lemma is the same as the proof of a similar lemma in the full version by noticing that $\prod _{i=1}^n \varDelta _i$ is a common denominator of all $\Vert {\varvec{b}}^{\star }_i\Vert ^2$.

For each basis $\mathbf {B}_i$, we define $\delta _i$ as in Lemma 9. In the dichotomy step, we stop when the difference of the two terms is smaller than $\min _{j\in \{1,\cdots ,m\}}\delta _j$. The other steps are the same as in the previous section.