On the Concrete Security of LWE With Small Secret

Abstract

Lattice-based cryptography is currently under consideration for standardization in the ongoing NIST PQC Post-Quantum Cryptography competition, and is used as the basis for Homomorphic Encryption schemes world-wide. Both applications rely specifically on the hardness of the Learning With Errors (LWE) problem. Most Homomorphic Encryption deployments use small secrets as an optimization, so it is important to understand the concrete security of LWE when sampling the secret from a non-uniform, small distribution. Although there are numerous heuristics used to estimate the running time and quality of lattice reduction algorithms such as BKZ2.0, more work is needed to validate and test these heuristics in practice to provide concrete security parameter recommendations, especially in the case of small secret. In this work, we introduce a new approach which uses concrete attacks on the LWE problem as a way to study the performance and quality of BKZ2.0 directly. We find that the security levels for certain values of the modulus q and dimension n are smaller than predicted by the online Lattice Estimator, due to the fact that the attacks succeed on these uSVP lattices for blocksizes which are smaller than expected based on current estimates. We also find that many instances of the TU Darmstadt LWE challenges can be solved significantly faster when the secret is chosen from the binary or ternary distributions.

1 Introduction

Lattice-based cryptography, proposed more than 20 years ago, is currently used as the basis for Homomorphic Encryption schemes world-wide. Cryptosystems based on the hardness of lattice problems are also under consideration for standardization in the ongoing NIST PQC Post-Quantum Cryptography competition. Both applications rely specifically on the hardness of the Learning with Errors (LWE) problem [1].

Homomorphic Encryption allows computations on encrypted data, with security parameters for practical applications specified in HES, the Homomorphic Encryption Standard [2]. For efficiency reasons, it is common in homomorphic encryption to sample the secret from special distributions, such that it has small entries [3]. For example, two common distributions are the binary or ternary distributions [4, 5], where the entries in the secret are in $\{0,1\}$ or $\{0,\pm 1\}$ respectively. We also consider secrets sampled from the same small discrete gaussian distribution as the errors. In fact, the Homomorphic Encryption Standard [2] specifies tables of secure parameters for three possible distributions for the secret vector: uniform, ternary, and error distributions.

When the secret has a small norm, instances of LWE can be embedded into instances of the unique Shortest Vector Problem (uSVP) [6,7,8]. To recover the shortest vector, lattice reduction algorithms such as the BKZ2.0 algorithm [9] are currently the most effective in practice. Although there are numerous heuristics used to estimate the running time and quality of lattice reduction algorithms such as BKZ2.0, [10,11,12], more work is needed to validate and test these heuristics in practice to provide concrete security parameter recommendations, especially in the case of small secret and small error.

In this work, we introduce a new approach which uses concrete attacks on the LWE problem as a way to study the performance and quality of BKZ2.0 directly. We generate random LWE instances using secrets sampled from binary, ternary or discrete Gaussian distributions. We convert each LWE instance into a uSVP instance and run the BKZ2.0 algorithm to find an approximation to the shortest vector. When the attack is successful, we can deduce a bound on the Hermite factor achieved for the given blocksize. In practice we find that the attacks succeed for a smaller block size than would be expected based on current estimates.

Our approach is similar to the approach taken in earlier work [13] for estimating the approximation factor for the LLL algorithm. Laine and Lauter used synthetically generated LWE instances to study the approximation factor for LLL in dimension up to 800, without solving the Shortest Vector Problem. They found that the approximation factor for LLL is significantly better than expected in dimensions up to 800, which confirmed and extended what Gama and Nyugen [10] had found for LLL in dimension up to 200. But it was not clear how that would extend to other lattice reduction algorithms such as BKZ. The attacks presented in [13] also cover the case of secrets sampled from the uniform distribution, but in that case the attacks are only successful for very large moduli.

In this work, we find that the security levels for certain values of the modulus q and dimension n are smaller than predicted by the online Lattice Estimator [11]. This is due to the fact that the attacks succeed on these uSVP lattices for smaller blocksizes 30, 35, 40 and 45 than expected, for randomly generated LWE instances with small secret. The work of [6] attempts to quantify the loss of security when using binary secret by analyzing how much larger the lattice dimension n should be in order to achieve the same level of security. We use the same approach as [6] for attacking the LWE instances, but we run experiments to find the smallest blocksize necessary to break each LWE instance.

The tables of experimental data we present in Sect. 4 can be interpreted as follows: for each fixed blocksize $\beta$ and lattice dimension n, the bold line in the table represents the smallest value of $\log (q)$ for which the attacks succeed. There are several estimates in the literature predicting which blocksize will be necessary to achieve a sufficiently good approximation factor for the attack to succeed (the 2008 [10] and the 2016 [12] estimates). However our experiments on LWE instances with small secret (and small error) show that the approximation factor may be significantly better than predicted by the estimates for random lattices, and this translates into attacks succeeding with smaller blocksize than expected.

