Application of Discrete Pruned Enumeration in Solving BDD

Abstract

The bounded distance decoding (BDD) is a fundamental problem in lattice-based cryptography which is derived from the closest vector problem (CVP). In this paper, we adapt the lattice enumeration with discrete pruning, a burgeoning method for the shortest lattice vector problem (SVP), to solve BDD in various cryptanalysis scenarios using direct method. We first transfer the basic definition involved in discrete pruning technique from SVP to CVP, prove corresponding properties and give the specific procedures of the algorithm. Additionally, we use the discrete pruning technique to interpret the classical CVP algorithms, including Babai’s nearest plane and Lindner–Peikert nearest planes, which can be regarded as discrete pruned enumeration on some special pruning sets. We propose three probability models in the runtime analysis to accurately estimate the cost of our algorithm in different application scenarios. We study the application of discrete pruned enumeration for BDD mainly on LWE-based cryptosystem and DSA with partially known nonces. The experimental results show that our new algorithm has higher efficiency than the previous algorithms which directly solve BDD, including the nearest plane(s) algorithms and the lattice enumeration with classical pruning strategies, and we are able to recover the DSA secret with less leaked information than the previous works.

1. Introduction

The closest vector problem (CVP) is one of the cornerstones of lattice-based cryptanalysis which has many variants. Its most significant derivative, the bounded distance decoding problem (BDD), is widely applied in the analysis of post-quantum and classical public-key cryptosystems.

In the analysis of lattice-based post-quantum public-key cryptosystems, BDD attack is the most direct way to solve the learning with errors (LWE) problem, which makes up the most important hardness assumption underlying many lattice-based cryptographic primitives. Much work has been devoted to solving the BDD problem underlying LWE [1,2,3,4,5,6,7,8].

For classical public-key cryptosystems, the application of lattice is usually conjuncted with side channel attack and lattice algorithms are applied to solve the hidden number problem (HNP), which is also a variant of BDD. The lattice method is intensively discussed in the key recovery attack of DSA/ECDSA with partially known nonces [9,10,11,12,13,14].

For most of the cryptanalysis scenarios related to BDD, the target in implementation level is to find a particular lattice vector whose distance from a target vector is less than a given bound. To solve these problems, one route is to directly solve BDD using some approximation algorithms, such as the famous Babai nearest plane algorithm [15] and its extended nearest planes algorithm proposed by Lindner and Peikert [1]. This route is further developed by Li and Nguyen [2] by introducing a SVP algorithm, GNR enumeration [16], into CVP. Another indirect route is Kannan’s embedding techniques [17], which embeds the target vector into a lattice basis and recovers the solution to original CVP by solving a shortest vector problem (SVP) on the new constructed lattice. This method shows great performance in practice benefiting from the abundant theoretical work and practical implementation of various SVP algorithms, especially the lattice reduction algorithms [18,19,20,21]. However, this method only works well on unique SVP, which ensures that the shortest lattice vector corresponds to the secret we want to recover. For lattice method combined with side channel attack, this route sometimes failed to recover the secret, since the lattice constructed from the leaked information cannot guarantee such a “gap” between the secret-related vector and other lattice vectors.

In this work, we further explore the capability of the first route by using some state-of-art techniques called discrete pruning to directly solve CVP and BDD problem. The prototype of discrete pruning was first proposed by Schnorr [22] and improved by [23,24] for solving SVP. The formal concept and meticulous theoretical analysis were given by [25]. The authors of [26] recently proposed further improvements and rectification and experimentally proved the efficiency of discrete pruning is higher than GNR enumeration, which indicates the potential advantage in solving problems deriving from CVP.

Contributions. From the theoretical point of view, we define the translated lattice partition and prove its necessary properties inherited from the original definition, which is the core concept of discrete pruning. Benefiting from the detailed proof, we are able to discover the particular relationship between discrete pruning and the classical CVP algorithm, Babai’s nearest plane and its extended version, nearest planes algorithm. We declare that the nearest plane and nearest planes algorithm are special cases of discrete pruning enumeration with some specific pruning sets, which in turn indicates that the discrete pruning method is a generalization of the nearest plane(s) algorithm with a global optimal pruning set. Then, we propose the overall structure and implementation detail of discrete pruned enumeration for solving the generalized BDD problem, and give the cost estimation method with three success probability models considering the different distributions of error vector in most of the possible application scenarios.

From a practical point of view, we apply discrete pruned enumeration to solving the BDD problems underlying the LWE problem and HNP derived from DSA with partially known nonces, respectively. We experimentally proved that for the same scale, the discrete pruning method has a shorter running time than other algorithm directly solving BDD, such as nearest plane(s) algorithm and enumeration with classical pruning. In the DSA case, we also find that our discrete pruning method with the generalized success probability model could even work with less leaked information, which is beyond the ability of other general methods for solving BDD.

2. Preliminaries

2.1. Lattice

A lattice $\mathcal{L}$ is a discrete additive subgroup of ${\mathbb{R}}^m$. $\mathcal{L}$ is a rank n lattice if any point $\mathbf{v}$ in $\mathcal{L}$ can be represented by an integral combination of n linear independent vectors ${\mathbf{b}}_1,\dots ,{\mathbf{b}}_n\in {\mathbb{R}}^m$. We use column matrix $\mathbf{B}=\left[{\mathbf{b}}_1,\dots ,{\mathbf{b}}_n\right]$ to denote a basis of lattice $\mathcal{L}$, and $\mathcal{L}$ can be defined as $\mathcal{L}\left(\mathbf{B}\right)=\left\{{\sum }_{i=1}^n{x}_i{\mathbf{b}}_i:x_i\in \mathbb{Z}\right\}$. In this work, we typically consider the full-rank integral lattice with basis $\mathbf{B}\in {\mathbb{Z}}^{n\times n}$ from the perspective of cryptography. A basis $\mathbf{B}$ of $\mathcal{L}$ can be transformed to another basis ${\mathbf{B}}^{\prime }$ by applying elementary column operations, i.e., there exists a unimodular matrix $\mathbf{U}$ such that ${\mathbf{B}}^{\prime }=\mathbf{B}\mathbf{U}$. A lattice basis corresponds to a fundamental parallelepiped $\mathcal{P}\left(\mathbf{B}\right)=\left\{{\sum }_{i=1}^n{a}_i{\mathbf{b}}_i:0\le a_i<1,i=1,\dots ,n\right\}$. Obviously, the volume of the fundamental parallelepiped is an invariant of the lattice $\mathcal{L}$, which can be computed by $\mathrm{vol}\left(\mathcal{L}\right)=\sqrt{\det \left({\mathbf{B}}^T\mathbf{B}\right)}$. It can also be defined as an origin-symmetric parallelepiped ${\mathcal{P}}_{1/2}\left(\mathbf{B}\right)=\left\{{\sum }_{i=1}^n{a}_i{\mathbf{b}}_i:-\frac{1}{2}\le a_i<\frac{1}{2},i=1,\dots ,n\right\}$.

Let S be a measurable set of ${\mathbb{R}}^n$, Gaussian heuristic assumes that the number of lattice points contained in S is

$$\#\{S\cap \mathcal{L}\}\approx \mathrm{vol}\left(S\right)/\mathrm{vol}\left(\mathcal{L}\right)$$

Under the Gaussian heuristic assumption, the shortest vector length ${\lambda }_1\left(\mathcal{L}\right)$ can be estimated by $\mathrm{GH}\left(\mathcal{L}\right)$, which is the radius of an n-dimensional ball with volume $\mathrm{vol}\left(\mathcal{L}\right)$, especially when n is sufficiently large ($n⪆45$):

$$\mathrm{GH}\left(\mathcal{L}\right)=\frac{\mathrm{vol}{\left(\mathcal{L}\right)}^{1/n}}{B_n{\left(1\right)}^{1/n}}=\frac{1}{\sqrt{\pi }}\Gamma {\left(\frac{n}{2}+1\right)}^{\frac{1}{n}}\mathrm{vol}{\left(\mathcal{L}\right)}^{\frac{1}{n}}\approx \sqrt{\frac{n}{2\pi e}}\mathrm{vol}{\left(\mathcal{L}\right)}^{\frac{1}{n}}$$

(1)