For example, in Table 1 for binary secret, observe that blocksize 30 is enough to break LWE instances with $n=120$ and $\log (q) = 12$ and error width $\sigma = 3.2$ in under 2 hours. Although machines are more powerful now, this can be compared with [6, Table 4] where the predicted security levels for $(n, q, \sigma ) = (128, 2^{12}, 22.6)$, depending on the Hermite factor $\delta$, range from $94-175$ bits of security for the standard attack to $34-59$ bits of security for their attack. Note that their $\delta \approx 1.008$ is closer to the delta we get for failed instances $\delta \approx 1.01$ than our average $\delta$ for successful cases $\delta \approx 0.99$.

We also observe a marked difference in blocksize required for a successful attack in comparison with the experiments presented in [7]. For example, in [7, Table 1], they validate the 2016 estimate in the case of $n = 110$, $\log (q) = 11$, where their attack requires blocksize 78. In our experiments attacking LWE instances with binary secrets, we successfully attack the same parameters with the same error width using blocksize 35 (see Table 2) with the dimension as predicted in the 2008 estimate. In this case the discrepancy is most likely due to the secret distribution: binary instead of uniform.

Our approach differs from the online Lattice Estimator [11] in the sense that we run BKZ2.0 on synthetically generated LWE instances in order to study the approximation factor and the required blocksize, whereas the Estimator uses models based on heuristic estimates to predict the blocksize and running time necessary. We find for example that LWE instances in dimension 200 with $\log (q) = 19$ and binary secret can be broken using BKZ2.0 with blocksize 30, whereas the Lattice Estimator predicts that blocksize 40 would be required, and a similar discrepancy with the Lattice Estimator predictions applies to most entries in our Tables.

We present separate tables for each possible choice of the secret distribution: binary, ternary, and Gaussian, for blocksizes 30, 35, 40 and 45, and lattice dimension ranging from $n=40$ to $n=200$. Note the difference in security levels between the tables for binary, ternary, and Gaussian secrets. For the same choice of blocksize $\beta$ and lattice dimension n, the attack succeeds for smaller values of $\log (q)$ for binary secret than for ternary secret and Gaussian secret (e.g., for $\beta =30$, $n=120$, $\log (q) = 12, 13, 14$ respectively).

We also generated synthetic instances of the TU Darmstadt LWE challenges [14] with binary, ternary and discrete gaussian secrets, and ran our same attack on these instances. Although our experiments only cover blocksizes 30, 35, 40 and 45, these blocksizes are already large enough to attack all the solved LWE challenges in the online tables, for secrets sampled from the binary and ternary secret distributions. We observed significantly lower running times for successful attacks on instances generated with the binary distribution for the secret vector. We observed that sampling the secret from the discrete Gaussian error distribution yielded greater security than the binary or ternary distributions for the same set of parameters, as the attack rarely succeeds. Our attacks run in a matter of minutes (under an hour) for blocksizes 30, 35, 40 and in a matter of hours for blocksize 45, for the range of parameters where the actual challenges have been solved.

2 Preliminaries

Let $\textbf{b}_1,\ldots , \textbf{b}_d \in \mathbb {R}^d$ be linearly independent vectors, and let $\textbf{B} =(\textbf{b}_1,\ldots ,\textbf{b}_d) \in \mathbb {R}^{d\times d}$ be the matrix whose columns are formed by them. The lattice generated by $\textbf{B}$ is

$$\begin{aligned} L(\textbf{B}) = \left\{ \textbf{Bx}\,:\,\textbf{x}\in \mathbb {Z}^d\right\} \,. \end{aligned}$$

(1)

The Shortest Vector Problem (SVP) asks to find the shortest nonzero vector in the lattice, whose norm is the first minimum:

$$\begin{aligned} \lambda _1(L(\textbf{B})) = \min _{\textbf{v}\in L(\textbf{B})\,,\textbf{v}\ne 0} ||\textbf{v}||\,, \end{aligned}$$

(2)

where we use $||\cdot ||$ to denote the $\ell _2$-norm. Similarly, the second minimum is

$$\begin{aligned} \lambda _2(L(\textbf{B})) = \min _{\textbf{v}_1,\textbf{v}_2\in L(\textbf{B})}\left\{ \max \{||\textbf{v}_1||, ||\textbf{v}_2||\}\,:\, \textbf{v}_1,\textbf{v}_2{\text { linearly independent}}\right\} \,. \end{aligned}$$

(3)

The unique Shortest Vector Problem (uSVP) with gap $\gamma$ is a variant of the SVP where $\lambda _2 \ge \gamma \cdot \lambda _1$, for some $\gamma \ge 1$. While random lattices do not satisfy this condition, in Sect. 3 we describe a procedure for embedding an instance of LWE with small secrets to an instance of uSVP.

In this work, we use the BKZ2.0 lattice reduction algorithm [9] to solve instances of the uSVP. Let $\textbf{b}_1^*,\ldots ,\textbf{b}_d^*$ denote the Gram-Schmidt orthogonalization of the basis vectors. For $1\le i \le d$, let $\pi _i$ be the orthogonal projection over $(\textbf{b}_1,\ldots ,\textbf{b}_{i-1})^{\perp }$. For $1\le j\le k\le d$, let $B_{[j,k]}$ be the local projected block $(\pi _j(\textbf{b}_j),\ldots , \pi _j(\textbf{b}_k))$, and let $L_{[j,k]}$ be the lattice spanned by $B_{[j,k]}$, of dimension $k-j+1$.

Definition 1

A basis $\textbf{b}_1,\ldots ,\textbf{b}_d$ is BKZ-reduced with blocksize $\beta \ge 2$ if it is LLL-reduced, and for each $1\le j\le d$, $||\textbf{b}_j^*|| = \lambda _1(L_{[j,k]})$ where $k=\min (j+\beta -1,d)$.

The BKZ algorithm works by iteratively reducing each local block $B_{[j,k]}$ of size up to $\beta$. Each block is first LLL-reduced, before being enumerated to find a vector that is the shortest in the projected lattice $L_{[j,k]}$. The BKZ2.0 algorithm [9] improves on BKZ by modifying the enumeration routine, incorporating the sound pruning technique by [15].

The volume of a lattice is ${{\,\textrm{Vol}\,}}(L(\textbf{B})) = |\det (\textbf{B})|$. We use the root Hermite factor to measure the quality of the BKZ-reduced basis.

Definition 2

The root Hermite factor $\delta$ of a basis $\{\textbf{b}_1,\dots ,\textbf{b}_d\}$ is defined by

$$\begin{aligned} ||\textbf{b}_1|| = \delta ^d \cdot {{\,\textrm{Vol}\,}}(L(\textbf{B}))^{1/d}\,. \end{aligned}$$

(4)

For BKZ with block size $\beta$, Chen [16] gives the following estimate for $\delta$ which only depends on $\beta$.

$$\begin{aligned} \delta (\beta ) \approx \left( \frac{\beta }{2\pi e} (\pi \beta )^{1/\beta }\right) ^{\frac{1}{2(\beta -1)}}\,. \end{aligned}$$

(5)

For a large $\beta$, we can approximate this by $\beta ^{1/2\beta }$.

3 Reduction from LWE to uSVP

In this work, we study the uSVP attack on LWE, which is currently the most effective attack if the LWE secret has small entries [6,7,8]. There are two known estimates for the conditions under which uSVP can be solved by lattice reduction, which are known as the 2008 estimate [10] and the 2016 estimate [12]. In this section, we describe the reduction from LWE to uSVP, which proceeds by first reducing LWE to BDD and then reducing BDD to uSVP. We also describe the 2008 and 2016 estimates, and calculate the optimal parameters for the uSVP attack under these estimates, as well as the predicted values of the Hermite factor.

3.1 The LWE Problem

We first define the search variant of the LWE problem.

Definition 3

Let $n\ge 1$, $q\ge 2$ be a prime modulus and let $D_\sigma$ be a discrete gaussian distribution over $\mathbb {Z}$ with standard deviation $\sigma$. Let $A\in \mathbb {Z}_q^{m\times n}$ be a matrix with entries uniformly sampled from $\mathbb {Z}_q$, let $\textbf{s}\in \mathbb {Z}_q^n$ be a secret vector, and let $\textbf{e}\in \mathbb {Z}_q^m$ be an error vector with entries sampled independently from $D_\sigma$. Let $\textbf{b}=\textbf{A}\textbf{s} + \textbf{e} \pmod {q}$. The goal of the LWE problem is to find $\textbf{s}$, given $(\textbf{A},\textbf{b})$.

We consider the following distributions for the secret:

• Binary: Secret has entries sampled uniformly at random from $\{0,1\}$.

• Ternary: Secret has entries sampled uniformly at random from $\{0,\pm 1\}$.

• Gaussian: Secret has entries sampled from the same discrete gaussian distribution as the error.

3.2 Reduction from LWE to BDD

Assuming that the secret has a small norm, we can transform the LWE problem into the Bounded Distance Decoding (BDD) problem. Specifically, given a lattice $L(\textbf{B})$ and a target vector $\textbf{t}$, such that the distance of $\textbf{t}$ from $L(\textbf{B})$ is bounded by a factor of $\lambda _1$, the BDD problem asks to find a lattice vector $\textbf{v}\in L(\textbf{B})$ close to $\textbf{t}$. Consider the lattice generated by

$$\begin{aligned} \textbf{B}_0 = \begin{pmatrix} \textbf{I}_n &{} \textbf{0} \\ \textbf{A} &{} q\cdot \textbf{I}_m \end{pmatrix}\,. \end{aligned}$$

(6)