Orthogonalization and projection. For a lattice basis $\mathbf{B}=\left[{\mathbf{b}}_1,\dots {\mathbf{b}}_n\right]\in {\mathbb{Z}}^{m\times n}$, its corresponding Gram–Schmidt orthogonal basis is defined as ${\mathbf{B}}^{*}=\left[{\mathbf{b}}_1^{*},\dots {\mathbf{b}}_n^{*}\right]{\mathbb{Q}}^{m\times n}$ where ${\mathbf{b}}_i^{*}={\mathbf{b}}_i-{\sum }_{j=1}^{i-1}{\mu }_{i,j}{\mathbf{b}}_j^{*}$, and the orthogonal coefficient ${\mu }_{i,j}=\frac{\langle {\mathbf{b}}_i,{\mathbf{b}}_j^{*}\rangle }{\langle {\mathbf{b}}_j^{*},{\mathbf{b}}_j^{*}\rangle }$. A more general definition is i-th orthogonal projection ${\pi }_i:{\mathbb{R}}^m\to span{({\mathbf{b}}_1,\dots ,{\mathbf{b}}_{i-1})}^{\perp }$. For any vector $\mathbf{v}\in {\mathbb{R}}^n$, we have ${\pi }_i\left(\mathbf{v}\right)=\mathbf{v}-{\sum }_{j=1}^{i-1}\frac{\langle \mathbf{v},{\mathbf{b}}_j^{*}\rangle }{\parallel {\mathbf{b}}_j^{*}{\parallel }^2}{\mathbf{b}}_j^{*}$. Furthermore, any $\mathbf{v}\in {\mathbb{R}}^n$ can be represented under orthogonal basis ${\mathbf{B}}^{*}$ as $\mathbf{v}={\sum }_{i=1}^n{u}_i{\mathbf{b}}_i^{*}$ where $u_i=\frac{\langle \mathbf{v},{\mathbf{b}}_i^{*}\rangle }{\parallel {\mathbf{b}}_i^{*}{\parallel }^2}$. We also define the parallelepiped of ${\mathbf{B}}^{*}$ as ${\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)=\left\{{\sum }_{i=1}^n{a}_i{\mathbf{b}}_i^{*}:-\frac{1}{2}<a_i\le \frac{1}{2},i=1,\dots ,n\right\}$, which is essentially a hypercuboid. (It is convention to use the “left closed and right open” interval to define the parallelepiped, but to unify all the works introduced below and maintain the consistency, we slightly modify the definition of ${\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$ by using “left open and right closed” intervals).

It is a common scenario in lattice-based cryptanalysis to consider a lattice vector very close to a given target vector $\mathbf{t}\in {\mathbb{R}}^n$. Finding such a lattice vector usually means exposing the information of secret key of a cryptosystem, which is always a hard computing problem.

Definition 1

(Closest Vector Problem (CVP)). Given a target vector $\mathbf{t}$ and lattice $\mathcal{L}$, finding the vector $\mathbf{v}\in \mathbf{L}$ such that $\parallel \mathbf{v}-\mathbf{t}\parallel \le \parallel {\mathbf{v}}^{\prime }-\mathbf{t}\parallel$ for any other ${\mathbf{v}}^{\prime }\in \mathbf{L}$.

The Closest Vector Problem (CVP) is to find $\mathbf{v}\in \mathcal{L}$ to minimize $\parallel \mathbf{v}-\mathbf{t}\parallel$. Bounded Distance Decoding (BDD) is a more common variant of CVP in cryptography.

Definition 2

(Original definition of BDD). Given a target vector $\mathbf{t}$ which is very close to $\mathcal{L}\left(\mathbf{B}\right)$, the goal of Bounded Distance Decoding (BDD) problem BDD$(\mathbf{B},\mathbf{t})$ is to find the unique vector ${\mathbf{v}}_0\in \mathcal{L}$ closest to $\mathbf{t}$.

To guarantee the uniqueness of such a lattice vector, we generally require $\mathrm{dist}(\mathbf{t},\mathcal{L})\le d$ where $d<{\lambda }_1/2$. The smaller $\mathrm{dist}(\mathbf{t},\mathcal{L})$ is, the easier BDD is. The vector ${\mathbf{v}}_0-\mathbf{t}$ is called BDD error. However, in some cases, the lattice structure cannot ensure the uniqueness of such a ${\mathbf{v}}_0$. In other words, the ${\mathbf{v}}_0$ related to the secret may not be the lattice vector closest to $\mathbf{t}$ or there is more than one lattice vector contained in the searching area of the CVP algorithm. To describe this scenario in cryptanalysis, here, we propose a generalized description of the BDD problem.

Definition 3

(generalized definition of BDD). Given a target vector $\mathbf{t}$, lattice $\mathcal{L}\left(\mathbf{B}\right)$ and an oracle $\mathcal{O}$, which only outputs 1 on some certain ${\mathbf{v}}_0$ and outputs 0 on any other input, the generalized BDD problem BDD$(\mathbf{B},\mathbf{t},\mathcal{O})$ is to find out ${\mathbf{v}}_0\in \mathcal{L}$ which is very close to $\mathbf{t}$.

2.2. Approximate Algorithms for Solving CVP

The most classical and well-known method for approximately solving CVP (and BDD) is Babai’s Nearest Plane algorithm [15]. The detailed procedures are given by Algorithm 1.

Babai’s Nearest Plane algorithm outputs a lattice vector $\mathbf{v}$ “relatively close” to $\mathbf{t}$ with polynomial time and space complexity, which guarantees $\mathbf{v}-\mathbf{t}\in {\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$. However, a typical well-reduced lattice basis has a geometrically decreasing Gram–Schmidt sequence ${\left\{\parallel {\mathbf{b}}_i^{*}\parallel \right\}}_{i=1}^n$, which means the shape of ${\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$ with unbalanced side length $\parallel {\mathbf{b}}_i^{*}\parallel$ is a narrow box, while the components of BDD error vector $\mathbf{e}={\mathbf{v}}_0-\mathbf{t}$ generally have identical uniform or discrete Gaussian distribution. Therefore, NearestPlane would fail to find the right solution of BDD with a high probability, since $\mathbf{t}$ may lie outside ${\mathbf{v}}_0+{\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$.

Algorithm 1NearestPlane($\mathbf{B},\mathbf{t}$)

Require:     Lattice basis $\mathbf{B}$, target vector $\mathbf{t}\in {\mathbb{R}}^n$ Ensure:     Lattice vector $\mathbf{v}$ such that $\mathbf{v}-\mathbf{t}\in {\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$ 1: ${\mathbf{t}}^{\prime }\leftarrow \mathbf{t}$ 2: $\mathbf{v}\leftarrow \mathbf{0}$ 3: for $i=n$ to 1 do 4:     $x_i\leftarrow \lfloor \frac{\langle {\mathbf{t}}^{\prime },{\mathbf{b}}_i^{*}\rangle }{\langle {\mathbf{b}}_i^{*},{\mathbf{b}}_i^{*}\rangle }\rceil$      $//$$\lfloor x\rceil \stackrel{def}{=}\lfloor x+0.5\rfloor$ 5:     ${\mathbf{t}}^{\prime }\leftarrow {\mathbf{t}}^{\prime }-x_i{\mathbf{b}}_i$ 6:     $\mathbf{v}\leftarrow \mathbf{v}+x_i{\mathbf{b}}_i$ 7: end for 8: return  $\mathbf{v}$

Lindner and Peikert [1] proposed an extended version of NearestPlane to enlarge and balance the searching area to increase success probability. Their NearestPlanes algorithm searches for all $\mathbf{v}\in \mathcal{L}$ such that $\mathbf{v}-\mathbf{t}\in {\mathcal{P}}_{1/2}({\mathbf{B}}^{*}·\mathbf{D})$, where $\mathbf{D}$ is a diagonal matrix with ${\mathbf{D}}_{i,i}=d_i$, which is manually designated. To keep the “balance” of side length $d_i·\parallel {\mathbf{b}}_i^{*}\parallel$ of ${\mathcal{P}}_{1/2}({\mathbf{B}}^{*}·\mathbf{D})$, the smaller $\parallel {\mathbf{b}}_i^{*}\parallel$ is, the larger $d_i$ should be.

The running time of NearestPlanes is exactly ${\prod }_{i=1}^k{d}_i$ times of Babai’s NearestPlane algorithm. In essence, NearestPlanes can be implemented by conducting a depth-first exhaustive search for hypercuboids $\left\{{\sum }_{i=1}^n{a}_i{\mathbf{b}}_i^{*}:\right.$$-\frac{1}{2}+x_i\le a_i<\frac{1}{2}+x_i,$$\left.i=1,\dots ,n\right\}$ with all possible combinations of $(x_1,\dots ,x_n)$, where $x_i=x_i^{\left(0\right)}\dots ,x_i^{(d_i-1)}$ are computed by line 4 of Algorithm 2.

Algorithm 2NearestPlanes($\mathbf{B},\mathbf{t},\mathbf{d}$)

Require:     Lattice basis $\mathbf{B}=[{\mathbf{b}}_1,\dots ,{\mathbf{b}}_k]$, $\mathbf{d}=(d_1,\dots ,d_k)\in {\mathbb{N}}^k$, target vector $\mathbf{t}\in {\mathbb{R}}^k$ Ensure:     A vector set $S=\{{\mathbf{v}}_i\in \mathcal{L}:i=1,\dots ,{\prod }_{i=1}^k{d}_i\}$ such that ${\mathbf{v}}_i-\mathbf{t}\in {\mathcal{P}}_{1/2}({\mathbf{B}}^{*}·\mathrm{diag}\left(\mathbf{d}\right))$ 1: if  $k=0$  then 2:       return $\mathbf{0}$ 3: else 4:       Compute the $d_k$ integers $x_k^{\left(0\right)},\dots ,x_k^{(d_k-1)}$ closest to $\frac{\langle \mathbf{t},{\mathbf{b}}_k^{*}\rangle }{\langle {\mathbf{b}}_k^{*},{\mathbf{b}}_k^{*}\rangle }$ 5:       return ${\displaystyle \bigcup _{i=0,\dots ,d_k-1}}\{x_k^{\left(i\right)}{\mathbf{b}}_k +$ NearestPlanes $\left([{\mathbf{b}}_1,\dots ,{\mathbf{b}}_{k-1}],\mathbf{t}-x_k^{\left(i\right)}{\mathbf{b}}_k,(d_1,\dots ,d_{k-1})\right)\}$ 6: end if

In CT-RSA’13, Liu and Nguyen [2] made some improvements on NearestPlanes algorithm and reveal its connection with Schnorr’s random sampling method [22] and lattice enumeration [16,27,28], both of which are originally proposed for solving the shortest lattice vector problem (SVP). Lattice enumeration for SVP tries to find all the vector $\mathbf{v}\in \mathcal{L}$ such that $\parallel {\pi }_{n+1-k}\left(\mathbf{v}\right)\parallel \le R·f\left(k\right)$ for all $k=1,\dots ,n$, where $f\left(k\right)\in (0,1]$ is the pruning function. Liu and Nguyen treat BDD decoding as lattice vector enumeration in an n-dimensional ball with radius R. This new method requires an extra parameter $R\approx \parallel {\mathbf{v}}_0-\mathbf{t}\parallel$, which is a reasonable estimation of BDD error.

For solving BDD, enumeration algorithm is to find $\mathbf{v}\in \mathcal{L}$ such that $\parallel {\pi }_{n+1-k}(\mathbf{v}-\mathbf{t})\parallel \le R·f\left(k\right)$. From the perspective of implementation, their BDD enumeration essentially changes the “center” of searching at each layer of the enumeration tree. Given the target vector represented by orthogonal basis $\mathbf{t}={\sum }_{i=1}^n{s}_i{\mathbf{b}}_i^{*}$, the algorithm at layer k start searching for the component value $x_k$ of $\mathbf{v}={\sum }_{i=1}^n{x}_i{\mathbf{b}}_i$ from $c_k=\lfloor s_k-{\sum }_{i=k+1}^n{\mu }_{ik}{x}_i\rceil$, while this value for classical SVP enumeration is $c_k=\lfloor -{\sum }_{i=k+1}^n{\mu }_{ik}{x}_i\rceil$ (see [28], Section 6, Algorithm ENUM, line 7–8). They also use the extreme pruning method [16] to optimize the pruning function $f\left(k\right)$ to accelerate BDD enumeration with utmost effort.

Another indirect way to solve BDD is to convert it to a unique-SVP problem by Kannan’s embedding method [17] and use SVP algorithms, mainly referring to lattice reduction, to recover the BDD error as the unique shortest vector in the new problem. For a BDD instance BDD$(\mathbf{B},\mathbf{t})$, the construction of new lattice $\mathcal{L}\left({\mathbf{B}}^{\prime }\right)$ is

$${\mathbf{B}}^{\prime }=\left(\begin{array}{cc}\mathbf{B}& \mathbf{t}\\ \mathbf{0}& \tau \end{array}\right)$$

(2)

The basis ${\mathbf{B}}^{\prime }=({\mathbf{b}}_1^{\prime },\dots ,{\mathbf{b}}_{n+1}^{\prime })$ is a $(n+1)\times (n+1)$ column matrix with the “embedding factor” $\tau$. If the lattice reduction algorithm outputs a short vector in the form of $\mathbf{v}={\sum }_{i=1}^n{x}_i{\mathbf{b}}_i^{\prime }-1·{\mathbf{b}}_{n+1}^{\prime }$, then one can recover the solution to BDD$(\mathbf{B},\mathbf{t})$ by extracting ${\sum }_{i=1}^n{x}_i{\mathbf{b}}_i$, where ${\mathbf{b}}_i$ is the i-th column vector of basis $\mathbf{B}$. The structure of $\mathbf{B}$ and the value of $\tau$ should be elaborately dealt with to construct the “gap” between the shortest vector and other lattice vectors to guarantee that lattice reduction algorithm can find it. Benefiting from the strong power of some state-of-art lattice reduction techniques [18,20,21,29,30,31], this method is widely applied in the security analysis of LWE-based cryptosystem [3,4,5,6,7,8,32] since it is relatively easy to construct such a “gap” when the number of LWE samples is sufficient. While solving BDD instance reduced from the hidden number problem (HNP), this method usually comes up with a “barrier” that the lattice vector corresponding to the secret is not significantly shorter than other vectors, since the information acquired from the cryptosystem is limited and cannot build a proper “gap”. Albrecht and Heninger [14] break this barrier by introducing a verification subalgorithm into uSVP to check whether a point is the valid solution.

2.3. Lattice Enumeration

Enumeration is the most practical polynomial-space algorithm for solving SVP [28,33]. For lattice vector written in the form

$$\mathbf{v}=\sum _{j=1}^n{u}_j{\mathbf{b}}_j^{*}=\sum _{j=1}^n\left(x_j+\sum _{i=j+1}^n{\mu }_{ij}{x}_i\right){\mathbf{b}}_j^{*}$$

(3)

This algorithm traverses an enumeration tree of the coordinates $x_n,\dots ,x_1$ by a depth-first search method, and on k-th layer of the tree, it find all $x_{n-k+1}$ such that partial sum $\parallel {\pi }_{n-k+1}\left(\mathbf{v}\right)\parallel ={\sum }_{j=n-k+1}^n|x_j+{\sum }_{i=j+1}^n{\mu }_{ij}{x}_i|\parallel {\mathbf{b}}_j^{*}\parallel \le R$ for some fixed $(x_{n-k+2},\dots ,x_n)$. Pruning technique efficiently accelerates lattice enumeration by cutting off some branches by restricting $\parallel {\pi }_{n+1-k}\left(\mathbf{v}\right)\parallel \le R·f\left(k\right)$. The pruning function $f\left(k\right)\in (0,1]$ naturally satisfies $f\left(k\right)\le f\left(k^{\prime }\right)$ for all $k<k^{\prime }$. Since the shortest vector might be cut off in the middle layer, the classical lattice enumeration with pruning becomes a probabilistic algorithm from a deterministic one.

Extreme pruning (which is also called GNR enumeration) proposed by Gama et al. [16] is the most important method which makes a contribution of exponential acceleration to full enumeration. They provided a detailed analysis on the success probability $p_{succ}$ and speedup ratio for various pruning functions, and the key idea of extreme pruning method is to minimize the enumeration cost:

$${\mathrm{Cos}\mathrm{t}}_{extreme}=T_{reduction}+\frac{\#Nodes·T_{node}}{p_{succ}}$$

$\#Nodes$ denotes the number of nodes on the pruned enumeration tree, which is estimated as $\#Nodes=\frac{1}{2}{\sum }_{k=1}^n\frac{V_k(R·f\left(k\right))}{{\prod }_{i=n+1-k}^n\parallel {\mathbf{b}}_i^{*}\parallel }$ where $V_k\left(R\right)$ denotes the volume of a k-dimensional ball with radius R.

Another burgeoning and promising technique is discrete pruning. It originated from random sampling reduction algorithms [22,23], which heuristically search for lattice vectors $\mathbf{v}={\sum }_{i=1}^n{u}_i{\mathbf{b}}_i^{*}$ with some certain “pattern” in their Gram–Schmidt coefficients $(u_1,\dots ,u_n)$. In EUROCRYPT’17, Aono and Nguyen summarized these random sampling strategies into a common framework, called discrete pruned enumeration [25]. They proposed the concept of “lattice partition” to build a bijection between lattice vector with the “tag” of partition cells, which indicates the “pattern” of Gram–Schmidt coefficients. Then, the algorithm enumerates some tags which are likely to correspond with very short lattice vectors and check if they are valid. The name “discrete pruning” comes from its discrete searching area, which is a union of many discontinuous hypercuboids.

Definition 4

(Lattice partition [25]). Let $\mathcal{L}$ to be a full-rank lattice in ${\mathbb{Z}}^n$. An $\mathcal{L}$-partition $\left(\mathcal{C}\right(),T)$ is a partition of ${\mathbb{R}}^n$ such that:

• ${\mathbb{R}}^n={\cup }_{\mathbf{z}\in T}\mathcal{C}\left(\mathbf{z}\right)$ and $\mathcal{C}\left(\mathbf{z}\right)\cap \mathcal{C}\left({\mathbf{z}}^{\prime }\right)=⌀$. The index set T is a countable set.
• There is exactly one lattice point in each cell $\mathcal{C}\left(\mathbf{t}\right)$, and there exists a polynomial time algorithm to convert a tag $\mathbf{z}$ to the corresponding lattice vector $\mathbf{v}\in \mathcal{C}\left(\mathbf{z}\right)\cap \mathcal{L}$.

A non-trivial partition is generally related to the orthogonal basis ${\mathbf{B}}^{*}$. We now introduce Babai’s partition and natural partition, which are abstracted from Babai’s Nearest Plane algorithm and natural number representation (NNR) of Fukase–Kashiwabara algorithm [23], respectively.

Definition 5

(Babai’s partition [25]). Given a lattice $\mathcal{L}\left(\mathbf{B}\right)$ with $\mathbf{B}\in {\mathbb{Z}}^{n\times n}$, Babai’s partition $({\mathcal{C}}_{\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ defines the cell ${\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)$ as

$${\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)=\left\{\sum _{i=1}^n{x}_i{\mathbf{b}}_i^{*}:z_i-\frac{1}{2}<x_i\le z_i+\frac{1}{2}\right\}$$

(4)

Definition 6

(Natural partition [25]). Given a lattice $\mathcal{L}\left(\mathbf{B}\right)$ with $\mathbf{B}\in {\mathbb{Z}}^{n\times n}$, the natural partition $({\mathcal{C}}_{\mathbb{N}}\left(\right),{\mathbb{N}}^n)$ defines the cell ${\mathcal{C}}_{\mathbb{N}}\left(\mathbf{z}\right)$ as

$${\mathcal{C}}_{\mathbb{N}}\left(\mathbf{z}\right)=\left\{\sum _{i=1}^n{x}_i{\mathbf{b}}_i^{*},-\frac{z_i+1}{2}<x_i\le -\frac{z_i}{2}\mathrm{or}\frac{z_i}{2}<x_i\le \frac{z_i+1}{2}\right\}$$

(5)

In other words, given lattice vector $\mathbf{v}={\sum }_{j=1}^n{u}_j{\mathbf{b}}_j^{*}$, under Babai’s partition, $\mathbf{v}\in {\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)$ if and only if $\mathbf{z}=(z_1,\dots ,z_n)$ satisfies $u_j\in \left(z_i-\frac{1}{2},z_i+\frac{1}{2}\right]$ for $i=1,\dots ,n$. Under natural partition, $\mathbf{v}\in {\mathcal{C}}_{\mathbb{N}}\left(\mathbf{z}\right)$ if and only if $\mathbf{z}$ satisfies $u_j\in \left(-\frac{z_i+1}{2},-\frac{z_i}{2}\right]\cup \left(\frac{z_i}{2},\frac{z_i+1}{2}\right]$ for $i=1,\dots ,n$.

If we consider $\mathbf{v}$ as an n-dimensional random variable distributed in the corresponding ${\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)$ or ${\mathcal{C}}_{\mathbb{N}}\left(\mathbf{z}\right)$, then based on some putative distribution assumptions, one can compute the first moments (mathematical expectation) of ${\parallel \mathbf{v}\parallel }^2={\sum }_{i=1}^n|u_i{|}^2{\parallel {\mathbf{b}}_i^{*}\parallel }^2$ with the information about a cell’s tag $\mathbf{z}$:

$$\mathbb{E}\left[{\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)\right]=\sum _{i=1}^n\left(z_i^2+1/12\right){\parallel {\mathbf{b}}_i^{*}\parallel }^2$$

(6)

$$\mathbb{E}\left[{\mathcal{C}}_{\mathbb{N}}\left(\mathbf{z}\right)\right]=\sum _{i=1}^n\left(z_i^2/4+z_i/4+1/12\right){\parallel {\mathbf{b}}_i^{*}\parallel }^2$$

(7)

The value of $\mathbb{E}\left[\mathcal{C}\left(\mathbf{z}\right)\right]$ is an indicator of the “pruning”: the smaller $\mathbb{E}\left[\mathcal{C}\left(\mathbf{z}\right)\right]$ is, the shorter $\mathbf{v}\in \mathcal{C}\left(\mathbf{z}\right)$ might be. Then, a bunch of tags with minimal $\mathbb{E}\left[\mathcal{C}\left(\mathbf{z}\right)\right]$ will survive the pruning procedure, and go to subsequent processing. The whole route of discrete pruned (DP) enumeration is given in Algorithm 3.

Algorithm 3DPenumeration

Require:     Lattice basis $\mathbf{B}$, number of tags M, target vector length R Ensure:     $\mathbf{v}\in \mathcal{L}\left(\mathbf{B}\right)$ such that $\parallel \mathbf{v}\parallel <R$ 1: Reduce lattice basis $\mathbf{B}$ 2: while true do 3:       $S\leftarrow ⌀$ 4:       Use binary search to find r such that there are M tags $\mathbf{z}$ satisfying $f\left(\mathbf{z}\right)=\mathbb{E}\left[\mathcal{C}\right(\mathbf{z}\left)\right]<r$ 5:       Enumerate all these M tags and save them in set S 6:       for $\mathbf{z}\in S$ do 7:             Decode $\mathbf{z}$ to recover the corresponding $\mathbf{v}$ such that $\mathbf{v}\in \mathcal{C}\left(\mathbf{z}\right)$ 8:             if ${\parallel \mathbf{v}\parallel }^2<R^2$ then 9:                   return $\mathbf{v}$                          $//$ Find a solution 10:             end if 11:       end for 12:       Rerandomize $\mathbf{B}$ 13:       Reprocess $\mathbf{B}$ using lattice reduction algorithms such as BKZ or LLL 14: end while

3. Discrete Pruning for Solving BDD

3.1. Lattice Partition with Translation

In a sense, lattice partition in the context of SVP can be considered as a tessellation centered at the origin $\mathbf{0}$. For example, in Babai’s partition, the cell ${\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)$ with tag $\mathbf{z}=\mathbf{0}$ exactly corresponds to the origin-symmetric parallelepiped ${\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)$, and for any tag $\mathbf{z}$, the closure of ${\mathcal{C}}_{\mathbb{Z}}\left(\mathbf{z}\right)$ and ${\mathcal{C}}_{\mathbb{Z}}(-\mathbf{z})$ are central symmetrical with regard to the origin. In addition, if $\mathbf{t}$ is close to $\mathbf{0}$ ($\mathbf{t}$ has sparse coordinates or have light “weight”), it is more likely to contain a short lattice vector. Natural partition also has analogous properties. (See Figure 1 in [25].)

Since DP enumeration shows its advantages in lattice enumeration for solving SVP, which can be explained as a special instance of CVP with target vector $\mathbf{t}=\mathbf{0}\in {\mathbb{R}}^n$, then it is a natural idea to generalize it to CVP instances with $\mathbf{t}\ne \mathbf{0}$.

For a given basis $\mathbf{B}$, and a target vector $\mathbf{t}$, in the following, we write $\mathbf{v}={\sum }_{i=1}^n{u}_i{\mathbf{b}}_i^{*}$ and $\mathbf{t}={\sum }_{i=1}^n{s}_i{\mathbf{b}}_i^{*}$ to denote their decomposition under Gram–Schmidt basis ${\mathbf{B}}^{*}$. To minimize the distance ${\parallel \mathbf{v}-\mathbf{t}\parallel }^2={\sum }_{i=1}^n{(u_i-s_i)}^2{\parallel {\mathbf{b}}_i^{*}\parallel }^2$, discrete pruning technique requires a proper definition of partition which is centered at $\mathbf{t}$.

Definition 7

(translated Babai’s partition). Given basis $\mathbf{B}$, target vector $\mathbf{t}={\sum }_{i=1}^n{s}_i{\mathbf{b}}_i^{*}$, Babai’s partition translated to $\mathbf{t}$ is defined by lattice partition $({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$, where for tag $\mathbf{z}\in {\mathbb{Z}}^n$, the cell

$${\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)=\left\{\sum _{i=1}^n{x}_i{\mathbf{b}}_i^{*}:z_i-\frac{1}{2}<x_i-s_i\le z_i+\frac{1}{2}\right\}$$

Definition 8

(Translated Natural partition). Given $\mathbf{B}$ and $\mathbf{t}$ as above, the natural partition translated to $\mathbf{t}$ is defined by lattice partition $({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\right),{\mathbb{N}}^n)$, where for tag $\mathbf{z}\in {\mathbb{N}}^n$, the cell

$${\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)=\left\{\sum _{i=1}^n{x}_i{\mathbf{b}}_i^{*},-\frac{z_i+1}{2}<x_i-s_i\le -\frac{z_i}{2}\mathrm{or}\frac{z_i}{2}<x_i-s_i\le \frac{z_i+1}{2}\right\}$$

Since $({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ and $({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\right),{\mathbb{N}}^n)$ are the translation of $({\mathcal{C}}_{\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ and $({\mathcal{C}}_{\mathbb{N}}\left(\right),{\mathbb{N}}^n)$ with offset $\mathbf{t}$, respectively, obviously they are tessellations of ${\mathbb{R}}^n$ and therefore meet the first property of Definition 4. To prove the uniqueness of lattice vector contained in $({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ and $({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\right),{\mathbb{N}}^n)$, we first give the algorithms to recover $\mathbf{v}\in \mathcal{L}$ from tag $\mathbf{t}$ and give proofs of their correctness, then from the proofs we can derive the bijection property between lattice vector and tag vector.

Proposition 1.

Algorithm BabaiDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) outputs the unique $\mathbf{v}\in \mathcal{L}\left(\mathbf{B}\right)$ such that $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$, and therefore, the translated Babai’s partition $({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ is a $\mathcal{L}$-partition.

Proof. 

We first prove the correctness of Algorithm 4, and then prove the uniqueness of vector contained in ${\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$, which also verifies that the $({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\right),{\mathbb{Z}}^n)$ keeps the second property of lattice partition in Definition 4 after translation.

Consider the output of BabaiDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) in the form of Equation (3), i.e., $\mathbf{v}={\sum }_{k=1}^n{u}_k{\mathbf{b}}_k^{*}$, we have $u_k=x_k+{\sum }_{i=k+1}^n{\mu }_{ik}{x}_i$, where $x_k$ are calculated by line 7–8 in Algorithm 4. Then, the following holds

$$\begin{array}{cc}\hfill u_k-s_k-z_k& =x_k+\sum _{i=k+1}^n{\mu }_{ik}{x}_i-s_k-z_k\hfill \\ \hfill & =⌊z_k+s_k-\sum _{i=k+1}^n{x}_i{\mu }_{i,k}⌉+\sum _{i=k+1}^n{\mu }_{ik}{x}_i-s_k-z_k\hfill \end{array}$$

(8)

for all $k=1,\dots ,n$. From the stipulation of rounding off operation $\lfloor ·\rceil$, it is easy to see $-\frac{1}{2}<u_k-s_k-z_k\le \frac{1}{2}$ and more directly, $-\frac{1}{2}+z_k<u_k-s_k\le \frac{1}{2}+z_k$, which exactly satisfies the definition of cell ${\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$ and we can conclude that $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$.

Now, we assume there are two lattice vector $\mathbf{v}\ne {\mathbf{v}}^{\prime }$ contained in the same cell ${\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$. Let $\mathbf{v}={\sum }_{i=1}^n{x}_i{\mathbf{b}}_i$ and ${\mathbf{v}}^{\prime }={\sum }_{i=1}^n{x}_i^{\prime }{\mathbf{b}}_i$, and assume there exists an index $1\le k\le n$ such that $x_k\ne x_k^{\prime }$ and $x_{k+1}=x_{k+1}^{\prime },x_{k+2}=x_{k+2}^{\prime },\dots ,x_n=x_n^{\prime }$. This means in line 8 of Algorithm 4, $x_k$ and $x_k^{\prime }$ are derived from the different $y_k$ value, denoted by $y_k$ and $y_k^{\prime }$, respectively, and $y_k\ne y_k^{\prime }$. This makes a contradiction since both y and $y^{\prime }$ are calculated by the same $z_k$, $s_k$, and $x_i{\mu }_{i,k}$ ($i\ge k$).    □

Algorithm 4BabaiDecode($\mathbf{t},\mathbf{B},\mathbf{z}$)

Require:    Target vector $\mathbf{t}$, lattice basis $\mathbf{B}$, tag $\mathbf{z}\in {\mathbb{Z}}^n$ Ensure:     lattice vector $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$ 1: Compute orthogonal basis ${\mathbf{B}}^{*}\in {\mathbb{R}}^{n\times n}$ and Gram–Schmidt coefficients $\mathbf{U}={\left({\mu }_{i,j}\right)}_{n\times n}$ 2: for$k=1$tondo 3:       $x_k\leftarrow 0$ 4:       $s_k\leftarrow \frac{\langle \mathbf{t},{\mathbf{b}}_k^{*}\rangle }{\langle {\mathbf{b}}_k^{*},{\mathbf{b}}_k^{*}\rangle }$                         $//$$\mathbf{t}={\sum }_{i=1}^n{s}_i{\mathbf{b}}_i^{*}$ 5: end for 6: for $k=n$to 1 do 7:       $y_k\leftarrow z_k+s_k-{\sum }_{i=k+1}^n{x}_i{\mu }_{i,k}$ 8:       $x_k\leftarrow ⌊y_k⌉$ 9: end for 10: return$\mathbf{v}=\mathbf{Bx}$

Similarly, for natural partition, we also give the decoding algorithm NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) in the following and provide an analogous declaration and proof.

Proposition 2.

Algorithm NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) outputs the unique $\mathbf{v}\in \mathcal{L}\left(\mathbf{B}\right)$ such that $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$, and therefore the translated natural partition $({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\right),{\mathbb{Z}}^n)$ is an $\mathcal{L}$-partition.

Proof. 

Consider the output of NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) written in the form as above, according to Algorithm 5, then for all $k=1,\dots ,n$, there holds:

$$\begin{array}{cc}\hfill u_k-s_k& =x_k+\sum _{i=k+1}^n{x}_i{\mu }_{i,k}-s_k\hfill \\ \hfill & =⌊s_k-\sum _{i=k+1}^n{x}_i{\mu }_{i,k}⌉+\sum _{i=k+1}^n{x}_i{\mu }_{i,k}-s_k+{\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉\hfill \\ \hfill & =⌊y_k⌉-y_k+{\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉\hfill \end{array}$$

(9)

where ${\delta }_k=\mathrm{sign}(⌊y_k⌉-y_k)$ and especially, we stipulate $\mathrm{sign}\left(0\right)=-1$.

Let $\sigma \in \mathbb{N}$, now, we consider four cases:

Case 1: $z_k=2\sigma$ and ${\delta }_k=-1$. In this case, ${\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉=-\sigma$, and since $⌊y_k⌉-y_k\le 0$, we have $⌊y_k⌉-y_k\in (-\frac{1}{2},0]$. With the third line in Equation (9), it is easy to see

$$-\frac{1}{2}-\sigma <u_k-s_k\le -\sigma \Rightarrow -\frac{z_k+1}{2}<u_k-s_k\le -\frac{z_k}{2}$$

Case 2: $z_k=2\sigma +1$ and ${\delta }_k=-1$. In this case, ${\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉=\sigma +1$. Similar to case 1, we have

$$-\frac{1}{2}+(\sigma +1)<u_k-s_k\le \sigma +1\Rightarrow \frac{z_k}{2}<u_k-s_k\le \frac{z_k+1}{2}$$

Case 3: $z_k=2\sigma$ and ${\delta }_k=1$. In this case, ${\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉=\sigma$. Additionally, we have $⌊y_k+0.5⌋-y_k\in (0,\frac{1}{2}]$, and therefore,

$$\sigma <u_k-s_k\le \frac{1}{2}+\sigma \Rightarrow \frac{z_k}{2}<u_k-s_k\le \frac{z_k+1}{2}$$

Case 4: $z_k=2\sigma +1$ and ${\delta }_k=1$. In this case, ${\delta }_k·{(-1)}^{z_k}⌈z_k/2⌉=-(\sigma +1)$. Similar with case 3, we have

$$-(\sigma +1)<u_k-s_k\le \frac{1}{2}-(\sigma +1)\Rightarrow -\frac{z_k+1}{2}<u_k-s_k\le -\frac{z_k}{2}$$

For all the possible cases for Equation (9), we have proved $u_k-s_k$ satisfies the Definition 8, which means $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$. The uniqueness of vector $\mathbf{v}$ can be proved by the similar method of proving Proposition 1.    □

Algorithm 5NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}$)

Require:    Target vector $\mathbf{t}$, lattice basis $\mathbf{B}$, tag $\mathbf{z}\in {\mathbb{Z}}^n$ Ensure:     lattice vector $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$ 1: Compute orthogonal basis ${\mathbf{B}}^{*}\in {\mathbb{R}}^{n\times n}$ and Gram–Schmidt coefficients $\mathbf{U}={\left({\mu }_{i,j}\right)}_{n\times n}$ 2: for$k=1$tondo 3:       $x_k\leftarrow 0$ 4:       $s_k\leftarrow \frac{\langle \mathbf{t},{\mathbf{b}}_k^{*}\rangle }{\langle {\mathbf{b}}_k^{*},{\mathbf{b}}_k^{*}\rangle }$ 5: end for 6: for$k=n$to 1 do 7:       $y_k\leftarrow s_k-{\sum }_{i=k+1}^n{x}_i{\mu }_{i,k}$ 8:       $x_k\leftarrow ⌊y_k⌉$ 9:       if $x_k\le y_k$ then 10:           $x_k\leftarrow x_k+{(-1)}^{z_k}⌈z_k/2⌉$ 11:       else 12:           $x_k\leftarrow x_k-{(-1)}^{z_k}⌈z_k/2⌉$ 13:       end if 14: end for 15: return$\mathbf{v}=\mathbf{Bx}$

Although a certain lattice vector $\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$ (or ${\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$) is determined by the tag $\mathbf{z}$, for vectors randomly selected in the lattice, their distribution behavior still shows some pseudo-randomness, which is called randomness assumption and is commonly applied in the analysis of many SVP algorithms [22,23,25]. The essence of this assumption is to treat the fractional part of GS coefficients $u_i$ of lattice vector $\mathbf{v}={\sum }_{i=1}^n{u}_i{\mathbf{b}}_i^{*}$ as uniformly distributed in a certain interval, and we believe that this is also applicable to the translated cases. Here, we propose the randomness assumption for our lattice partition.

Assumption 1.

Given lattice $\mathcal{L}\left(\mathbf{B}\right)$ and some $\mathbf{t}={\sum }_{i=1}^n{s}_i{\mathbf{b}}_i^{*}$, let lattice vector $\mathbf{v}={\sum }_{i=1}^n{u}_i{\mathbf{b}}_i^{*}$ be a random variable, then, we assume $u_1,\dots ,u_n$ are n independent random variables and each $u_i$ is uniformly distributed in $\left(-\frac{1}{2}+z_i+s_i,\frac{1}{2}+z_i+s_i\right]$ (resp. $\left(-\frac{z_i+1}{2}+s_i,-\frac{z_i}{2}+s_i\right]\cup \left(\frac{z_i}{2}+s_i,\frac{z_i+1}{2}+s_i\right]$), where $\mathbf{z}$ is the tag of cell ${\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)$ (resp. ${\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$) containing $\mathbf{v}$. As the first moment of each ${(u_i-s_i)}^2$ is $\frac{z_i^2}{4}+\frac{1}{12}$ (respectively, $\frac{z_i^2}{4}+\frac{z_i}{4}+\frac{1}{12}$), the expected values of ${\parallel \mathbf{v}-\mathbf{t}\parallel }^2$ in Babai’s partition and natural partition are

$$\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)\right]\stackrel{def}{=}\mathbb{E}\left[{\parallel \mathbf{v}-\mathbf{t}\parallel }^2\right]=\frac{1}{12}\sum _{i=1}^n(12z_i^2+1){\parallel {\mathbf{b}}_i^{*}\parallel }^2$$

and

$$\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right]\stackrel{def}{=}\mathbb{E}\left[{\parallel \mathbf{v}-\mathbf{t}\parallel }^2\right]=\frac{1}{12}\sum _{i=1}^n(3z_i^2+3z_i+1){\parallel {\mathbf{b}}_i^{*}\parallel }^2.$$

Similarly, the variances of ${\parallel \mathbf{v}-\mathbf{t}\parallel }^2$ are

$$\mathbb{V}\left({\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{z}\right)\right)=\sum _{i=1}^n(\frac{z_i^2}{3}+\frac{1}{180}){\parallel {\mathbf{b}}_i^{*}\parallel }^2$$

and

$$\mathbb{V}\left({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)=\sum _{i=1}^n(\frac{z_i^2}{48}+\frac{z_i}{48}+\frac{1}{180}){\parallel {\mathbf{b}}_i^{*}\parallel }^2.$$

We note that Assumption 1 is a generalization of the original randomness assumption (see Corollary 2 and 3 in [25]). In other words, the original randomness assumption is a special case of Assumption 1 where $s_i=0$ for all $i=1,\dots ,n$.

3.2. Interpreting Nearest Plane(s) Algorithm with Lattice Partition

From the perspective of output results, we can immediately conclude that $\mathbf{t}+{\mathcal{P}}_{1/2}\left({\mathbf{B}}^{*}\right)={\mathcal{C}}_{\mathbf{t},\mathbb{Z}}\left(\mathbf{0}\right)={\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{0}\right)$, which means that the output of NearestPlane($\mathbf{B},\mathbf{t}$) exactly equals to BabaiDecode($\mathbf{t},\mathbf{B},\mathbf{z}=\mathbf{0}$) and NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}=\mathbf{0}$).

For NearestPlanes algorithm, since

$$\begin{array}{cc}\hfill & \mathbf{t}+{\mathcal{P}}_{1/2}({\mathbf{B}}^{*}·\mathrm{diag}\left(\mathbf{d}\right))\hfill \\ \hfill =& \mathbf{t}+\left\{\sum _{i=1}^n{a}_i{\mathbf{b}}_i^{*}:-\frac{d_i}{2}<a_i\le \frac{d_i}{2},i=1,\dots ,n\right\}\hfill \\ \hfill =& \bigcup _{\{\mathbf{z}:z_i<d_i\}}{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\hfill \end{array}$$

we can see that the output set of NearestPlanes($\mathbf{B},\mathbf{t},\mathbf{d}$) equals with the set of vectors output by calling NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}=\mathbf{z}$) on all tags $\mathbf{z}$ with $z_i<d_i$ for all $i=1,\dots ,n$.

From the perspective of calculation process, we also give an interpretation of the essential equivalence between Nearest Plane(s) algorithms and lattice partition in depth. In NearestPlane($\mathbf{B},\mathbf{t}$) (Algorithm 1), for $k=n$, we can easily verify that $x_n=⌊\frac{\langle \mathbf{t},{\mathbf{b}}_n^{*}\rangle }{\langle {\mathbf{b}}_n^{*},{\mathbf{b}}_n^{*}\rangle }⌉=\lfloor s_n\rceil$. For iteration indexes $k\ge k^{\prime }$, we assume $x_k=\lfloor s_k-{\sum }_{i=k+1}^n{x}_i{\mu }_{i,k}\rceil$, and in line 5 of Algorithm 1, we have ${\mathbf{t}}^{\prime }=\mathbf{t}-{\sum }_{i=k}^n{x}_i{\mathbf{b}}_i$. Then, in the next loop, we actually compute $x_{k^{\prime }-1}=⌊\frac{\langle \mathbf{t}-{\sum }_{i=k^{\prime }}^n{x}_i{\mathbf{b}}_i,{\mathbf{b}}_{k^{\prime }-1}^{*}\rangle }{\langle {\mathbf{b}}_{k^{\prime }-1}^{*},{\mathbf{b}}_{k^{\prime }-1}^{*}\rangle }⌉=\lfloor s_{k^{\prime }-1}-{\sum }_{i=k^{\prime }}^n{x}_i{\mu }_{i,k^{\prime }-1}\rceil$, which is equivalent to line 3 of Algorithm 5 with $z_i=0$.

As for NearestPlanes($\mathbf{B},\mathbf{t},\mathbf{d}$) (Algorithm 2), the combination coefficients $\mathbf{x}=(x_1,\dots ,x_n)$ of output vector $\mathbf{v}=\mathbf{Bx}$ form a recursion tree with depth n, and each parent node with path $x_n,x_{n-1},\dots ,x_{k+1}$ in the $(n-k)$-th layer leads to $d_k$ child nodes $x_k^{\left(0\right)},\dots ,x_k^{(d_k-1)}$ (line 4), where $x_k^{\left(z\right)}$ is the $(z+1)$-th closest integer to $⌊\frac{\langle \mathbf{t}-{\sum }_{i=k+1}^n{x}_i{\mathbf{b}}_i,{\mathbf{b}}_k^{*}\rangle }{\langle {\mathbf{b}}_k^{*},{\mathbf{b}}_k^{*}\rangle }⌉=⌊s_k-{\sum }_{i=k+1}^n{x}_i{\mu }_{i,k}⌉=y_k$, which is also calculated in line 7 of Algorithm 5. Now, we explain how the “$(z+1)$-th closest integer to $y_k$” is calculated. Consider the quadratic function ${(x-y_k)}^2$ of variable x, the integral value of x closest to $y_k$ is $x_k^{\left(0\right)}=\lfloor y_k\rceil$. If the rounding off goes to $-\infty$ direction, i.e., $\lfloor y_k\rceil \le y_k$, then the next integral value of x closest to $y_k$ takes the $+\infty$ direction and $x_k^{\left(1\right)}=\lfloor y_k\rceil +1$. Then, the second integer goes in the same direction with rounding off and $x_k^{\left(2\right)}=\lfloor y_k\rceil -1$, and so on. It can be easily deduceed that $x_k^{\left(z\right)}={\delta }_k·{(-1)}^z⌈z/2⌉$ which is what NaturalDecode (Algorithm 5) actually does. Therefore, for each leaf node correspond to coefficients $(x_1^{\left(z_1\right)},\dots ,x_n^{\left(z_n\right)})$ reached by NearestPlanes algorithm, it is equivalent to NaturalDecode with input tag $\mathbf{z}=(z_1,\dots ,z_n)$.

The work of AN17 [25] gave experimental evidence to show that the natural partition is expected to contain a short vector with higher probability than Babai’s partition. In this section, we also exhibit that natural partition has more explainability by using it to interpret the nearest plane(s) algorithms.

3.3. DP Enumeration for BDD

Babai’s Nearest plane algorithm or nearest planes algorithm is actually a single round of lattice decoding on a certain (but not the optimal) set of cells. Inspired by discrete pruned enumeration for SVP, here, we propose the DP enumeration based on the translated lattice partition to solve BDD problem. This algorithm includes nearest plane(s) algorithms as special cases, while it is expected to achieve an optimal performance when solving BDD.

To migrate DP enumeration from SVP to BDD, a peculiar case one has to consider in addition is that, in some cryptanalysis scenarios, the information an adversary can acquire is insufficient to construct a “gap” in the lattice and therefore the lattice vector found by BDD algorithm might not be the “unique” vector close to a target vector $\mathbf{t}$. For example, solving LWE with few samples [32], and the lattice attack of ECDSA with very few leaked nonce bits [12,14]. Assume that the BDD instance has a right solution ${\mathbf{v}}_0$ such that $\parallel {\mathbf{v}}_0-\mathbf{t}\parallel \approx R$, and then by searching in an n-dimensional ball centered at $\mathbf{t}$ with radius R, the enumeration algorithm might find more than one lattice vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_K$ such that all $\parallel {\mathbf{v}}_i-\mathbf{t}\parallel \le R$. In such a case, each of them should be checked to see which is the right solution corresponding to the secret of the cryptosystem. This oracle related to a certain cryptographic algorithm is also a “BDD predicate” by Albrecht and Heninger [14], and we will call it a BDD oracle Orc$(·)$ to be consistent with the definition of generalized BDD.

Algorithm 6 gives the framework of DP enumeration with natural partition $({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\right),{\mathbb{N}}^n)$. We note that in a standard BDD instance, i.e., $\mathrm{dist}(\mathbf{t},\mathcal{L})\le d<{\lambda }_1/2$, the lattice vector satisfying $\parallel \mathbf{v}-\mathbf{t}\parallel <R=d$ is unique and we can omit the BDD oracle Orc$(·)$. To solve the BDD instance derived from different cryptosystems, the Pred$(·)$ is also different and we will give their detail in Section 5.  

Algorithm 6DPenum4BDD

Require:     BDD target vector $\mathbf{t}$, lattice basis $\mathbf{B}$, expected length of BDD error length R, BDD oracle Orc$(·)$, number of tags M, BKZ parameter $\beta$ Ensure:     $\mathbf{v}\in \mathcal{L}\left(\mathbf{B}\right)$ such that $\parallel \mathbf{v}-\mathbf{t}\parallel <R$ 1: Run BKZ reduction on $\mathbf{B}$ with blocksize $\beta$ 2: while true do 3:       $S\leftarrow ⌀$ 4:       $r\leftarrow$ BinSearch($\mathbf{B},\mathbf{t},M$)                   $//$ Find r such that there are M tags $\mathbf{z}$ satisfying $\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right]<r$ 5:       $S\leftarrow$ CellEnum(${\mathbf{B}}^{*},\mathbf{t},r$)                   $//$ Enumerate these M tags and save them in set S 6:       for $\mathbf{z}\in S$ do 7:             $\mathbf{v}\leftarrow$ NaturalDecode($\mathbf{t},\mathbf{B},\mathbf{z}$) 8:             if ${\parallel \mathbf{v}-\mathbf{t}\parallel }^2<R^2$ and Orc$\left(\mathbf{v}\right)=1$ then 9:                  return $\mathbf{v}$                                                     $//$ Find the solution 10:             end if 11:       end for 12:       Reprocess($\mathbf{B},\beta$)                   $//$ generate a different reduced basis and repeat the enumeration 13: end while

This framework is inherited from the improved version of DP enumeration [26], and some details should be explained in depth in order to make our algorithm adapt to the BDD problem.

Binary search and cell enumeration.

The goal of line 4 and 5 of Algorithm 6 is to generate a batch of cells $S=\left\{{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)\}$ which are “most likely” to contain a lattice vector very close to $\mathbf{t}$. The optimality of such a set is generally indicated by the expected distance $\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right]$. However, the original definition of $\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right]$ cannot guarantee the polynomial time complexity of CellEnum and the indicator $\mathbb{E}\left[{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right]$ should be slightly modified. The pivotal modification is removing the constant part of each item $\frac{1}{12}{\sum }_{i=1}^n(3z_i^2+3z_i+1){\parallel {\mathbf{b}}_i^{*}\parallel }^2$, and the indicator becomes

$$f\left({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)\stackrel{def}{=}\sum _{i=1}^n\frac{1}{4}(z_i^2+z_i){\parallel {\mathbf{b}}_i^{*}\parallel }^2$$

(10)

Since the bound r for cell enumeration is hard to determine, one should specify the size of set S, and then r can be computed by a binary search method by calling CellEnum (Algorithm 7) as a subalgorithm.

Algorithm 7CellEnum

Require:     $\mathbf{B}$, r Ensure:     $S=\left\{\mathbf{z}\in {\mathbb{N}}^n:f\left(\mathbf{z}\right)\le r\right\}$ 1: Compute orthogonal basis ${\mathbf{B}}^{*}=[{\mathbf{b}}_1^{*},\dots ,{\mathbf{b}}_n^{*}]$ from $\mathbf{B}$ 2: $S\leftarrow ⌀$ 3: $z_1=z_2=\dots =z_n=0$ 4: $c_1=c_2=\dots =c_{n+1}=0$ 5: $k\leftarrow 1$ 6: while true do 7:       $c_k\leftarrow c_{k+1}+\frac{1}{4}(z_i^2+z_i){\parallel {\mathbf{b}}_i^{*}\parallel }^2$                            $//$ Equation (10) 8:       if $c_k<r$ then 9:             if $k=1$ then 10:                  $S\leftarrow S\cup \{\mathbf{z}=(z_1,z_2,\dots ,z_n)\}$ 11:                  $z_k\leftarrow z_k+1$; 12:             else 13:                  $k\leftarrow k-1$ 14:                  $z_k\leftarrow 0$ 15:             end if 16:       else 17:             $k\leftarrow k+1$ 18:             if $k=n+1$ then 19:                 exit 20:             else 21:                $z_k\leftarrow z_k+1$ 22:             end if 23:        end if 24: end while 25:   return S

Algorithm 8 gives a polynomial-time binary search method to calculate the cell enumeration radius r. If $ϵ$ is small, say $ϵ=0.005$ or smaller, the number of tags satisfying $f\left(\mathbf{z}\right)<r$ can be approximately counted as M. Note that in line 5, CellEnum can be terminated instantly as long as it outputs more than $(1+ϵ)M$ tags.

Algorithm 8BinSearch

Require:     $\mathbf{B},\mathbf{t},M,ϵ$ Ensure:     $r\in \mathbb{R}$ such that $\#\{\mathbf{z}:f(\mathbf{z})<r\in [(1-ϵ)M,(1+ϵ)M\left]\right\}$ 1: $R_l\leftarrow f\left(\mathbf{0}\right)$ 2: $R_r\leftarrow f([\lceil M^{\frac{1}{n}}\rceil ,\dots ,\lceil M^{\frac{1}{n}}\rceil ]$ 3: while$R_l<R_r$do 4:       $R_m\leftarrow \frac{R_l+R_r}{2}$ 5:       if CellEnum(${\mathbf{B}}^{*},\mathbf{t},r$) returns more than $(1+ϵ)M$ tags then 6:            $R_l\leftarrow R_m$                  $//$$R_m$ is too large 7:       else if CellEnum(${\mathbf{B}}^{*},\mathbf{t},r$) returns less than $(1-ϵ)M$ tags then 8:            $R_r\leftarrow R_m$                  $//$$R_m$ is too small 9:       else 10:            return $r\leftarrow R_m$              $//$$R_m$ is acceptable 11:       end if 12: end while

According to [26], the time complexity of CellEnum is proved to be $O\left((2n-1)·M/2\right)$, and BinSearch calls CellEnum for $O\left(logn+\right.$$\left.log\frac{1}{ϵ}+nlog\left(n\right)\right)$ times.

Lattice basis reprocessing.

When solving BDD, a single round of DP enumeration might not find the solution, since its searching space does not cover the whole ${\mathcal{B}}_n(\mathbf{t},R)$. A standard way is to re-randomize the lattice basis and repeat the procedures on the new basis. To improve the efficiency and for the convenience of concrete time analysis, Luan et al. [26] proposed a set of comprehensive strategies along with the preprocessing of DP enumeration, which can be instantiated as Reprocess (Algorithm 9).

At the very beginning of DPenum4BDD, the lattice basis is BKZ${}_{\beta }$-reduced, and in the following loops, Reprocess heuristically guarantees that the properties of output basis are as good as those of a fully BKZ${}_{\beta }$-reduced basis at a very small and controllable cost, while the latter usually has rather long and unpredictable running time.

Algorithm 9Reprocess

Require:     $\mathbf{B},\beta ,k$ Ensure:     ${\mathbf{B}}_{new}$ 1: $\mathbf{Q}\leftarrow \mathbf{I}\in {\mathbb{Z}}^{n\times n}$                         $//$$\mathbf{I}$ is identity matrix 2: Randomly select n position $(i,j)$ with $i<j$ and let $Q_{ij}\leftarrow \{\pm 1,\pm 2\}$ 3: $\mathbf{B}\leftarrow \mathbf{BQ}$ 4: Run k-tours of BKZ reduction on $\mathbf{B}$                  $//$ Usually $k=8$ 5: return$\mathbf{B}$

4. Complexity Analysis and Cost Estimation

We note that algorithm NaturalDecode can be called in line 10 of algorithm CellEnum, and the invalid tags can be directly discarded. Therefore, the whole DP enumeration does not need to save any output of CellEnum. It is easy to see that DPenum4BDD essentially has polynomial-space complexity. In this section, we only focus on the running time of DPenum4BDD. The cost estimation has an overall framework

$$T_{total}=T_{pre}+\frac{T_{repro}+T_{bin}+T_{cell}+M·T_{decode}+K·T_{orc}}{p_{succ}}$$

(11)

• $T_{pre}$: Cost of preprocessing, which is generally a full BKZ${}_{\beta }$ reduction on a n-dimensional lattice. For preprocessing, where the required blocksize $\beta$ is usually very small, the most practical algorithm is BKZ 2.0 [18] and the running time of such a preprocessing method is easy to estimate using BKZ simulator. In particular, the fraction part in (11) is much larger than $T_{pre}$ when the scale of BDD problem is very large, hence, it can be ignored in the asymptotic estimation.
• $T_{repro}$, $T_{bin}$, $T_{cell}$, $T_{decode}$: The running time of Reprocess, BinSearch, CellEnum and NaturalDecode, respectively. These inherent subalgorithms of the original DP enumeration are studied in detail by [26] and have explicit cost estimation formulae.
• K: The number of lattice vector $\mathbf{v}$ such that $\parallel \mathbf{v}-\mathbf{t}\parallel <R$ and should be verified by the BDD oracle in line 8 of DPenum4BDD.
• $T_{orc}$: The cost of recovering a lattice vector to the corresponding cryptographic secret and checking whether the BDD attack is successful.
• $p_{succ}$: The success probability of finding out the right solution in a single round of DP enumeration.

Let S be the output tag set of algorithm CellEnum in one round of DPenum4BDD, then the searching area in this round can be represented by

$${\mathrm{Ball}}_n(\mathbf{t},R)\cap P\stackrel{def}{=}{\mathrm{Ball}}_n(\mathbf{t},R)\cap \left\{\bigcup _{\mathbf{z}\in S}{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right\}$$

where ${\mathrm{Ball}}_n(\mathbf{t},R)$ denotes the n-dimensional ball with radius R centered at $\mathbf{t}$.

Under Gaussian heuristic, the number of lattice contained in ${\mathrm{Ball}}_n(\mathbf{t},R)\cap P$ can be estimated by

$$\begin{array}{cc}\hfill K\approx & \frac{\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\cap \left\{{\bigcup }_{\mathbf{z}\in S}{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right\}\right)}{\mathrm{vol}\left(\mathcal{L}\right)}\hfill \\ \hfill =& \frac{{\sum }_{\mathbf{z}\in S}\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\cap {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)}{{\prod }_{i=1}^n\parallel {\mathbf{b}}_i^{*}\parallel }\hfill \end{array}$$

(12)

We note that if $K\ll 1$ in Equation (12), which implies the solution is unique and the BDD problem is the original version (Definition 2), then there is no need to call BDD oracle. In this situation, we let $K=0$ in the cost model in Equation (11).

Then, only the value of success probability $p_{succ}$ remains to be decided. The discussion of $p_{succ}$ can be classified into the following three cases.

Case 1: Generalized model

In the generalized definition of BDD, the estimated bound R of BDD cannot guarantee $R<{\lambda }_1/2$, which indicates that there might be more than one lattice vectors lying in ${\mathrm{Ball}}_n(\mathbf{t},R)$. This case was recently discussed by [14] for solving the hidden number problem underlying ECDSA. In this case, K can be directly derived from Equation (12) under Gaussian heuristic as above. However, there are about $N\approx \frac{\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\right)}{\mathrm{vol}\left(\mathcal{L}\right)}$ lattice vector contained in ${\mathrm{Ball}}_n(\mathbf{t},R)$ and there is only one corresponding to the right secret. Assume that all the lattice vectors in the ball are uniformly distributed, and in each round of DP enumeration, we can randomly find K candidate vectors, then the possibility that the solution is contained in them is

$$p_{succ}=\frac{\left(\genfrac{}{}{0pt}{}{N-1}{K-1}\right)}{\left(\genfrac{}{}{0pt}{}{N}{K}\right)}=\frac{K}{N}\approx \frac{{\sum }_{\mathbf{z}\in S}\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\cap {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)}{{\mathrm{Ball}}_n(\mathbf{t},R)}$$

(13)

Case 2: Strict BDD with general distribution assumption

If the only one lattice vector $\mathbf{v}$ contained in ${\mathrm{Ball}}_n(\mathbf{t},R)$ is considered to be randomly distributed over ${\mathrm{Ball}}_n(\mathbf{t},R)$, then the probability that $\mathbf{v}$ falls in a cell ${\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$ can be derived from the geometric probability model

$$\begin{array}{cc}\hfill p_{succ}\left(\mathbf{z}\right)& =\underset{\mathbf{v}\leftarrow {\mathrm{Ball}}_n(\mathbf{t},R)}{\mathrm{Pr}}\left\{\mathbf{v}\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right\}\hfill \\ \hfill & =\frac{\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\cap {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)}{\mathrm{vol}\left({\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)}\hfill \end{array}$$

(14)

This is also the probability estimation method of [25] (refer to Heuristic 2 in [25]). Furthermore, if we assume that the lattice basis has a stable quality, especially the shape of Gram–Schmidt sequence ${\left\{{\mathbf{b}}_i^{*}\right\}}_{i=1}^n$, which is experimentally verified in [26], then the value of Equation (12) is also stable during the repetition of DP enumeration. Therefore, we can use the output set S of a single round DP enumeration to estimate the success probability of the algorithm on average:

$$p_{succ}=\sum _{\mathbf{z}\in S}{p}_{succ}\left(\mathbf{z}\right)=\sum _{\mathbf{z}\in S}\frac{\mathrm{vol}\left({\mathrm{Ball}}_n(\mathbf{t},R)\cap {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\right)}{{\prod }_{i=1}^n\parallel {\mathbf{b}}_i^{*}\parallel }$$

(15)

Case 3: BDD with known error distribution

For a common case in lattice-based cryptography, the error vector $\mathbf{e}={\mathbf{v}}_0-\mathbf{t}$ is pre-selected following some certain distribution. In typical this refers to discrete Gaussian distribution $D_{\mathbb{Z},\alpha ·q}$, with parameter $s=\alpha q$. Lindner and Peikert gives the success probability of their nearest planes algorithm by estimating approximately using the continuous Gaussian distribution ([1], Equation (5)). [2] also adopts this method and gives the corresponding analysis for GNR enumeration. Following the same assumption, the success probability of finding ${\mathbf{v}}_0$ in a given cell ${\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$ can be estimated by

$$\begin{array}{cc}\hfill & p_{succ}\left(\mathbf{z}\right)\hfill \\ \hfill =& \mathrm{Pr}\{{\mathbf{v}}_0\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\}\hfill \\ \hfill =& \prod _{i=1}^n\mathrm{Pr}\left\{\left|\frac{\langle \mathbf{e},{\mathbf{b}}_i^{*}\rangle }{\langle {\mathbf{b}}_i^{*},{\mathbf{b}}_i^{*}\rangle }\right|\in \left[\frac{z_i}{2},\frac{z_i+1}{2}\right]\right\}\hfill \\ \hfill =& \prod _{i=1}^n\left(\mathrm{erf}(\frac{\sqrt{\pi }}{s}·\frac{z_i+1}{2}\parallel {\mathbf{b}}_i^{*}\parallel )-\mathrm{erf}(\frac{\sqrt{\pi }}{s}·\frac{z_i}{2}\parallel {\mathbf{b}}_i^{*}\parallel )\right)\hfill \end{array}$$

(16)

and

$$p_{succ}=\sum _{\mathbf{z}\in S}\mathrm{Pr}\{\mathbf{e}\in {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)\}$$

(17)

To accelerate the computation of Equations (12), (15) and (17), it is suggested that one can apply a stratified sampling method to calculate the sum of each on the tag set S. The work in [25] also provides a detailed numerical calculation method on the volume of hyper ball-box intersection ${\mathrm{Ball}}_n(\mathbf{t},R)\cap {\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right)$.

5. Experiments and Application

5.1. Solving LWE

We first compare the performance of DPenum4BDD with the previous work of [2], which includes the rerandomized nearest planes algorithm and classical enumeration with pruning. We take the LWE instances provided by LWE challenge [34]. Since the original nearest planes algorithm only searches once without any repetition, the rerandomized nearest planes algorithm is a more reasonable reference. As explained in Section 3.2, the rerandomized nearest planes algorithm with parameter $(d_1,\dots ,d_n)$ is essentially the discrete pruning on some designated cells of natural partition $P=\left\{{\mathcal{C}}_{\mathbf{t},\mathbb{N}}\left(\mathbf{z}\right):z_i<d_i,\forall i=1,\dots ,n\right\}$. Therefore, we run the nearest planes algorithm by using the same implementation of our DPenum4BDD but only with different tag enumeration strategy: for the nearest planes algorithm, we take $S=\{\mathbf{z}:z_i<d_i,\forall i=1,\dots ,n\}$ and for the discrete pruning enumeration, we obtain S by Algorithm 7.

For each LWE challenge instance with parameter $(n,q,s)$, we first determine the lattice dimension m such that $\parallel \mathbf{e}\parallel \approx \sqrt{m}s$ is slightly larger than $\frac{1}{2}{\lambda }_1\left(\mathcal{L}\right)$. For both nearest planes and discrete pruned enumeration, we use the cost model defined by (11) along with a BKZ simulator [21], and the success probability $p_{succ}$ corresponds to Equation (17) in Case 3, since all the LWE instances in this subsection use discrete Gaussian distribution. We calculate the optimal parameter for each algorithm to minimize the estimated cost by a Nelder–Mead optimization method which is applied in the DP enumeration for SVP [26]. For the classical enumeration, we take the implementation in fplll library [35] and compute the optimal pruning parameters using the Pruner module in fplll. The preprocessing algorithm is BKZ 2.0 in fplll.

For each LWE instance, we randomly choose m samples to construct a lattice. On each lattice basis, we run the three algorithms with their optimal parameter respectively, and the average running time for finding the LWE error $\mathbf{e}$ on 30 trials is shown in

Table 1. The experimental performance for solving LWE challenge [34].

LWE $(\mathit{n},\mathit{q},\mathit{s})$	Nearest Planes (s)	Extreme Pruning (s)	DPenum4BDD (s)	$(\mathit{m},\mathit{\beta },\mathit{M})$
(40, 1601, 8.005)	15.4	3.2	5.2	(80, 25, 30,000)
(45, 2027, 10.135)	38.1	18.9	26.1	(90, 36, 45,000)
(50, 2503, 12.515)	153	103.2	57.3	(120, 42, 80,000)
(55, 3037, 15.185)	2868.3	2015.1	1566.5	(141, 52, 120,000)
(60, 3607, 18.035)	4910.1	4681.1	3664.5	(160, 60, 200,000)

. The running time is in seconds, and the last column gives the parameter we used for DPenum4BDD as a reference.

Then, we give a numerical comparison of the cost estimation on LWE instances of Lindner–Peikert cryptosystem [1]. The LWE instances are generated using sage.crypto.lwe module in Sage toolkit. In

Table 2. The numerical cost prediction for solving LWE with Lindner–Peikert parameter setting.

LWE $(\mathit{n},\mathit{q},\mathit{s})$	Nearest Planes (log(s))	Linear Pruning (log(s))	DPenum4BDD (log(s))	Experiment
(128, 2053, 6.7)	26.6	23.6	12.8	526.3 (s)
(192, 4093, 8.9)	66.5	62.8	38.8	-
(256, 4093, 8.3)	111.4	105.5	68.5	-

, the second and third columns are the numerical results from [2] and the last column gives the prediction of our algorithm. The cost is in base-2 logarithm (seconds). In experiments, we are even able to solve the LWE instance of $n=128$ in several minutes, which is only about 9.03 log(s) and is rather lower than our prediction.

Both the experiments and simulated prediction results show that lattice enumeration with improved discrete pruning strategy performs better than the previous algorithms in the category of directly solving BDD problem.

5.2. Solving HNP under Generalized BDD Model

In this part, we apply our algorithm on the attacking of DSA described by Nguyen and Shparlinski [10], which is also reduced to solving a hidden number problem.

The Digital Signature Algorithm (DSA) is, given large prime numbers $q,p$ such that $q|p-1$, the signer uses his secret key $\alpha \in {\mathbb{F}}_q^{*}$ and a randomly chosen nonce $k\in {\mathbb{F}}_q^{*}$ to sign a message $\mu$ and output two elements in ${\mathbb{F}}_q$

$$\begin{array}{cc}\hfill r\left(k\right)& =(g^{k}modp)modq\hfill \\ \hfill s(k,\mu )& =k^{-1}(h\left(\mu \right)+\alpha r\left(k\right))modq\hfill \end{array}$$

where $g\in {\mathbb{F}}_p$ has multiplicative order q and $h(·)$ is a random hash function. In the following, the signature $\left(r\right(k),s(k,\mu \left)\right)$ is denoted by $(r,s)$, and $h\left(\mu \right)$ by h for short.

The hidden number problem originating from DSA requires to recover the secrete $\alpha \in {\mathbb{F}}_q^{*}$ for many known $t\in {\mathbb{F}}_q$ and the corresponding “approximation” of $\alpha t$, which is denoted by ${\mathrm{APP}}_{\ell ,q}(\alpha ,t)$. ${\mathrm{APP}}_{\ell ,q}(\alpha ,t)$ is any rational number r such that ${\left|\alpha t\right|}_q\le q/2^{\ell +1}$ where ${\left|x\right|}_q$ denotes the minimal residue of x modulo q. As a matter of fact, the leaked information of k reveals an approximation of $\alpha t$. If the ℓ least significant bits of k are known, i.e., we can obtain a number a of ℓ-bit length such that $2^{\ell }|k-a$, then we can define two elements

$$\begin{array}{cc}\hfill t& =2^{-\ell }·r·s^{-1}\hfill \\ \hfill u& =2^{-\ell }(a-s^{-1}·h)modq-q/2^{\ell +1}\hfill \end{array}$$

It is proved that u satisfies the definition of ${\mathrm{APP}}_{\ell ,q}(\alpha ,t)$.

Given enough signatures with leaked k, one can easily compute the HNP pairs $(t_i,u_i)$ ($i=1,\dots ,d$) and construct a $(d+1)$-dimensional lattice $\mathcal{L}\left(\mathbf{B}\right)$ with column basis

$$\mathbf{B}=\left(\begin{array}{ccccc}q{2}^{\ell +1}& & & & t_1{2}^{\ell +1}\\ & q{2}^{\ell +1}& & & t_2{2}^{\ell +1}\\ & & \dots & & \dots \\ & & & q{2}^{\ell +1}& t_d{2}^{\ell +1}\\ 0& 0& \dots & 0& 1\end{array}\right)$$

(18)

and has volume $\mathrm{vol}\left(\mathcal{L}\left(\mathbf{B}\right)\right)={(q·2^{\ell +1})}^d$.

Let $\mathbf{u}=(u_1{2}^{\ell +1},\dots ,u_d{2}^{\ell +1},0)$ be a target vector. Then, there exists a vector in the form of ${\mathbf{v}}_0=((\alpha t_1+q_1{x}_1)2^{\ell +1},\dots ,(\alpha t_d+q_d{x}_d)2^{\ell +1},\alpha )\in \mathcal{L}\left(\mathbf{B}\right)$. Nguyen and Shparlinski proves that $\parallel {\mathbf{v}}_0{-\mathbf{u}\parallel }_{\infty }\le q$ [10], and naturally leads to a Euclidean norm bound $\parallel {\mathbf{v}}_0-\mathbf{u}\parallel \le \sqrt{d+1}·q$. From a practical point of view, the value of $\parallel {\mathbf{v}}_0-\mathbf{u}\parallel$ is usually relatively small. Intuitively, if the number of leaked bits ℓ goes very small, ${\lambda }_1\left(\mathcal{L}\left(\mathbf{B}\right)\right)\approx \sqrt{\frac{d+1}{2\pi e}}{\left(q{2}^{\ell +1}\right)}^{d/(d+1)}$ also goes small, and the corresponding BDD problem becomes harder. There might hold $\parallel \mathbf{e}\parallel \gtrsim {\lambda }_1\left(\mathcal{L}\left(\mathbf{B}\right)\right)$, which implies a generalized BDD problem with a BDD oracle as described in Algorithm 10. From another perspective, to amount a successful attack, a small ℓ requires more signatures with leaked nonce, which increases the workload of leakage detection.

Algorithm 10OrcDSA-HNP

Require:     $\mathbf{v}\in \mathcal{L}\left(\mathbf{B}\right)$ as defined in Equation (18) 1: Randomly choose a DSA signature $(r,s)$ and corresponding message $\mu$ 2: ${\alpha }^{\prime }\leftarrow v_{d+1}·2^{\ell +1}$ 3: $k^{\prime }\leftarrow {\alpha }^{\prime }r+h\left(\mu \right)·s^{-1}modq$ 4: if$r\ne r\left(k^{\prime }\right)$then 5:        return 0 6: else 7:        return 1 8: end if

We run the DPenum4BDD with Orc_DSA-HNP to solve HNP problem stated above, on lattice defined in Equation (18). For DSA signatures, we randomly chosen 160-bit q and 512-bit p following [2,10]. Then, we fix a secrete $\alpha \in {\mathbb{F}}_q^{*}$, and generate d signatures with different nonces k. We assume the last ℓ bits of each k is known and construct lattice as described above to solve the corresponding HNP instance. The searching bound is set to be $R=\gamma \sqrt{d+1}q$ for some reasonable $\gamma$ such that $\parallel {\mathbf{v}}_0-\mathbf{u}\parallel <R$ for most of the instances.

Table 3. Results for solving HNP under DSA with partially known nonces.

ℓ	d	${\mathit{p}}_{\mathbf{succ}}$ (Estimated)	Actual Rounds	Total Cost (s)	$(\mathit{\beta },\mathit{M})$	Previous Work
3	64	0.089	12	523.6	(30, 150,000)	d = 100, mostly solvable using nearest plane. [10]
3	66	0.11	11	363.3
3	68	0.34	5	215.8
2	96	3.04 × 10${}^{-6}$	-	-	(45, 300,000)	d = 100, success rate $=23\%$, expected cost = 4185/0.23 ≈ 18,195.7 s [2]
2	98	6.39 × 10${}^{-5}$	22,895	26,578.2
2	100	1.60 × 10${}^{-4}$	8264	10,315.4

presents the experimental results of the performance of discrete pruned enumeration, along with the success probability prediction and parameter we heuristically used. The data in each line take the average value (with rounding off) of 10 trials. The column of $p_{succ}$ is the success probability predicted by the model in Section 4. The distribution of BDD error ${\mathbf{v}}_0-\mathbf{u}$ is hard to deduce and we simply assume it follows a uniform distribution over a ball. For $\ell =3,d=64$ and $\ell =2,d=96,98$, the probability model refers to case 1 in Section 4 since the searching bound of DP enumeration is slightly larger than ${\lambda }_1$ under these settings. As for the rest experiments, the bound is small enough compared with ${\lambda }_1$ and we use the model given in case 2. The 4th column in Table 3 is the actual number of rounds that DP enumeration uses for recovering the right secrete $\alpha$, which approximately verifies the expectation given by $1/p_{succ}$.

For $\ell =3$, it is already verified that the attack is mostly successful and very efficient with $d=100$ signatures by Babai’s nearest plane algorithm, while our results show that discrete pruned enumeration could recover the secret in a lower dimension $d\approx 68$ within a few minutes, which is also an acceptable running time. For $\ell =2$, we first compare the performance of DP enumeration with the result given by classical enumeration [2] under the same condition $d=100$. In terms of the overall expected cost of recovering the secrete, DP enumeration is slightly faster than classical enumeration. We note that the success probability of a single round of discrete pruning is much lower than classical pruning method, but it searches for much fewer vectors in a round and could repeat very fast, and achieve a better performance globally. We also try to solve the HNP with fewer signatures, which is also feasible in $d=98$, but the experiment is almost unreachable for $d=96$ under the current parameters for DPenum4BDD, and the estimation shows that it might take several days to recover the secret.

6. Conclusions and Further Work

In this work, the SVP algorithm—discrete pruned enumeration is transplanted to an approximate algorithm for solving CVP. We reveal the internal connection between this emergent algorithm and some classical CVP algorithms, including Babai’s nearest plane and its variant, the nearest planes algorithm. We propose several success probability models for its application in various cryptanalysis scenarios. The experimental results show that our model can approximately estimate the cost, and the actual performance of DP enumeration exceeds some previous work: For both the LWE and DSA-HNP cases, the efficiency of DP enumeration is higher than the classical enumeration and nearest planes algorithms, and for the DSA-HNP case, it requires less information about the leaked nonces.

For further research on the application of DP enumeration, it might be valuable to consider some more scenarios in cryptanalysis, such as solving the extended HNP problem for attacking DSA/ECDSA utilizing the non-consecutive leaked bits [13,36]. The parallelized implementation is also a practical issue to be considered.