Since $\textbf{As} +\textbf{e}= \textbf{b} \pmod {q}$, we can write $\textbf{b}= \textbf{As}+\textbf{e}+q\cdot \textbf{c}$ for some $\textbf{c}\in \mathbb {Z}^m$. Hence the lattice contains the vector $\textbf{B}_0\begin{pmatrix} \textbf{s} \\ \textbf{c}\end{pmatrix} = \begin{pmatrix} \textbf{s} \\ \textbf{As} + q\textbf{c}\end{pmatrix} = \begin{pmatrix} \textbf{s} \\ \textbf{b}-\textbf{e}\end{pmatrix}$. Thus if we solve the BDD problem in the lattice generated by $\textbf{B}_0$, with respect to the target point $\textbf{t}=\begin{pmatrix} \textbf{0} \\ \textbf{b}\end{pmatrix}$, then we obtain $\begin{pmatrix} \textbf{s} \\ -\textbf{e} \end{pmatrix}$, allowing us to recover the secret.

3.3 Reduction from BDD to uSVP

We can reduce the BDD problem to an instance of uSVP using Kannan’s embedding technique [17]. Consider the basis matrix obtained by adding one row and column to (6):

$$\begin{aligned} \textbf{B}_1 = \begin{pmatrix} \textbf{B}_0 &{} \textbf{t} \\ \textbf{0} &{} 1 \end{pmatrix} = \begin{pmatrix} \textbf{I}_n &{} \textbf{0} &{} \textbf{0} \\ \textbf{A} &{} q\cdot \textbf{I}_m &{} \textbf{b} \\ 0 &{} 0 &{} 1 \end{pmatrix}\,. \end{aligned}$$

(7)

The lattice generated by the columns of $\textbf{B}_1$ contains the unique shortest vector

$$\begin{aligned} \textbf{B}_1 \begin{pmatrix} \textbf{s} \\ \textbf{c} \\ -1\end{pmatrix} = \begin{pmatrix} \textbf{B}_0\begin{pmatrix} \textbf{s} \\ \textbf{c}\end{pmatrix}-\textbf{t} \\ -1 \end{pmatrix} = \begin{pmatrix} \textbf{s} \\ -\textbf{e} \\ -1 \end{pmatrix}\,. \end{aligned}$$

(8)

Assuming that the gap between $\lambda _1$ and $\lambda _2$ in this lattice is sufficiently large, we can solve for the unique shortest vector using lattice reduction algorithms such as BKZ2.0. Following [6], we further optimize this by balancing the lengths of the secret and error vectors, scaling the secret by some constant factor $\omega$. If the secret is sampled from the same discrete gaussian distribution as the error, then we set $\omega =1$. For the binary or ternary secret distributions, consider the matrix

$$\begin{aligned} \textbf{B} = \begin{pmatrix} \omega \cdot \textbf{I}_n &{} \textbf{0} &{} \textbf{0} \\ \textbf{A} &{} q\cdot \textbf{I}_m &{} \textbf{b} \\ 0 &{} 0 &{} 1 \end{pmatrix}\,. \end{aligned}$$

(9)

The lattice $L(\textbf{B})$ generated by (9) has dimension

$$\begin{aligned} d = n+m+1 \end{aligned}$$

(10)

and contains a short vector

$$\begin{aligned} \textbf{B} \begin{pmatrix} \textbf{s} \\ \textbf{c} \\ -1\end{pmatrix} = \begin{pmatrix} \omega \cdot \textbf{s} \\ \textbf{As}+q\textbf{c}-\textbf{b} \\ -1\end{pmatrix} = \begin{pmatrix} \omega \cdot \textbf{s} \\ -\textbf{e} \\ -1 \end{pmatrix}\,. \end{aligned}$$

(11)

Since this is the shortest vector of this lattice, we approximate the first minimum of the lattice by its expected norm:

$$\begin{aligned} \lambda _1 = \sqrt{\omega ^2\cdot ||\textbf{s}||^2 + ||\textbf{e}||^2 +1} \approx \sqrt{\omega ^2 \cdot h + m\sigma ^2 + 1}\,, \end{aligned}$$

(12)

where $\sigma$ is the standard deviation of the discrete Gaussian distribution and h is the expected value of $||\textbf{s}||^2$. We have $h=\frac{n}{2}$ for the binary distribution and $h=\frac{2}{3}n$ for the ternary distribution.

We estimate the second minimum $\lambda _2$ to be the same as the first minimum of a random lattice with the same dimension using the Gaussian Heuristic. Since the lattice is q-ary, it also contains vectors of norm q, so we have

$$\begin{aligned} \lambda _2\approx \min \left\{ q, \sqrt{\frac{d}{2\pi e}} \omega ^{n/d} q^{m/d}\right\} \,. \end{aligned}$$

(13)

We can solve the uSVP using lattice reduction algorithms if $\lambda _2$ is sufficiently larger than $\lambda _1$. We choose $\omega$ to maximize the ratio $\frac{\lambda _2}{\lambda _1}$ as follows. First we write

$$\begin{aligned} \gamma = \frac{\lambda _2}{\lambda _1} \approx \frac{\min \left\{ q, \sqrt{\frac{d}{2\pi e}} \omega ^{n/d} q^{m/d}\right\} }{\sqrt{\omega ^2 h + m\sigma ^2}}\,. \end{aligned}$$

(14)

We choose the parameters to optimize the second term in the minimum, since the Gaussian Heuristic would asymptotically be smaller than q. Differentiating the expression in (14) with respect to $\omega$ and setting the result to zero, we get

$$\begin{aligned} \omega ^2 = \frac{nm}{h(d-n)} \sigma ^2 \approx \frac{n}{h} \sigma ^2\,. \end{aligned}$$

(15)

This gives us $\omega = \sqrt{2}\sigma$ for the binary distribution and $\omega =\sqrt{\frac{3}{2}}\sigma$ for the ternary distribution. Substituting (15) into (12), we get

$$\begin{aligned} \lambda _1 \approx \sqrt{d}\sigma \,. \end{aligned}$$

(16)

This also holds for the case where the secret is sampled from the same discrete gaussian distribution as the error. Notably, the shortest vector has the same $\ell _2$-norm regardless of the secret distribution, whereas the $\ell _1$-norm differs. Thus

$$\begin{aligned} \gamma = \frac{\min \left\{ q, \sqrt{\frac{d}{2\pi e}} \omega ^{n/d} q^{m/d}\right\} }{\sqrt{d}\sigma }\,. \end{aligned}$$

(17)

Remark 1

Another commonly used secret distribution is the uniform distribution on $\mathbb {Z}_q$, where the entries of the secret are sampled uniformly at random from $\{0,1,\ldots ,q-1\}$. Since the secret does not have a small norm, the uSVP attack would require a much larger q to succeed. To balance the norms of the secret and error vectors, we have to choose the scaling factor to be $\omega \approx \frac{\sqrt{3}}{q}\sigma$. However, the Gaussian heuristic would then be greater than q, and so $\lambda _2 = q$ from (13). For the uSVP attack to be effective, $\lambda _2$ would have to be much greater than $\lambda _1$, which means that q would have to be much larger than for the other secret distributions.

There are two known ways for estimating the conditions under which uSVP can be solved using lattice reduction, which are called the 2008 estimate and the 2016 estimate in the literature. We study each of these in turn.

3.4 2008 Estimate

From experiments by Gama and Nguyen [10], they claimed that the shortest vector can be recovered if

$$\begin{aligned} \gamma = \frac{\lambda _2}{\lambda _1} \ge \delta ^d\,, \end{aligned}$$

(18)

where $\delta$ is the root Hermite factor of the lattice reduction algorithm, up to a multiplicative constant. In what follows, we will compute the estimate of $\delta$ based on the heuristic in (18) for our setting. We will fix n and q, while choosing the lattice dimension d to maximize $\gamma$. First we write

$$\begin{aligned} \gamma \approx \frac{\sqrt{\frac{d}{2\pi e}} \omega ^{n/d} q^{m/d}}{\sqrt{d} \sigma } = \frac{1}{\sqrt{2\pi e}} \frac{\omega ^{n/d} q^{m/d}}{\sigma } \approx \frac{1}{\sqrt{2\pi e}} \left( \frac{q}{\omega }\right) ^{-n/d} \left( \frac{q}{\sigma }\right) \ge \delta ^d\,. \end{aligned}$$

(19)

We choose d to maximize the ratio in (19), by setting

$$\begin{aligned} d = \sqrt{\frac{n\log \left( \frac{q}{\omega }\right) }{\log \delta }}\,. \end{aligned}$$

(20)

We solve for the largest possible value of $\delta$ as a function of $n, q, \omega , \sigma$. First, we assume equality in (19) and take logarithms on both sides:

$$\begin{aligned} \log \left( \frac{q}{\sqrt{2\pi e} \sigma }\right) -\frac{n}{d} \log \left( \frac{q}{\omega }\right) = d\log \delta \,. \end{aligned}$$

(21)

Substituting (20) and rearranging, we get the 2008 estimate for $\delta$:

$$\begin{aligned} \log \delta _{2008} = \frac{\log ^2\left( \frac{q}{\sqrt{2\pi e} \sigma }\right) }{4n \log \left( \frac{q}{\omega }\right) }\,. \end{aligned}$$

(22)

We substitute (22) into (20) to obtain

$$\begin{aligned} d_{2008} = \frac{2n\log \left( \frac{q}{\omega }\right) }{\log \left( \frac{q}{\sqrt{2\pi e}\sigma }\right) }\,. \end{aligned}$$

(23)

This is the lattice dimension that we use in our experiments to compute $\delta _{2008}$. We observe that $\delta _{2008}$ increases with q. For fixed $n,\beta$, we experimentally find the smallest q such that the attack succeeds. Substituting the parameters into (22), we then obtain a heuristic estimate of $\delta _{2008}$, which we compare with the actual value of $\delta$ from (4).

We remark that (22) only holds for large q, such that $\lambda _2$ is given by the Gaussian Heuristic. If $\lambda _2=q$, then the same analysis as above gives

$$\begin{aligned} \log \delta _{2008} = \frac{1}{d} \log \left( \frac{q}{\sqrt{d}\sigma }\right) \,. \end{aligned}$$

(24)

We also compare $\delta _{2008}$ with the actual value of $\delta$ that we expect from the experiments, using the definition in (4) and assuming that the shortest vector is successfully recovered, and that $\lambda _2$ is equal to the Gaussian Heuristic. We have

$$\begin{aligned} \delta _{2008}^d = \frac{\lambda _2}{\lambda _1} = \sqrt{\frac{d}{2\pi e}} \delta ^{-d}\,. \end{aligned}$$

(25)

This gives us the relation between the expected experimental $\delta$ and $\delta _{2008}$.

$$\begin{aligned} \delta = \frac{1}{\delta _{2008}} \left( \frac{d}{2\pi e}\right) ^{1/2d}\,. \end{aligned}$$

(26)

Hence we expect $\delta$ to trend differently from $\delta _{2008}$.

Table 1 Binary secrets

Table 2 Binary secrets (continued)

Table 3 Ternary secrets

Table 4 Ternary secrets (continued)

Table 5 Gaussian secrets

Table 6 Gaussian secrets (continued)

3.5 2016 Estimate

The 2016 estimate is given in the New Hope key exchange paper [12]. The authors consider the evolution of the Gram-Schmidt coefficients of the unique shortest vector in the BKZ tours, assuming that the Geometric Series Assumption [18] holds. This says that the norms of the Gram-Schmidt vectors after lattice reduction satisfy

$$\begin{aligned} ||\textbf{b}_i^*|| \approx \delta ^{d-2i+2} \cdot \text {Vol}(L(\textbf{B}))^{1/d}\,. \end{aligned}$$

(27)

The reasoning in [12] is that, if the projection of the unique shortest vector onto the space spanned by the last $\beta$ Gram-Schmidt vectors is shorter than $\textbf{b}_{d-\beta +1}^*$, then the SVP oracle in BKZ would be able to find it when called on the last block of size $\beta$. The success condition is thus given by

$$\begin{aligned} \sqrt{\frac{\beta }{d}} \lambda _1 \le ||\textbf{b}_{d-\beta +1}^*||\,. \end{aligned}$$

(28)

Based on these heuristics, we compute the estimated value of $\delta$ in our setting. Substituting $\lambda _1 \approx \sqrt{d}\sigma$ and (27), we get

$$\begin{aligned} \sqrt{\beta } \sigma \le \delta ^{2\beta -d} \cdot \text {Vol}(L(\textbf{B}))^{1/d} = \delta ^{2\beta -d}\omega ^{n/d} q^{m/d} \,. \end{aligned}$$

(29)

If we choose d to optimize this ratio, we obtain (20) again. Substituting (20) into (29) and taking logarithms, we get a quadratic equation in $\sqrt{\log \delta }$:

$$\begin{aligned} 2\beta \log \delta - 2\sqrt{n\log \left( \frac{q}{\omega }\right) \log \delta } + \log \left( \frac{q}{\sqrt{\beta }\sigma }\right) = 0\,. \end{aligned}$$

(30)

We solve this equation to get the 2016 estimate for $\delta$:

$$\begin{aligned} \log \delta _{2016} = \frac{n\log \left( \frac{q}{\omega }\right) }{4\beta ^2} \left( 1 - \sqrt{1- \frac{2\beta \log \left( \frac{q}{\sqrt{\beta }\sigma }\right) }{n\log \left( \frac{q}{\omega }\right) }}\right) ^2\,, \end{aligned}$$

(31)

If the value inside the squareroot is negative, then we take $\log \delta _{2016}=\frac{n\log \left( \frac{q}{\omega }\right) }{4\beta ^2}$. We obtain the lattice dimension $d_{2016}$ by substituting (31) into (20). For large n, (31) is asymptotically

$$\begin{aligned} \log \delta _{2016} \approx \frac{\log ^2\left( \frac{q}{\sqrt{\beta }\sigma }\right) }{4n\log \left( \frac{q}{\omega }\right) }\,. \end{aligned}$$

(32)

We observe that (32) is similar to (22) except for the denominator of q in the numerator. The experiments in [7, 8] suggest that the 2016 estimate is more consistent with experiments than the 2008 estimate. In this paper, we will experimentally compare$\delta _{2008}$ and $\delta _{2016}$ with actual values of $\delta$.

We compare $\delta _{2016}$ with the expected experimental value of $\delta$, using the definition in (4) and assuming that the shortest vector is successfully recovered. We have

$$\begin{aligned} \delta _{2016}^{2\beta -d} = \sqrt{\frac{\beta }{d}} \frac{\lambda _1}{{{\,\textrm{Vol}\,}}(L(\textbf{B}))^{1/d}} = \sqrt{\frac{\beta }{d}} \delta ^d\,. \end{aligned}$$

(33)

Hence we have the relation

$$\begin{aligned} \delta = \delta _{2016}^{2\beta /d-1} \left( \frac{d}{\beta }\right) ^{1/2d}\,. \end{aligned}$$

(34)

We observe that $\delta$ trends differently from $\delta _{2016}$, similarly to (26) for $\delta _{2008}$.

Fig. 1

Comparing estimates (blue) for $\delta$ with observed $\delta$s from successful (green) and failed (red) attacks for binary secrets and block sizes $\beta =30,35,40,45$. The black line is Chen’s estimate (Color figure online)

Fig. 2

Plots of $\delta$ for ternary secrets and $\beta =30,35,40,45$

Fig. 3

Plots of $\delta$ for gaussian secrets and $\beta =30,35,40,45$

4 Experiments

4.1 Setup

We perform our experiments using a 2.4 GHz Intel Xeon E5-2673 v4 processor, with 48 virtual CPUs and 192 GB of RAM. We generate random instances of LWE, and convert them into instances of uSVP via (9). We sample the errors from a discrete gaussian distribution with standard deviation $\sigma =3.2$, using the discrete gaussian sampler in [19], and we sample secrets uniformly from the binary, ternary and discrete gaussian distributions. To recover the shortest vector, we use the BKZ2.0 algorithm implemented in fplll [20], with the bkzautoabort option, and with blocksizes $\beta =30,35,40,45$. The bkzautoabort option causes the algorithm to terminate when the norms of the Gram-Schmidt vectors stop changing.

For $\beta =30$, we run experiments for n from 40 to 200 in steps of 10. For $\beta =35,40$, we choose n from 40 to 150, and for $\beta =45$, we choose n from 40 to 100. We use a smaller range of values of n for higher $\beta$, since the running time of BKZ2.0 grows exponentially with $\beta$, so it is infeasible to run the experiments for higher $\beta$ with large n. For each set of parameters, we vary $\log q$ to determine the smallest value of $\log q$ such that BKZ2.0 succeeds in recovering the secret. We perform 10 trials per set of parameters, to account for the randomness in sampling the lattices.

Fig. 4

Plots of running times in minutes. The dots and crosses represent attacks run with the dimensions calculated from the 2008 and 2016 estimates respectively. The blue, red, green and cyan represent blocksizes 30, 35, 40, 45 respectively

The data are in Tables 1 to 6, where the rows in boldface contain the data for the smallest value of $\log (q)$ where the attack succeeds. For each set of parameters, we compute the values of $\delta$ using the estimates in (22) and (31), which we tabulate as $\delta _{2008}$ and $\delta _{2016}$ respectively. Based on the estimates, we also compute the optimal values of the lattice dimensions from (20), which we tabulate as $d_{2008}$ and $d_{2016}$. Since these dimensions are different, we conducted two sets of experiments for each set of parameters, where one set has lattice dimension $d_{2008}$ and the other has dimension $d_{2016}$. We thus divide Tables 1 to 6 into two parts, where the left parts indicate the experiments for the 2008 estimate and the right for the 2016 estimate.

For each instance, we compute the actual values of $\delta$ using the definition in (4). We split the instances into cases where BKZ2.0 succeeds in recovering the secret, and cases where it fails, and we compute the average value of $\delta$ in each scenario. We tabulate these experimental values of $\delta$ under the columns labeled “Average successful $\delta$” and “Average failed $\delta$”.

Fig. 5

TU Darmstadt LWE challenges for binary secrets. Each cell is colored based on the number of successful trials, where the colors red, orange, yellow and green indicate that the number of successful trials is 3, 2, 1 and 0 respectively. The bottom diagonal of each divided cell indicates the 2008 estimate, while the top diagonal indicates the 2016 estimate

Fig. 6

TU Darmstadt LWE challenges for ternary secrets

Fig. 7

TU Darmstadt LWE challenges for gaussian secrets

In Figs. 1, 2, 3, we plot the values of $\delta$ for various blocksizes, $\beta$, against the lattice dimension for the binary, ternary and gaussian secret distributions respectively, with separate graphs for each blocksize. In each graph, we plot the values of the 2008 and 2016 estimates for $\delta$ against the dimension of the lattice, using blue dots for 2008 and blue crosses for 2016 predictions. For comparison, we plot Chen’s estimate (5) which only depends on the blocksize, using a black line. In green and red, we plot the average observed values of $\delta$ for the instances where BKZ2.0 succeeds and fails. The green and red represent the successful and failed instances respectively. The dots and crosses represent attacks run with the dimensions calculated from the 2008 and 2016 estimates respectively. The data for the successful cases is obtained from the smallest value of $\log (q)$ where the attack succeeds, which are the rows in boldface in the tables, while the data for the failed cases is obtained from the largest value of $\log (q)$ where the attack does not succeed, which are the rows directly above those in boldface.

Due to the experimental nature of our work, we could only produce data for lattices of small dimensions, as the running time of BKZ2.0 grows exponentially with the parameters. We plot the average running times of BKZ2.0 for each set of parameters in Fig. 4. In the plots, the dots and crosses represent attacks run with the dimensions calculated from the 2008 and 2016 estimates respectively. The blue, red, green and cyan represent blocksizes 30, 35, 40, 45 respectively.

4.2 Results

The main observation is that the experimental values of $\delta$ for successful instances decrease as the lattice dimension increases, whereas the 2008 and 2016 estimates show increasing trends which seem to approach Chen’s estimate.

We observe that the experimental values of $\delta$ for failed instances closely follow the 2008 and 2016 estimates. The values of $\delta$ for failed instances are higher than for successful instances, which is expected since BKZ2.0 finds shorter vectors for the latter. Moreover, the values of $\delta$ for the successful instances decrease as the lattice dimension increases. In the cases where BKZ2.0 fails to recover the unique shortest vector, it recovers instead a vector with length close to the Gaussian Heuristic, and so the algorithm behaves like it would on a random lattice of the same dimension. In these cases, the experimental values of $\delta$ closely follow the 2008 and 2016 estimates. This indicates that the estimates accurately capture the behavior of BKZ2.0 on random lattices, but not on successful instances of uSVP.

We also observe that the success rates for the 2008 and 2016 estimates are comparable, although the 2008 estimate generally predicts higher lattice dimensions which lead to longer running times. The 2008 estimate also generally predicts higher values of $\delta$ than the 2016 estimate, for fixed lattice dimensions.

Additionally, for fixed n and $\beta$, the values of $\log q$ and d required to recover the secret is significantly higher for the cases where the secret is sampled from the discrete gaussian distribution, as compared to the binary and ternary distributions. The values for the binary and ternary distributions are comparable, though slightly higher for the ternary distribution. This indicates that gaussian secrets yield greater security levels, and would be recommended over binary or ternary secrets in practical applications. For all three secret distributions, the shortest vector has the same $\ell _2$-norm, whereas the $\ell _1$-norm is highest for the gaussian distribution, followed by the ternary and binary distributions. This indicates a trend of higher security level with increasing $\ell _1$-norm, and it would be interesting to study this more systematically.

It is infeasible to run our experiments for $\beta \ge 50$ and $n> 100$ within reasonable times. For comparison, with blocksize 50, it takes about 19 hours to run the experiment with binary secrets for $n=40$ and $\log q=6$, as compared to an hour for blocksize 45 with the same parameters. It would be desirable to conduct longer experimental studies with higher blocksizes and dimensions, to simulate the parameters used in practical cryptosystems. Nevertheless, our work represents a first step towards a systematic experimental understanding of the success characteristics of BKZ2.0 on uSVP lattices, alongside with the follow-up work in [21,22,23].

4.3 TU Darmstadt LWE Challenge

Using the same experimental setup, we generate instances of the TU Darmstadt LWE challenges [14]. In the actual challenges, the secrets are sampled from uniform distributions on $\mathbb {Z}_q$; in our experiments we use instead the binary, ternary and gaussian secret distributions.

In the challenges, the discrete Gaussian error distributions have varying standard deviations $\sigma = \alpha q$, where $\alpha$ is a parameter. For each challenge, the parameters $n,q,\alpha$ are fixed. We generate instances with binary, ternary and Gaussian secrets, and we run the uSVP attack using the BKZ2.0 algorithm with blocksizes $\beta =30,35,40,45$. Due to resource limitations, we run only 3 trials for each set of parameters.

The data from our experiments are in Figs. 5, 6, 7. In each figure, we plot a grid for each blocksize, where the columns are indexed by n and the rows by $\alpha$. Each cell in the grid is colored based on the number of successful trials, where the colors red, orange, yellow and green indicate that the number of successful trials is 3, 2, 1 and 0 respectively. Moreover, the bottom diagonal of each divided cell indicates the 2008 estimate, while the top diagonal indicates the 2016 estimate.

We observe that there is a much higher success rate in solving the challenges for the binary and ternary secret distributions, as compared to the gaussian distribution. This indicates that gaussian secret distributions are more secure for practical applications. Moreover, our running times for the successful instances are significantly less than the records in the actual challenges, which use secrets from uniform distributions. Furthermore, we also observe that we are already able to attack all the solved LWE challenges in the online tables, for secrets sampled from the binary or ternary secret distributions. This indicates that uniform secrets offer much higher security than the secret distributions that we consider, and it would be promising to study the case of uniform secrets in our experimental framework, as a potential follow-up to this work.