# Solving SIS in any norm via Gaussian sampling

Amaury Pouly, Yixin Shen

<figure><img src="image_1.png" /></figure>

## To cite this version:

Amaury Pouly, Yixin Shen. Solving SIS in any norm via Gaussian sampling. 2026. hal-05504851

HAL Id: hal-05504851

https://hal.science/hal-05504851v1

Preprint submitted on 11 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Solving SIS in any norm via Gaussian sampling

Amaury Pouly¹[0000-0002-2549-951X] and Yixin Shen²[0000-0002-8657-9337]

¹ Centre National de la Recherche Scientifique (CNRS)
amaury.pouly@cnrs.fr

² Univ Rennes, Inria, CNRS, IRISA, Rennes
yixin.shen@inria.fr

**Abstract.** The short integer solution (SIS) problem is an important problem in lattice-based cryptography. In this paper, we construct a natural and simple algorithm that allows us to solve the problem for any norm in the case where the norm bound $\ell$ is smaller than half the modulus $q$. The algorithm consists in using a discrete gaussian sampler on the SIS $q$-ary lattice to sample lattice vectors, and requires to estimate the probably that the sampled vector is non-zero and falls into a ball of radius $\ell$ in the given norm. For the latter, we improve upon previous analysis of random $q$-ary lattice by obtaining tight bounds on the expected value and variance of the Gaussian mass of the entire lattice and of an $\ell_p$-norm ball, for any $p \in (0, \infty]$. These bounds require new technical results on the discrete Gaussian, but also rely on a conjecture which we have extensively verified. Aside from the conjecture, the remaining part of the algorithm is provably correct. When instantiated with a Markov chain Monte Carlo (MCMC)-based discrete Gaussian sampler, the complexity of the algorithm can be estimated precisely. Although our algorithm does not break Dilithium, it is at least 50 bits faster than the recent algorithm of Ducas, Engelberts and Loyer [15] in Crypto 2025 for all security levels.

**Keywords:** Random Lattices, Smoothing Parameter, Short Integer Solution

## 1 Introduction

The Short Integer Solution problem (SIS) is a foundational computational problem in lattice-based cryptography. It asks to find a short non-zero lattice vector in a randomly generated $q$-ary lattice of a specific form, with respect to a certain norm. The $\ell_2$-norm case was first introduced by Ajtai [4] and enjoys worst case to average case reduction for certain parameter regimes. It has numerous applications in cryptography, including the construction of collision-resistant hash functions, digital signatures, identification schemes, and more recently, zero-knowledge proofs.

In practice, designers of crytographic schemes are tempted to use SIS instances that are outside the asymptotic coverage of the worst case to average case reduction regime in order to gain efficiency. In many cases, they also consider variants of the problem. This is for example the case of the recently NIST
standardized signature scheme Dilithium [16], whose harness relies on the hardness of the SIS problem under the $l_\infty$-norm.

Suprisingly, there are not many studies about the concrete complexity for solving the problem in both $l_2$-norm and $l_\infty$-norm cases. This is in contrast to other lattice problems such as Learning with Errors (LWE), for which the well-known Lattice Estimator [6] is widely used in the community to estimate its complexity***.

*Contributions* In this paper, we propose to remediate to the situation by constructing a natural and simple algorithm that allows us to solve the SIS problem for any norm, in the case where the norm bound $\ell$ is smaller than half the modulus $q$. Our algorithm is provably correct under a mathematical conjecture that we verified experimentally. The complexity of the algorithm can be estimated precisely (Theorem 4) and we also give asymptotic versions of the complexity for $p=2$ (Theorem 6) and $p = \infty$ (Theorem 5) which are considerably simpler.

In a nutshell, our algorithm can be explained as follows: we use a discrete gaussian sampler on the SIS $q$-ary lattice to sample lattice vectors, and we estimate the probability that the sampled vector is non-zero and falls into a ball of radius $\ell$ in the given norm. If this is the case, then the sampled vector will be a solution of the SIS problem. More concretely, we use the Markov chain Monte Carlo (MCMC)-based discrete Gaussian sampler proposed by Wang and Ling [36] whose complexity was analysed in [31] when the basis of the lattice is obtained via the BKZ algorithm, and under the Geometric Series Assumption (GSA).

A key point in the analysis of the algorithm is to estimate the probability that a discrete Gaussian sample falls into a ball (Corollary 3). We improve upon previous analysis of random $q$-ary lattice by obtaining tight bounds on the expected value and variance of the Gaussian mass of an $l_p$-norm of a ball, for any $p \in (0, \infty]$ (Lemma 9). These bounds require new technical results on the discrete Gaussian, but also rely on a conjecture which we have extensively verified. We also prove similar bounds for the mass of the entire lattice (Lemma 7 and Corollary 1). In particular, this allows us to derive a probabilistic bound on the smoothing parameter of a random $q$-ary lattice which may be of independent interest (Corollary 2). Although our bounds on the variance of the Gaussian mass are essentially optimal (Remark 5 and Remark 8), this does not translate into an optimal bound for the smoothing parameter for very small values of $\varepsilon$ (Remark 7). This suggest that more work is needed to better understand the smoothing parameter of random $q$-ary lattices, for example by computing the higher moments of the Gaussian mass.

We apply our algorithm to the parameters of Dilithium and compared our complexity to the one in [15] that was published this year at Crypto. Although

<footnote>*** It is also possible to estimate the cost of the SIS problem with the Lattice Estimator. However, the proposed methods are very heuristic and don't seem to be widely accepted by the community as far as we understand.</footnote>
our algorithm does not break Dilithium, it is at least 50 bits faster than the algorithm in [15] for all security levels.

*Organization of the paper* Section 2 contains preliminary technical results. Section 3 contains some new technical results on the discrete Gaussian. Section 4 gives some probabilistic bounds on the Gaussian mass and smoothing parameter of random q-ary lattices. Section 5 describes and analyses our algorithm for the SIS problem.

## 2 Preliminaries

We denote vectors and matrices in bold case. We denote by $\mathbf{x}^T$ the transpose of the (column) vector $\mathbf{x}$, which is therefore a row vector. For any vector $\mathbf{x} \in \mathbb{R}^n$, we denote by $\|\mathbf{x}\|$ its Euclidean norm and by $\|\mathbf{x}\|_p$ its $p$-norm for any $p \in [1, \infty]$. For any$^\dagger p \in [1, \infty]$, $n \ge 1$ and $r > 0$, we denote by $B_n^p$ the open $p$-norm ball of radius 1 in $\mathbb{R}^n$, and by $B_n^p(r)$ the open $p$-norm ball of radius $r$. Finally, we let $B_n^{p,\mathbb{Z}}(\ell) = B_n^p(\ell) \cap \mathbb{Z}^n$. For $p = 2$, we omit the subscript and just write $B_n$, $B_n(r)$ and $B_n^{\mathbb{Z}}(r)$.

For any finite set $X$, we denote by $\mathcal{U}(X)$ the uniform distribution over $X$. As usual, if $P$ and $Q$ are two probability distributions over $X$ and $Y$ respectively, we denote by $PQ$ the product distribution over $X \times Y$. For any two distributions $P$ and $Q$, we denote by $d_{TV}(P, Q)$ the statistical distance (or total variation distance) between $P$ and $Q$. We say that two distributions $P$ and $Q$ are $\varepsilon$-close if $d_{TV}(P, Q) \le \varepsilon$.

We denote by erf the error function, defined for any $x \ge 0$ by $\text{erf}(x) = \frac{2}{\sqrt{\pi}} \int_0^x e^{-t^2} dt$.

We will use the standard fact that for any $d \in \mathbb{N}$ and $r \ge 0$,

$$ \text{vol}(B_d(r - \frac{1}{2}\sqrt{d})) \le |\{\mathbf{x} \in \mathbb{Z}^d : \|\mathbf{x}\| \le r\}| \le \text{vol}(B_d(r + \frac{1}{2}\sqrt{d})) \quad (1) $$

where the first inequality holds when $r \ge \frac{1}{2}\sqrt{d}$. Recall that this can be obtained by placing a unit open hypercube $(-\frac{1}{2}, \frac{1}{2})^d$ centered on each point of the set on the left-hand side and arguing that those disjoint hypercubes all belong to the ball $B_d(r + \frac{1}{2}\sqrt{d})$ and contain the ball $B_d(r - \frac{1}{2}\sqrt{d})$. These estimates are asymptotically tight when $r = \omega(\sqrt{d})$.

### 2.1 Lattices

A lattice $\mathcal{L}$ is a discrete subgroup of $\mathbb{R}^d$. Equivalently it is the set

$$ \mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_n) = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i : x_i \in \mathbb{Z} \right\} $$

<footnote>$^\dagger$ Using a slightly abuse of notation, we mean either a real $p \ge 1$ or $p = \infty$.</footnote>
of all integer combinations of $n$ linearly independent vectors $\mathbf{b}_1, \dots, \mathbf{b}_n \in \mathbb{R}^d$. Such $\mathbf{b}_i$'s form a basis of $\mathcal{L}$ and are usually collected in matrix form $[\mathbf{b}_1 \cdots \mathbf{b}_n]$. The lattice $\mathcal{L}$ is said to be full-rank if $n = d$. We denote by $\lambda_1(\mathcal{L})$ the first minimum of $\mathcal{L}$, defined as the length of a shortest non-zero vector of $\mathcal{L}$. We denote by vol($\mathcal{L}$) the volume (or determinant) of $\mathcal{L}$. For a full-rank lattice $\mathcal{L}$, vol($\mathcal{L}$) = det($\mathbf{A}$) for any basis $\mathbf{A}$ of $\mathcal{L}$. Recall that for two lattices $\mathcal{L} \subseteq \mathcal{L}'$, the index of $\mathcal{L}$ in $\mathcal{L}'$ is the size of the quotient $\mathcal{L}' / \mathcal{L}$.

For a rank $n$ lattice $\mathcal{L} \subset \mathbb{R}^d$, the dual lattice, denoted $\hat{\mathcal{L}}$, is defined as the set of all points in $\mathrm{span}(\mathcal{L})$ that have integer inner products with all lattice points,

$$ \hat{\mathcal{L}} = \{ \mathbf{w} \in \mathrm{span}(\mathcal{L}) : \forall \mathbf{y} \in \mathcal{L}, \langle \mathbf{w}, \mathbf{y} \rangle \in \mathbb{Z} \}. $$

Similarly, for a lattice basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$, we define the dual basis $\mathbf{B}^* = (\mathbf{b}_1^*, \dots, \mathbf{b}_n^*)$ to be the unique set of vectors in $\mathrm{span}(\mathcal{L})$ satisfying $\langle \mathbf{b}_i^*, \mathbf{b}_j \rangle = 1$ if $i = j$, and 0, otherwise. It is easy to show that $\hat{\mathcal{L}}$ is itself a rank $n$ lattice, that vol($\hat{\mathcal{L}}$) = $\frac{1}{\mathrm{vol}(\mathcal{L})}$, and $\mathbf{B}^*$ is a basis of $\hat{\mathcal{L}}$. Given a lattice $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$, we denote $\|\mathbf{B}\|_2 = \max_i \|\mathbf{b}_i\|$.

Let $d \in \mathbb{N}$, $1 \le k \le d$ and $q$ be a prime number. We say that a lattice $L$ is a $d$-dimensional $q$-ary lattice if $q\mathbb{Z}^d \subseteq L \subseteq \mathbb{Z}^d$. Given a matrix $\mathbf{A} \in \mathbb{Z}^{d \times k}$, we consider the following $d$-dimensional $q$-ary lattices:

$$ L_q(\mathbf{A}) = \{ \mathbf{x} \in \mathbb{Z}^d : \exists \mathbf{s} \in \mathbb{Z}^k, \mathbf{A}\mathbf{s} = \mathbf{x} \mod q \}, $$

$$ L_q^{\perp}(\mathbf{A}) = \{ \mathbf{x} \in \mathbb{Z}^d : \mathbf{A}^T \mathbf{x} = \mathbf{0} \mod q \}. $$

It is well-known that for any $q$-ary lattice $L$, there exists $\mathbf{A}$ and $\mathbf{B}$ such that $L = L_q(\mathbf{A}) = L_q^{\perp}(\mathbf{B})$, and that $\widehat{L_q^{\perp}(\mathbf{A})} = \frac{1}{q}L_q(\mathbf{A})$. Furthermore vol($L_q(\mathbf{A})$) = $q^{d-\mathrm{rk}\mathbf{A}} \ge q^{d-k}$ and therefore vol($L_q^{\perp}(\mathbf{A})$) = $q^{\mathrm{rk}\mathbf{A}} \le q^k$. Finally, since $\mathbb{Z}_q$ is a field, a random matrix $\mathbf{A}$ has full rank (equal to $k$) with probability at least $1 - kq^{k-1-d}$.

We refer the reader to [18], [38, Section 2.5.1], [28] or [29] for more details on those constructions and why these lattices play a crucial role in lattice-based cryptography, in particular because of the LWE problem.

## 2.2 Random $q$-ary lattices

We will consider the distributions $\mathcal{L}_{d,k,q}$ and $\mathcal{L}_{d,k,q}^{\perp}$ of $q$-ary lattices defined over the set of integer lattices by

$$ \mathcal{L}_{d,k,q}(L) = \mathrm{Pr}_{\mathbf{A} \sim \mathcal{U}(\mathbb{Z}_q^{d \times k})}[L = L_q(\mathbf{A})], $$

$$ \mathcal{L}_{d,k,q}^{\perp}(L) = \mathrm{Pr}_{\mathbf{A} \sim \mathcal{U}(\mathbb{Z}_q^{d \times (d-k)})}[L = L_q^{\perp}(\mathbf{A})]. $$

In other words, the distribution is obtained by taking a matrix $\mathbf{A} \in \mathbb{Z}_q^{d \times k}$ with uniform and independently distributed entries, and looking at the $q$-ary lattice generated by $\mathbf{A}$; and similarly for the orthogonal version. When neither $k$ nor $d-k$ are too small, those two distributions are very close [29, Lemma 5].
Those distributions satisfy good uniformity properties when $q$ goes to infinity. In particular, the following theorem shows that we can compute statistical properties of lattices sampled according to $\mathcal{L}_{d,k,q}^{\perp}$. See [29, Section 2.5] for more context.

In this paper, we will only make use of the following special case to compute the variance of a sum over a lattice.

**Theorem 1 ([29, Theorem 3]).** Let $d \in \mathbb{N}$, $1 \le k \le d$ and $q$ be a prime number. For any $f: \mathbb{Z}^d \to \mathbb{R}$,

$$ \begin{aligned} \mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} \left[ \sum_{\mathbf{x} \in L} f(\mathbf{x}) \right] &= \sum_{\mathbf{x} \in q\mathbb{Z}^d} f(\mathbf{x}) + q^{k-d} \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d} f(\mathbf{x}), \\ \mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} \left[ \sum_{\mathbf{x} \in L} f(\mathbf{x}) \right] &= (q^{k-d} - q^{2(k-d)}) \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d} \sum_{\mathbf{u} \in \mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} f(\mathbf{x})f(\alpha\mathbf{x} + q\mathbf{u}). \end{aligned} $$

## 2.3 Short Integer Solution Problem

We will study the following lattice problem in this paper.

**Definition 1.** Let $m \ge n \ge 1$, $q$ be integer, $\ell > 0$ and $p \in (0, \infty]$. The search problem $\text{SIS}_{n,m,q,\ell}^p$ (Shortest Integer Solution) is defined as follows. The input is a random matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$. The goal is to output a vector $\mathbf{x} \in \mathbb{Z}^m$ such that $\mathbf{A}\mathbf{x} = 0 \mod q$ and $0 < \|\mathbf{x}\|_p \le \ell$.

Using the notation from Section 2.1, solving $\text{SIS}_{n,m,q,\ell}^p$ is equivalent to finding a nonzero vector in $L_q^{\perp}(\mathbf{A}^T) \cap B_n^p(\ell)$ with $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ sampled uniformly at random. Using the notation from Section 2.2, this is equivalent to finding a nonzero vector in $L \cap B_n^p(\ell)$ with $L \sim \mathcal{L}_{m,m-n,q}^{\perp}$. Note that “$k = m - n$” here because our definition of $\mathcal{L}_{d,k,q}^{\perp}$ samples a matrix in $\mathbb{Z}_q^{d \times (d-k)}$.

When $p = 2$, the SIS problem is known to be as hard as solving approximate SVP for all lattices [4]. In practice, a standard lattice reduction algorithm (BKZ algorithm) is used on the lattice $L_q^{\perp}(\mathbf{A}^T)$ to estimate the complexity of the problem.

Due to its simplicity, the case of $p = \infty$ is more often used in cryptography. However, when the parameters are set so that $\ell\sqrt{m} > q$, there is no known worst-case problem that is reducible to the average case $\text{SIS}_{n,m,q,\ell}^{\infty}$. This parameter setting is what is used in the recent NIST-standardized signature scheme Dilithium. In its documentation, the authors proposed a heuristic model to estimate the cost of $\text{SIS}_{n,m,q,\ell}^{\infty}$, by assuming that the coordinates of the short vectors generated by a sieving algorithm follow a Gaussian distribution. This model was not backed by experiments as far as we know. More generally, there are very few algorithms known for solving $\text{SIS}_{n,m,q,\ell}^{\infty}$. In [10], the authors mentioned a polynomial time classical algorithm from Regev that solves the problem when $q$ is a composite number and $m$ is very large. They also proposed a polynomial time quantum
algorithm that solves $SIS_{n,m,q, \frac{q-c}{2}}^{\infty}$ when $c$ is a constant integer and $m$ is polynomial in $n$. More recently, [15] showed a subexponential algorithm for $SIS_{n,m,q,l}^{\infty}$ when $q = \text{poly}(n)$, $m = n + \omega(n/\log\log(n))$ and $l = q/\text{polylog}(n)$. However, when instantiating their algorithm on the concrete parameters of Dilithium, their algorithm is far from threatening Dilithium's security.

For convenience, when we discuss the running time of the algorithms solving the problems above, we ignore polynomial factors in the bit-length of the individual input basis vectors (i.e. we assume the input basis has bit-size polynomial in the ambient dimension $d$).

## 2.4 BKZ

BKZ is a famous algorithm to reduce lattice basis [33]. We refer the reader to [21] recent work on this topic, and [24] for a formal analysis of its running time.

Let $\mathbf{B}$ be a BKZ-$\beta$ reduced basis lattice (of rank $d$) in $\mathbb{R}^d$. We will denote by $\tilde{\mathbf{b}}_1, \dots, \tilde{\mathbf{b}}_d$ its Gram-Schmidt vectors. Recall that the root Hermite factor $\delta_{\mathbf{B}}$ is defined by

$$ \|\mathbf{b}_1\| = \delta_{\mathbf{B}}^{d-1} \text{vol}(L)^{1/d}. $$

Experimentally, it has been verified [11] that

$$ \delta_{\mathbf{B}} \approx H_{\beta} := \left( \frac{\beta}{2\pi e} (\pi\beta)^{1/\beta} \right)^{1/2(\beta-1)} \quad (2) $$

See also [19] for more information. We will estimate the asymptotic runtime of BKZ with block size $\beta$ by $2^{0.292\beta+o(\beta)}$ [8].

We will make use of the the Geometric Series Assumption (GSA) [32] to obtain more precise information on the shape of the basis.

**Heuristic 1 (Geometric Series Assumption (GSA))** Let $\mathbf{b}_1, \dots, \mathbf{b}_d$ be a BKZ-$\beta$ reduced basis and $\tilde{\mathbf{b}}_1, \dots, \tilde{\mathbf{b}}_d$ be the corresponding Gram-Schmidt vectors. Then for all $i = 1, \dots, d$,

$$ \|\tilde{\mathbf{b}}_i\| = \|\mathbf{b}_1\| H_{\beta}^{-2(i-1)}, \quad \|\mathbf{b}_1\| = H_{\beta}^{d-1} \text{vol}(L)^{1/d}. $$

The GSA is known to be reasonably accurate when $\beta$ is larger than 50 and much smaller than $d$, although it does not correctly model what happens in the last $d - \beta$ coordinates, see e.g. [1].

## 2.5 Discrete Gaussian distribution

Let $d \in \mathbb{N}$ and $s > 0$. For any $\mathbf{x} \in \mathbb{R}^d$, we let

$$ \rho_s(\mathbf{x}) = e^{-\pi \|\mathbf{x}\|^2 / s^2}. $$
As usual, we extend $\rho_s$ to sets by

$$ \rho_s(X) = \sum_{\mathbf{x} \in X} \rho_s(\mathbf{x}) $$

for any set $X$. For any lattice $\mathcal{L} \subset \mathbb{R}^d$, we denote the discrete Gaussian distribution over $\mathcal{L}$ by $D_{\mathcal{L},s}(\mathbf{x}) = \frac{\rho_s(\mathbf{x})}{\rho_s(\mathcal{L})}$ for any $\mathbf{x} \in \mathcal{L}$. We denote $D_{\mathcal{L},1}$ by $D_{\mathcal{L}}$ for simplicity. It is well-known by the Poisson summation formula that for any lattice $\mathcal{L}$ and any $s > 0$,

$$ \rho_{1/s}(\hat{\mathcal{L}}) = \mathrm{vol}(\mathcal{L})s^{-d}\rho_s(\mathcal{L}). $$

It easily follows from the Poisson summation formula that $\mathbf{t} \in \mathbb{R}^d$, $\rho_s(\mathbf{t} + \mathcal{L}) \le \rho_s(\mathcal{L})$ [7]. See e.g. [35] for a good introduction on this topic. The discrete Gaussian distribution plays an essential role in lattice-based cryptography and an important problem is to be able to sample efficiently from it: this is known as the discrete Gaussian sampling (DGS) problem.

**Definition 2.** For $\delta = \delta(d) \ge 0$, $s$ a function that maps lattices to non-negative real numbers, and $m = m(d) \in \mathbb{N}$, $\delta-DGS_s^m$ is defined as follows. The input is a basis $\mathbf{B}$ for a lattice $\mathcal{L} \subset \mathbb{R}^d$ and a parameter $s > s(\mathcal{L})$. The goal is to output a sequence of $m$ vectors whose joint distribution is $\delta$-close to $m$ independent samples from $D_{\mathcal{L},s}$.

We omit the parameter $\delta$ if $\delta = 0$, and the parameter $m$ if $m = 1$. We stress that $\delta$ bounds the statistical distance between the joint distribution of the output vectors and $m$ independent samples from $D_{\mathcal{L},s}$.

In general, the smaller $s$ is, the harder it is to construct a sampler for $D_{\mathcal{L},s}$. The notion of smoothing parameter [27] captures the idea that sampling for a value of $s$ above this threshold is significantly easier than sampling below because the distribution looks more like a continuous Gaussian. Formally, for any $\varepsilon > 0$, the smoothing parameter of a lattice $\mathcal{L}$ is defined by

$$ \eta_{\varepsilon}(\mathcal{L}) = \inf\{s > 0 : \rho_{1/s}(\hat{\mathcal{L}}) \le 1 + \varepsilon\}. $$

Observe that $\eta_{\varepsilon}(\mathcal{L})$ is a decreasing function of $\varepsilon$.

There are many algorithms to sample above the smoothing parameter [23,20,9], including a time-space trade-off [2]. Sampling below the smoothing parameter is much more challenging and usually inefficient [3]. At the extreme, sampling for sufficiently small values of $s$ allows one to solve the Shortest Vector problem (SVP) [3] which is known to be NP-hard under randomized reduction [5]. The Monte Carlo Markov Chain based algorithm of [37] (see Theorem 2 below) works for all values of $s$ but the complexity significantly depends on $s$ and the shape of the basis [29]. Finally, it should be noted that the problem of estimating the smoothing parameter is provably harder than BDD and LWE in certain parameter ranges [13].
**Theorem 2 ([37]).** There is an algorithm that given a basis of a lattice $L \subset \mathbb{R}^d$, any vector $\mathbf{t} \in \mathbb{R}^n$, any $\varepsilon > 0$ and any $s > 0$, returns a sample according to some distribution $\mathcal{D}_{L,s,\mathbf{t},\varepsilon}$ such that $d_{\text{TV}}(\mathcal{D}_{L,s,\mathbf{t},\varepsilon}, D_{L,s,\mathbf{t}}) \le \varepsilon$. This algorithm runs in time $\ln(\frac{1}{\varepsilon}) \cdot \frac{1}{\Delta} \cdot \text{poly}(d)$ where $\frac{1}{\Delta} = \frac{1}{\rho_s(\mathbf{t}+L)} \prod_{i=1}^k \rho_{s/\|\tilde{\mathbf{b}}_i\|}(\mathbb{Z}) \le \prod_{i=1}^k \rho_{\|\tilde{\mathbf{b}}_i\|/s}(\mathbb{Z})$ and $\tilde{\mathbf{b}}_1, \dots, \tilde{\mathbf{b}}_k$ are the Gram-Schmidt vectors of the basis.

The main difficulty in using this theorem is to estimate the quantity $\prod_{i=1}^k \rho_{\|\tilde{\mathbf{b}}_i\|/s}(\mathbb{Z})$ which strongly depends on the basis. In [31], the authors gave an approximation formula for this quantity when the basis is BKZ-reduced, and assuming that the Geometric Series Assumption (GSA) holds.

**Theorem 3 ([31, Theorem 3]†).** Let $0 < d \le n$ and $0 < \beta \le d$. Let $\mathbf{b}_1, \dots, \mathbf{b}_d \in \mathbb{R}^n$ be a BKZ-$\beta$ reduced basis of a lattice $L$ and $\tilde{\mathbf{b}}_1, \dots, \tilde{\mathbf{b}}_d$ be the Gram-Schmidt vectors of the basis. Let $s > 0$ and $\alpha = \|\mathbf{b}_1\|/s$. If the GSA holds then for any odd number $p \ge 1$,

$$ \ln \left( \prod_{i=1}^{d} \rho_{\|\tilde{\mathbf{b}}_i\|/s}(\mathbb{Z}) \right) \le A + \sum_{\ell=1}^{p} \frac{2^{\ell}(-1)^{\ell+1}}{\ell} (B_{\ell} + C_{\ell}) $$

where

$$ A = (d_0 + 1) \ln \frac{\alpha}{H_{\beta}^{d_0}} + d\varepsilon, $$

$$ B_{\ell} = \frac{E_1 \left( \pi \ell \alpha^2 H_{\beta}^{-4(d_0 + \frac{1}{2})} \right) - E_1 (\pi \ell \alpha^2 H_{\beta}^{-2})}{2 \ln(H_{\beta})}, $$

$$ C_{\ell} = \frac{E_1 \left( \frac{\pi}{\alpha^2} \ell H_{\beta}^{4(d_0 + \frac{1}{2})} \right) - E_1 \left( \frac{\pi}{\alpha^2} \ell H_{\beta}^{4(d - \frac{1}{2})} \right)}{2 \ln(H_{\beta})}, $$

$$ H_{\beta} = \left( \frac{\beta}{2\pi e} (\pi\beta)^{1/\beta} \right)^{1/2(\beta-1)}, $$

$$ d_0 = \max \left( -1, \min \left( d - 1, \left\lfloor \frac{\ln(\alpha)}{2 \ln(H_{\beta})} \right\rfloor \right) \right) \text{ and } \varepsilon \le 6.974685811 \times 10^{-6}, \text{ and } E_1 \text{ refers to the exponential integral.} $$

# 3 Technical results on the discrete Gaussian distribution

In this section, we give some technical results on the discrete Gaussian. These results are used in the next section but can also be of independent interest.

<footnote>† There seems to be a small error in the statement in [31]: the two $E_1(\cdot)$ terms in $C_\ell$ should be swapped, otherwise it would be negative.</footnote>
## 3.1 A conjecture on the ratio of the Gaussian mass of $\mathbb{Z}$

We start with a conjecture of the ratio of the Gaussian of $\mathbb{Z}$. There is strong link between this quantity and the Jacobi $\vartheta$ function. Indeed, for any $s > 0$, $\rho_s(\mathbb{Z}) = \vartheta_3(0, e^{-\pi/s^2})$, where $\vartheta_3(z, q) = \sum_{n \in \mathbb{Z}} q^{n^2} e^{2niz}$. Ratios of Jacobi $\vartheta$ functions of the form $\vartheta_3(q, z)/\vartheta_3(q, z')$ is an extensively studied topic in mathematics. Unfortunately, we could not find any result on ratios of the form $\vartheta_3(q, z)/\vartheta_3(q', z)$ which is what we are interested in.

**Conjecture 1.** For any $\gamma \ge 1$ and $s \ge 0$, the ratio $\frac{\rho_{\gamma s}(\mathbb{Z})}{\rho_s(\mathbb{Z})}$ increases as $s$ increases.

As a heuristic argument, we can first observe why Conjecture 1 seems to hold to very small and large values of $s$. When $s$ is very small, $\rho_s(\mathbb{Z})$ and $\rho_{\gamma s}(\mathbb{Z})$ are both very close to 1. As $\gamma s$ approaches 1, $\rho_{\gamma s}(\mathbb{Z})$ will slowly become asymptotically equal to $\gamma s$ while $\rho_s(\mathbb{Z})$ is still close to 1, hence the ratio $\gamma s$ increases with $s$. When $s$ becomes very large, $\rho_s(\mathbb{Z})$ becomes asymptotically close to $s$ and $\rho_{\gamma s}(\mathbb{Z})$ to $\gamma$, therefore the ratio will tend to $\gamma$. Therefore the picture of this ratio generally looks like Figure 1.

It should be noted that for any concrete value of $\gamma$ and any compact interval $I \subset (0, \infty)$, one can numerically verify that $s \in I \mapsto \frac{\rho_{\gamma s}(\mathbb{Z})}{\rho_s(\mathbb{Z})}$ is increasing. Indeed, this function has a continuous derivative and for any value of $\gamma$ and $s$, one can compute arbitrary good approximations of it (the finite sums converge quickly) and therefore prove that the derivative is positive. By an effective continuity argument, one can then “prove” the conjecture over any compact interval $I$ of values of $s$. We have verified the conjecture for many values of $\gamma$ over reasonably large intervals of $s$.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Plot of $\frac{\rho_{\gamma s}(\mathbb{Z})}{\rho_s(\mathbb{Z})}$ for several values of $\gamma$. The plots support Conjecture 1.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Fig. 2. Plot of $\frac{d}{ds} \left( \frac{\rho_{\gamma s}(Z)}{\rho_s(Z)} \right)$ for several values of $\gamma$. The plots support Conjecture 1.</figcaption></figure>

## 3.2 Bounds on certain sums over shifted copies of $\mathbb{Z}^d$

When estimating the variance of the Gaussian mass of a lattice, we will need to bound certain sums involving the Gaussian mass of the shifted lattice $\mathbb{Z}^d$. More precisely, consider, for a given $\alpha \in \mathbb{Z}_q \setminus \{0\}$, the sum

$$S(\alpha) = \sum_{\mathbf{x} \in \mathbb{Z}^d} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x} + q\mathbb{Z}^d). \qquad (3)$$

The claim is that this sum should be maximum for $\alpha = 1$. Very roughly, the intuition is that each term $\rho_s(\mathbf{x})$ is “weighted down” by $\rho_s(\alpha\mathbf{x} + q\mathbb{Z}^d)$ which, for most values of $\alpha$ and $\mathbf{x}$, will be essentially close to $\rho_s(\alpha\mathbf{x})$, and therefore we want to take $\alpha$ as small as possible. Informally,

$$S(\alpha) \approx \sum_{\mathbf{x} \in \mathbb{Z}^d} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x}) = \sum_{\mathbf{x} \in \mathbb{Z}^d} \rho_{s/\sqrt{1+\alpha^2}}(\mathbf{x}) = \rho_{s/\sqrt{1+\alpha^2}}(\mathbb{Z}^d)$$

which is indeed maximum for $\alpha = 1$. The next lemma formalizes this intuition.

**Lemma 1.** For any $\alpha \in \mathbb{Z}_q \setminus \{0\}$, $d \ge 1$ and $q \ge 3$, if Conjecture 1 holds then

$$\sum_{\mathbf{x} \in \mathbb{Z}^d} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x} + q\mathbb{Z}^d) \le \rho_{s/\sqrt{2}}(\mathbb{Z}^d) \rho_{s\sqrt{2}/q}(\mathbb{Z}^d).$$

*Remark 1.* Note that for $\alpha = 1$, and by [14, Lemma 2.14], the sum is equal to

$$\sum_{\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{2}}(q\mathbf{u}) \rho_{s\sqrt{2}}(q\mathbf{u} + 2\mathbb{Z}^d) \ge \sum_{\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{2}}(q\mathbf{u}) \rho_{s\sqrt{2}}(q\mathbf{u} \text{ mod } 2) \rho_{s\sqrt{2}}(2\mathbb{Z}^d)$$
$$ \geq \sum_{\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{2}}(q\mathbf{u})\rho_{s\sqrt{2}}(\sqrt{d})\rho_{s/\sqrt{2}}(\mathbb{Z}^d) \\ = \rho_{s\sqrt{2}}(\sqrt{d})\rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d). $$

Therefore Lemma 1 is tight§ when $\sqrt{d}/s$ is not large.

*Proof.* First, observe that for any $\alpha \in \mathbb{Z}_q$,

$$ F_{d,q}(\alpha) = \sum_{\mathbf{x},\mathbf{u} \in \mathbb{Z}^d} \rho_s(\mathbf{x})\rho_s(\alpha\mathbf{x} + q\mathbf{u}) = \rho_s(\mathcal{L}) $$

where $\mathcal{L} = \{(\mathbf{x}, \alpha\mathbf{x} + q\mathbf{u}) : \mathbf{x}, \mathbf{u} \in \mathbb{Z}^d\}$. Since $\rho_s$ only depends on the 2-norm of its argument, we have that $F_{d,q}(\alpha) = \rho_s(R\mathcal{L})$ for any rotation $R$. Consider the rotation $R$ defined by its matrix:

$$ R = \begin{bmatrix} \frac{\alpha}{\sqrt{1+\alpha^2}} I_d & \frac{-1}{\sqrt{1+\alpha^2}} I_d \\ \frac{1}{\sqrt{1+\alpha^2}} I_d & \frac{\alpha}{\sqrt{1+\alpha^2}} I_d \end{bmatrix} $$

where $I_n$ is the identity matrix in dimension $d$. Then check that

$$ R \mathcal{L} = \frac{1}{\sqrt{1+\alpha^2}} \{( -q\mathbf{u}, (1+\alpha^2)\mathbf{x} + \alpha q\mathbf{u}) : \mathbf{x}, \mathbf{u} \in \mathbb{Z}^d \}. $$

It follows that

$$ \begin{aligned} F_{d,q}(\alpha) &= \sum_{\mathbf{x},\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{1+\alpha^2}}(-q\mathbf{u})\rho_{s\sqrt{1+\alpha^2}}((1+\alpha^2)\mathbf{x} + \alpha q\mathbf{u}) \\ &= \sum_{\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{1+\alpha^2}}(-q\mathbf{u})\rho_{s\sqrt{1+\alpha^2}}(\alpha q\mathbf{u} + (1+\alpha^2)\mathbb{Z}^d) \\ &\le \sum_{\mathbf{u} \in \mathbb{Z}^d} \rho_{s\sqrt{1+\alpha^2}}(-q\mathbf{u})\rho_{s\sqrt{1+\alpha^2}}((1+\alpha^2)\mathbb{Z}^d) \\ &= \rho_{s\sqrt{1+\alpha^2}}(q\mathbb{Z}^d)\rho_{s\sqrt{1+\alpha^2}}((1+\alpha^2)\mathbb{Z}^d) \\ &= \rho_{s\sqrt{1+\alpha^2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{1+\alpha^2}}(\mathbb{Z}^d). \end{aligned} $$

Now observe that $F_{d,q}$ is $q$-periodic so we can assume that $\alpha \in \{-\frac{q-1}{2}, \dots, \frac{q-1}{2}\} \setminus \{0\}$ and therefore $1+\alpha^2 \le q^2/4$ since $q \ge 3$. It follows that $\sqrt{1+\alpha^2}/q \le 1/2 \le 1/\sqrt{2}$. We can use Conjecture 1 for $\gamma = \frac{\sqrt{1+\alpha^2}}{\sqrt{2}} \ge 1$ (since $\alpha \ne 0$) to get that

$$ \begin{aligned} F_{d,q}(\alpha) &= \frac{\rho_{s\sqrt{1+\alpha^2}/q}(\mathbb{Z}^d)}{\rho_{s\sqrt{2}/q}(\mathbb{Z}^d)} \rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{1+\alpha^2}}(\mathbb{Z}^d) \\ &\le \frac{\rho_{s/\sqrt{2}}(\mathbb{Z}^d)}{\rho_{s/\sqrt{1+\alpha^2}}(\mathbb{Z}^d)} \rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{1+\alpha^2}}(\mathbb{Z}^d) \\ &= \rho_{s/\sqrt{2}}(\mathbb{Z}^d)\rho_{s\sqrt{2}/q}(\mathbb{Z}^d). \end{aligned} $$

□

<footnote>§ An upper bound independent of $\alpha$ is sufficient, it will become clear why in Section 4.1.</footnote>
### 3.3 Bounds on certain sums in a ball

In the next section, we will need to bound a similar sum to (3) but restricted to an $\ell_p$-ball. This is quite difficult to do in the general case when the ball may contain some $q$-vectors. However we show that if the ball is not too large, we can obtain a tight bound without even appealing to Conjecture 1. We start with a straightforward combinatorial lemma.

**Lemma 2.** Let $k \ge 1$, $\tau$ be a permutation of $\{1, \dots, k\}$ and $x_1, \dots, x_k \in \mathbb{R}$.
Then $\sum_{i=1}^k x_i x_{\tau(i)} \le \sum_{i=1}^k x_i^2$.

*Proof.* By a straightforward calculation: $\sum_{i=1}^k x_i x_{\tau(i)} \le \frac{1}{2} \sum_{i=1}^k (x_i^2 + x_{\tau(i)}^2) = \sum_{i=1}^k x_i^2$ since $\tau$ is a permutation. $\square$

Similarly to Lemma 1, we want to show that the sum is maximum when $\alpha = 1$.

**Lemma 3.** For any $p \in [1, \infty]$, prime $q$, $\alpha \in \mathbb{Z}_q \setminus \{0\}$, $d \ge 1$ and $0 \le l \le q/2$,

$$ \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(l)} \sum_{\mathbf{u} \in \mathbb{Z}^d : \alpha \mathbf{x} + q \mathbf{u} \in B_d^p(l)} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x} + q \mathbf{u}) \le \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(l)). $$

*Remark 2.* This upper bound cannot be improved because of $\alpha = 1$, the sum is equal to

$$ \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(l)} \sum_{\mathbf{u} \in \mathbb{Z}^d : \mathbf{x} + q\mathbf{u} \in B_d^p(l)} \rho_s(\mathbf{x}) \rho_s(\mathbf{x} + q\mathbf{u}) = \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(l)} \rho_s(\mathbf{x}) \rho_s(\mathbf{x}) = \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(l)) $$

since if $\mathbf{x} \in B_d^{p,\mathbb{Z}}(l)$ then the only value of $\mathbf{u}$ for which $\mathbf{x} + q\mathbf{u} \in B_d^p(l)$ is $\mathbf{u} = 0$.

*Proof.* Note that the sum a $q$-periodic function of $\alpha$ so we can assume without loss of generality that $\alpha \in \{1, \dots, q-1\}$ in the rest of the proof.

For any $\mathbf{x} \in \mathbb{Z}^d$, let $U_\alpha(\mathbf{x}) := \{\mathbf{u} \in \mathbb{Z}^d : \alpha \mathbf{x} + q\mathbf{u} \in B_d^p(l)\}$. We claim that $|U_\alpha(\mathbf{x})| \le 1$. Indeed, let $\mathbf{u}, \mathbf{v} \in U_\alpha(\mathbf{x})$ and observe that

$$ \|\alpha \mathbf{x} + q \mathbf{u}\|_p + \|\alpha \mathbf{x} + q \mathbf{v}\|_p < 2l \le q $$

by definition of $U_\alpha(\mathbf{x})$. On the other hand,

$$ \|\alpha \mathbf{x} + q \mathbf{u}\|_p + \|\alpha \mathbf{x} + q \mathbf{v}\|_p \ge \|(\alpha \mathbf{x} + q \mathbf{u}) - (\alpha \mathbf{x} + q \mathbf{v})\|_p = q \|\mathbf{u} - \mathbf{v}\|_p. $$

Since $\mathbf{u}, \mathbf{v} \in \mathbb{Z}^d$, either $\mathbf{u} = \mathbf{v}$ or $\|\mathbf{u} - \mathbf{v}\|_p \ge 1$, but the latter contradicts the above equations.

For any $\mathbf{x} \in B_d^{p,\mathbb{Z}}(l)$, let $f(\mathbf{x}) = \alpha \mathbf{x} + q\mathbf{u}$ if $U_\alpha(\mathbf{x}) = \{\mathbf{u}\}$, and $f(\mathbf{x})$ be undefined if $U_\alpha(\mathbf{x})$ is empty. Then by definition, $f$ is a map from $B_d^{p,\mathbb{Z}}(l)$ to itself. Furthermore, we claim that $f$ is injective. Indeed, if we have $f(\mathbf{x}) = f(\mathbf{y})$ for some $\mathbf{x}, \mathbf{y} \in B_d^{p,\mathbb{Z}}(l)$ then $\alpha(\mathbf{x} - \mathbf{y}) = q(\mathbf{u} - \mathbf{v})$ where $U_\alpha(\mathbf{x}) = \{\mathbf{u}\}$ and
$U_\alpha(\mathbf{y}) = \{\mathbf{v}\}$. Recall that $\mathbf{x}, \mathbf{y}, \mathbf{u}, \mathbf{v}$ have integer coordinates and $q$ is prime. Therefore, $q$ divides $\alpha(\mathbf{x} - \mathbf{y})$. But $q$ is prime and $\alpha \in \{1, \dots, q-1\}$ so $q$ divides $\mathbf{x} - \mathbf{y}$. But since $\mathbf{x}, \mathbf{y} \in B_d^{p,\mathbb{Z}}(\ell)$, we have that $\|\mathbf{x} - \mathbf{y}\|_p < 2\ell \le q$. Therefore the only possibility is that $\mathbf{x} = \mathbf{y}$.

Finally, observe that since $f$ is injective from $B_d^{p,\mathbb{Z}}(\ell)$ into itself, we can extend $f$ to an arbitrary permutation $\tau$ of $B_d^{p,\mathbb{Z}}(\ell)$. We then have that

$$
\begin{align*}
& \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(\ell)} \sum_{\mathbf{u} \in U_\alpha(\mathbf{x})} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x} + q\mathbf{u}) \\
&= \sum_{\mathbf{x} \in \text{Supp}(f)} \rho_s(\mathbf{x}) \rho_s(f(\mathbf{x})) \\
&\le \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(\ell)} \rho_s(\mathbf{x}) \rho_s(\tau(\mathbf{x})) \quad \text{since } \rho_s \text{ is non-negative} \\
&\le \sum_{\mathbf{x} \in B_d^{p,\mathbb{Z}}(\ell)} \rho_s(\mathbf{x}) \rho_s(\mathbf{x}) \quad \text{by Lemma 2} \\
&= \rho_s/\sqrt{2} (B_d^{p,\mathbb{Z}}(\ell)).
\end{align*}
$$

□

## 3.4 Other useful bounds

We will need the following results on the discrete Gaussian mass of lattices. The first result gives a tight bound on the Gaussian mass of the interval $[-\ell, \ell]$ (in dimension one). This will be very useful when studying SIS in the infinity norm where we need bounds on the Gaussian mass of the $\ell_\infty$-ball of radius $\ell$ which is $[-\ell, \ell]^d$, see Theorem 5.

**Lemma 4.** For any $s > 0$ and $\ell \ge 1$, we have that

$$1 + s \left( \operatorname{erf} \left( \frac{\ell \sqrt{\pi}}{s} \right) - \operatorname{erf} \left( \frac{\sqrt{\pi}}{s} \right) \right) \le \rho_s([-\ell, \ell] \cap \mathbb{Z}) \le 1 + s \operatorname{erf} \left( \frac{\ell \sqrt{\pi}}{s} \right).$$

*Proof.* Let $N = \lfloor \ell \rfloor$ so that $\rho_s([-\ell, \ell] \cap \mathbb{Z}) = \sum_{k=-N}^N \rho_s(k) = 1 + 2 \sum_{k=1}^N \rho_s(k)$. Then check that since $\rho_s$ is decreasing over $[0, \infty]$,

$$\sum_{k=1}^{N} \rho_s(k) \le \sum_{k=1}^{N} \int_{k-1}^{k} \rho_s(t) \, dt = \int_{0}^{k} \rho_s(t) \, dt = \frac{s}{2} \operatorname{erf} \left( \frac{N\sqrt{\pi}}{s} \right)$$

and we conclude since $N \le \ell$ and $\operatorname{erf}$ is increasing. Similarly,

$$\sum_{k=1}^{N} \rho_s(k) \ge \int_{1}^{k+1} \rho_s(t) \, dt = \frac{s}{2} \left( \operatorname{erf} \left( \frac{(N+1)\sqrt{\pi}}{s} \right) - \operatorname{erf} \left( \frac{\sqrt{\pi}}{s} \right) \right)$$

and we conclude since $N \ge \ell - 1$ and $\operatorname{erf}$ is increasing. □
Our second result give some intuitive asymptotics on the Gaussian mass of $\mathbb{Z}^d$ for extreme values of the width, specifically that $\rho_\sigma(\mathbb{Z})^d$ should be very close to $\sigma^d$ for large $\sigma$ and very close to 1 for small $\sigma$.

**Lemma 5.** Let $\sigma = \sigma(d) > 0$. If $\sigma = \omega(\sqrt{\log d})$ then $\rho_\sigma(\mathbb{Z})^d = \sigma^d(1 + o(1))$ as $d \to \infty$. If $\sigma = \omega(\sqrt{\log d})$ then $\rho_{1/\sigma}(\mathbb{Z})^d = 1 + O(de^{-\pi\sigma^2}) = 1 + o(1)$ as $d \to \infty$.

*Proof.* Recall that by the Poisson formula, for $\sigma \to \infty$,

$$ \rho_{\sigma}(\mathbb{Z}) = s \left( 1 + 2 \sum_{k=1}^{\infty} e^{-\pi k^2 \sigma^2} \right) \le \sigma + 2\sigma \sum_{k=1}^{\infty} e^{-\pi k \sigma^2} = \sigma(1 + 2e^{-\pi \sigma^2} + o(e^{-\pi \sigma^2})). $$

Therefore,

$$ \rho_{\sigma}(\mathbb{Z})^d \le \sigma^d e^{d \log(1+2e^{-\pi \sigma^2}+o(e^{-\pi \sigma^2}))} \le \sigma^d e^{2de^{-\pi \sigma^2}+o(de^{-\pi \sigma^2})} = \sigma^d(1+o(1)) $$ 
if $\sigma = \omega(\sqrt{\log d})$. Similarly, for $\sigma \to \infty$,

$$ \rho_{1/\sigma}(\mathbb{Z}) \le 1 + 2 \sum_{k=1}^{\infty} e^{-\pi k \sigma^2} = 1 + 2e^{-\pi \sigma^2} + o(e^{-\pi \sigma^2}) $$

and therefore

$$ \rho_{1/\sigma}(\mathbb{Z})^d \le e^{2de^{-\pi \sigma^2}+o(de^{-\pi \sigma^2})} = 1 + O(de^{-\pi \sigma^2}) $$ 
if $\sigma = \omega(\sqrt{\log d})$. $\square$

Finally, the following lemma gives relatively tight asymptotic bounds on the Gaussian mass $\rho_s(B_d^\tau(\ell))$ of the integers points in an $\ell_2$-ball when the radius is neither too small nor too large. The former constraint is required so that we can accurately approximate the number of integer points in an $\ell_2$-ball (see (1)). The latter is a technical condition used to simplify the calculation and essentially guarantee that we are the “heavy boundary” regime. This means that most of the Gaussian weight is concentrated on the boundary of $B_d^\tau(\ell)$. For sufficient large radii $\ell$, this becomes false as the weight of the boundary starts decreasing with $\ell$.

**Lemma 6.** Let $\ell = \ell(d)$ and $s = s(\ell)$. If $\ell^2 \le \frac{d(4s^2+\pi-\sqrt{\pi^2+8\pi s^2})}{8\pi}$ and $\ell = \omega(\sqrt{d})$ then

$$ \ell^d e^{-\pi \ell^2 / s^2} \left( \frac{2\pi e}{d} \right)^{d/2} e^{o(d)} \le \rho_s(B_d^\tau(\ell)) \le \ell^{d+2} e^{-\pi \ell^2 / s^2} \left( \frac{2\pi e}{d} \right)^{d/2} e^{o(d)} $$ 
as $d \to \infty$.

*Proof.* To simplify the proof, we will assume that $\ell$ is an integer. This can be formalised by replacing $\ell$ by $\lfloor \ell \rfloor$ which is asymptotically equivalent.

$$ \rho_s(B_d^\tau(\ell)) = \sum_{k=0}^{\ell^2} e^{-\pi k / s^2} |\{\mathbf{x} \in \mathbb{Z}^d : \|\mathbf{x}\|^2 = k\}| $$
$$
\begin{align*}
&\le \sum_{k=0}^{\ell^2} e^{-\pi k/s^2} |\{\mathbf{x} \in \mathbb{Z}^d : \|\mathbf{x}\|^2 \le k\}| \\
&\le \sum_{k=0}^{\ell^2} e^{-\pi k/s^2} \operatorname{vol}(B_d(\sqrt{k} + \frac{1}{2}\sqrt{d})) \quad \text{by (1)} \\
&= \operatorname{vol}(B_d) \sum_{k=0}^{\ell^2} e^{-\pi k/s^2} (\sqrt{k} + \frac{1}{2}\sqrt{d})^d.
\end{align*}
$$

Let $f(t) = e^{-\pi t/s^2}(\sqrt{t} + \frac{1}{2}\sqrt{d})^d$ be defined for any $t > 0$. A rather tedious analysis shows that $f$ is increasing over $[0, t_0]$ where

$$t_0 = \frac{d(4s^2 + \pi - \sqrt{\pi^2 + 8\pi s^2})}{8\pi}.$$

It follows that if $\ell^2 \le t_0$ and $\ell = \omega(\sqrt{d})$ then as $d \to \infty$

$$
\begin{align*}
\rho_s(B_d^{\mathbb{Z}}(\ell)) &\le (1 + \ell^2) f(\ell^2) \operatorname{vol}(B_d) \\
&= \ell^2 e^{-\pi \ell^2 / s^2} \ell^d e^{o(d)} \frac{1}{\sqrt{d\pi}} \left(\frac{2\pi e}{d}\right)^{d/2}.
\end{align*}
$$

The lower bound is simpler since

$$
\begin{align*}
\rho_s(B_d^{\mathbb{Z}}(\ell)) &= \sum_{k=0}^{\ell^2} e^{-\pi k/s^2} |\{\mathbf{x} \in \mathbb{Z}^d : \|\mathbf{x}\|^2 = k\}| \\
&\ge \sum_{k=0}^{\ell^2} e^{-\pi \ell^2/s^2} |\{\mathbf{x} \in \mathbb{Z}^d : \|\mathbf{x}\|^2 = k\}| \\
&= e^{-\pi \ell^2/s^2} |\operatorname{vol}(B_d^{\mathbb{Z}}(\ell))| \\
&\ge e^{-\pi \ell^2/s^2} \operatorname{vol}(B_d(\ell - \frac{1}{2}\sqrt{d})) \\
&= e^{-\pi \ell^2/s^2} (\ell - \frac{1}{2}\sqrt{d})^d \operatorname{vol}(B_d)
\end{align*}
$$

and the rest of the computation is similar. $\square$

# 4 On the Gaussian mass of random q-ary lattices

In this section, we give probabilistic estimates on the value of $\rho_s(L)$ when $L$ is a random q-ary lattice (see Section 2.2 for more details). These bounds also allow us to bound the smoothing parameter of random q-ary lattices.

A similar result was shown for “standard” random q-ary lattices (i.i.d. from uniform entries) in [25, Lemma 3] but only gives the expected value, whereas we also bound the variance. A much weaker bound on the variance is given in [31]. A closely related result is available in [22] which studies matrices with each entry
independently and identically distributed from an integer Gaussian distribution. Similarly, [12, Appendix A], [26, Section 7] and [34, Theorem 2] analyzes the Gaussian mass of a random q-ary lattice over cyclotomic fields. Finally, a very similar result appeared in [30] for real random lattices.

## 4.1 Mass of the entire lattice

The following gives a bound on the expected value and variance of the Gaussian of a random q-ary lattices. We follow the same approach as [31, Lemma 4] by using Theorem 1 but we obtain a much stronger bound using the results of the previous section, see Remark 4 for more details.

**Lemma 7.** For any $d \in \mathbb{N}$, $1 \le k \le d$, an odd prime number $q$ and $s > 0$, if Conjecture 1 holds then

$$ 
\begin{aligned}
\mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L)] &= \rho_{s/q}(\mathbb{Z}^d) + q^{k-d}\rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d), \\
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L)] &\le q^{1+k-d}\rho_s(\sqrt{2}/q)(\mathbb{Z}^d)\rho_s(\sqrt{2}\mathbb{Z}^d), \\
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L)] &\ge (q^{k-d} - q^{2(k-d)})X
\end{aligned}
$$

where

$$ X = \rho_{s\sqrt{2}}(\sqrt{d})\rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d) - (q-1)\rho_{s/q}(\mathbb{Z}^d)^2. $$

*Proof.* We use Theorem 1 to get that

$$ \mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L)] = \rho_s(q\mathbb{Z}^d) + q^{k-d}\rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d) $$

To estimate the variance, we use Theorem 1 again to get that

$$ 
\begin{aligned}
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L)] &= (q^{k-d} - q^{2(k-d)}) \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d} \sum_{\mathbf{u} \in \mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} \rho_s(\mathbf{x})\rho_s(\alpha\mathbf{x} + q\mathbf{u}) \\
&= (q^{k-d} - q^{2(k-d)}) \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} \rho_s(\mathbf{x})\rho_s(\alpha\mathbf{x} + q\mathbb{Z}^d) \\
&= (q^{k-d} - q^{2(k-d)})(A - B)
\end{aligned}
$$

where

$$ A = \sum_{\mathbf{x} \in \mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} \rho_s(\mathbf{x})\rho_s(\alpha\mathbf{x} + q\mathbb{Z}^d), \quad B = \sum_{\mathbf{x} \in q\mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} \rho_s(\mathbf{x})\rho_s(\alpha\mathbf{x} + q\mathbb{Z}^d). $$

By Lemma 1,

$$ A \le (q-1)\rho_{s\sqrt{2}}(q\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d). $$

We conclude on the upper bound since $B \ge 0$ and $q^{k-d} - q^{2(k-d)} \le q^{k-d}$. For the lower bound, first note that by Remark 1, we have (by keeping only the term $\alpha = 1$)

$$ A \ge \rho_{s\sqrt{2}}(\sqrt{d})\rho_{s\sqrt{2}}(q\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d). $$
Furthermore,

$$B \le (q-1) \sum_{\mathbf{x} \in q\mathbb{Z}^d} \rho_s(\mathbf{x})\rho_s(q\mathbb{Z}^d) = (q-1)\rho_{s/q}(\mathbb{Z}^d)^2.$$

This concludes for the lower bound.

□

**Remark 3.** If $1 \le s \le q$ then by Lemma 5,

$$\mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [\rho_s(L)] \approx 1 + q^{k-d} s^d$$

Furthermore, $\det(L) = q^{d-k}$ for almost all $L \sim \mathcal{L}_{d,k,q}^{\perp}$ (Sections 2.1 and 2.2). Hence, we recover a similar result to that of real lattices [30], namely that

$$\rho_s(L) \approx 1 + \frac{s^d}{\mathrm{vol}(L)}.$$

**Remark 4.** [29, Lemma 4] bounds the same variance by $q^{1+k-d}\rho_s(q\mathbb{Z}^d)\rho_s(\mathbb{Z}^d)$. To see why Lemma 7 is a significant improvement, observe that for the regime of interest where $q$ is much larger than $s$ but $s$ is not small (here $s \ge \sqrt{2}$ suffices), we have

$$\rho_s(q\mathbb{Z}^d)\rho_s(\mathbb{Z}^d) \approx s^d$$

whereas

$$\rho_s\sqrt{2}(q\mathbb{Z}^d)\rho_s/\sqrt{2}(\mathbb{Z}^d) \approx 2^{-d/2} \cdot s^d.$$

This allows us to significantly improve the probabilistic bound on $\rho_s$ of a random $q$-ary lattice, as shown in the corollary below.

**Remark 5.** The upper bound on the variance is essentially optimal when $1 \ll s \ll q$ and $q^{d-k}$ is large. Indeed, in this case $q^{k-d} - q^{2(k-d)} \approx q^{k-d}$ and $X \approx \rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d)$ which matches the upper bound up to a factor $q$.

**Corollary 1.** For any $d \in \mathbb{N}$, $1 \le k \le d$, an odd prime number $q$, $\alpha > 0$ and $s > 0$, if Conjecture 1 holds then

$$\mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [|\rho_s(L) - \mu| > \alpha] \le \frac{q^{1+k-d} \rho_{s\sqrt{2}/q}(\mathbb{Z}^d) \rho_{s/\sqrt{2}}(\mathbb{Z}^d)}{\alpha^2}$$

where $\mu = \rho_{s/q}(\mathbb{Z}^d) - q^{k-d}\rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d)$.

*Proof.* This is a direct application of Lemma 7 and Chebyshev's inequality. □

A direct consequence of these results is that we can obtain a bound on the smoothing parameter of a random lattice. Note here that since the definition of the smoothing parameter concerns the dual of the lattice, the result is on the distribution $\mathcal{L}_{d,k,q}$. This distribution is known to be close to $\mathcal{L}_{d,k,q}^{\perp}$ when $1 \ll k \ll d$ [29, Lemma 5].
**Lemma 8.** Let $d \in \mathbb{N}$, $1 \le k \le d$, an odd prime number $q$, $s > 0$ and $\varepsilon > 0$. Define $\alpha = 1 + \varepsilon - \rho_{1/s}(\mathbb{Z}^d) - q^{-k}\rho_{q/s}(\mathbb{Z}^d \setminus q\mathbb{Z}^d)$. If $\alpha > 0$ and Conjecture 1 holds then

$$ \mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}}[\eta_{\varepsilon}(L) > s] \le \frac{q^{1-k} \rho_{\sqrt{2}/s}(\mathbb{Z}^d) \rho_{q/s\sqrt{2}}(\mathbb{Z}^d)}{\alpha^2}. $$

*Proof.* Recall that $\eta_{\varepsilon}(L) > s$ if and only $\rho_{1/s}(\hat{L}) > 1 + \varepsilon$. Furthermore, if $L \sim \mathcal{L}_{d,k,q}$ then $\hat{L} \sim \frac{1}{q}\mathcal{L}_{d,d-k,q}^{\perp}$. Therefore,

$$ \mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}}[\eta_{\varepsilon}(L) > s] = \mathrm{Pr}_{L \sim \mathcal{L}_{d,d-k,q}^{\perp}}[\rho_{1/s}(\frac{1}{q}L) > 1 + \varepsilon] = \mathrm{Pr}_{L \sim \mathcal{L}_{d,d-k,q}^{\perp}}[\rho_{q/s}(L) > 1 + \varepsilon]. $$

By Corollary 1, for any $\alpha > 0$ and $\sigma > 0$,

$$ \mathrm{Pr}_{L \sim \mathcal{L}_{d,d-k,q}^{\perp}}[\rho_s(L) > \alpha + \rho_{\sigma/q}(\mathbb{Z}^d) + q^{-k}\rho_{\sigma}(\mathbb{Z}^d \setminus q\mathbb{Z}^d)] \le \frac{q^{1-k}\rho_{\sigma\sqrt{2}/q}(\mathbb{Z}^d)\rho_{\sigma/\sqrt{2}}(\mathbb{Z}^d)}{\alpha^2}. $$

Therefore, by our assumption, we can let $\sigma = q/s$ and $\alpha = 1 + \varepsilon - \rho_{\sigma/q}(\mathbb{Z}^d) - q^{k-d}\rho_{\sigma}(\mathbb{Z}^d \setminus q\mathbb{Z}^d)$ to get the result. $\square$

The previous lemma is difficult to use due to the nontrivial quantities involved in the bound. The following corollary gives an asymptotic bound under reasonable conditions (see remark below).

**Corollary 2.** Let $k = k(d)$, $q = q(d)$, $\varepsilon = \varepsilon(n)$. Assume that $q^{1-k/d}\varepsilon^{2/d} = \omega(\sqrt{\log d})$ and $q^{k/d}\varepsilon^{-2/d} = \omega(\sqrt{\log d})$. Let $s_{\varepsilon} = q^{1-k/d} \left( \frac{2\varepsilon+q+\sqrt{4\varepsilon q+q^2}}{2\varepsilon^2} \right)^{1/d}$. If Conjecture 1 holds then

$$ \mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}}[\eta_{\varepsilon}(L) > s_{\varepsilon}] \le 2^{-d/2}(1 + o(1)). $$

*Remark 6.* In a typical setting where $q = \text{poly}(d)$ and $1 \ll k \ll d$, we trivially have $q^{1-k/d} = \omega(\sqrt{\log d})$ and $q^{k/d} = \omega(\sqrt{\log d})$. Therefore the technical conditions hold true as soon as $\varepsilon^{2/d} = \Omega(1)$ and $\varepsilon^{-2/d} = \Omega(1)$ which in particular is true when $\varepsilon(d)$ is at least constant and at most subexponential in $d$. A much better analysis is of course possible for precise values of the parameters.

*Proof.* Let $s = s(n)$ be such that $s = \omega(\sqrt{\log d})$ and $q/s = \omega(\sqrt{\log d})$. By our assumption that $s = \omega(\sqrt{\log d})$ and that $q/s = \omega(\sqrt{\log d})$ and Lemma 5 it follows that

$$ \rho_{1/s}(\mathbb{Z}^d) = 1 + O(de^{-\pi s^2}), \qquad \rho_{\sqrt{2}/s}(\mathbb{Z}^d) = 1 + O(de^{-\pi s^2/2}), $$

$$ \rho_{q/s}(\mathbb{Z}^d) = q^d s^{-d}(1 + o(1)), \qquad \rho_{q/s\sqrt{2}}(\mathbb{Z}^d) = q^d 2^{-d/2}s^{-d}(1 + o(1)). $$

Therefore, using the notation of Lemma 8

$$ \alpha = 1 + \varepsilon - \rho_{1/s}(\mathbb{Z}^d) - q^{-k}\rho_{q/s}(\mathbb{Z}^d \setminus q\mathbb{Z}^d) $$

$$ = \varepsilon - O(de^{-\pi s^2}) - q^{d-k}s^{-d}(1 + o(1)) $$
$$= \tilde{\varepsilon} - 1/x$$

where $\tilde{\varepsilon} = \varepsilon + O(de^{-\pi s^2})$ and $x = q^{k-d}s^d(1+o(1))$. Furthermore, if $\alpha > 0$ then $\mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}}[\eta_{\varepsilon}(L) > s] \le p$ where

$$ \begin{aligned} p &= \frac{q^{1-k} \rho_{\sqrt{2}/s}(\mathbb{Z}^d) \rho_{q/s\sqrt{2}}(\mathbb{Z}^d)}{\alpha^2} \\ &= \frac{q^{1-k}(1+o(1))q^d 2^{-d/2}(1+o(1))}{s^d \alpha^2} \\ &= \frac{2^{-d/2}q(1+o(1))}{x(\tilde{\varepsilon} - 1/x)^2}. \end{aligned} $$

Solving for $x(\tilde{\varepsilon} - 1/x)^2 = q$, we get that the only solution meaningful solution is

$$x = \frac{2\tilde{\varepsilon} + q + \sqrt{4\tilde{\varepsilon}q + q^2}}{2\tilde{\varepsilon}^2}$$

assuming that $\tilde{\varepsilon} > 0$. From this, we get that $s = q^{1-k/d}x^{1/d}$ which verifies our initial assumptions that $s = \omega(\sqrt{\log d})$ and $q/s = \omega(\sqrt{\log d})$ by the assumptions of the lemma. Therefore $p \le 2^{-d/2}(1+o(1))$. $\square$

**Remark 7.** This result is very similar to that of [30, Corollary 3]. Indeed, the extra $q^{1-k/d}$ factor in the definition of $s_{\varepsilon}$ accounts for the volume $q^{d-k}$ of almost all $q$-ary lattices in $\mathcal{L}_{d,k,q}$, but the second part is otherwise almost identical. In particular, for similar reasons to [30, Section 2], we expect this bound to be quite good for constant $\varepsilon$ but not asymptotically optimal as $\varepsilon \to 0$. More precisely, our asymptotic will be $q^{1-k/d}\varepsilon^{-2/d}$ when we expect $q^{1-k/d}\varepsilon^{-1/d}$.

## 4.2 Mass of a ball

For the application to SIS, we not only require a bound on $\rho_s(L)$ but also a bound on $\rho_s(L \cap B_d^p(\ell))$, for any norm $\ell \in [1, \infty]$. The following lemma follows a similar strategy for this quantity. Due to some technical limitations in our proof, we can only handle radii $\ell$ up to $q/w$, so this lemma does not allow us to recover the result on $\rho_s(L)$ by letting $\ell$ tend to infinity. On the other hand, we are able to prove unconditional results, without relying on Conjecture 1. The main result, Corollary 3, informally shows that for a random lattice $L \sim \mathcal{L}_{d,k,q}^{\perp}$,

$$\rho_s(L \cap B_d^p(\ell)) \approx 1 + q^{k-d} \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\})$$

and quantifies the deviation from the average.

**Lemma 9.** For any $p \in [1, \infty]$, $d \in \mathbb{N}$, $1 \le k \le d$, an odd prime number $q$, $0 \le \ell \le q/2$ and $s > 0$,

$$\mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L \cap B_d^p(\ell))] = 1 + q^{k-d} \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\}),$$

$$\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L \cap B_d^p(\ell))] \le (q-1)q^{k-d} \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\}),$$

$$\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}}[\rho_s(L \cap B_d^p(\ell))] \ge (q^{k-d} - q^{2(k-d)}) \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\}).$$
Proof. We use Theorem 1 to get that

$$
\begin{align*}
\mathbb{E}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [\rho_s(L \cap B_d^p(\ell))] &= \rho_s(q\mathbb{Z}^d \cap B_d^p(\ell)) + q^{k-d} \rho_s((\mathbb{Z}^d \setminus q\mathbb{Z}^d) \cap B_d^p(\ell)) \\
&= 1 + q^{k-d} \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\})
\end{align*}
$$

where we have used that $\ell \le q$ to conclude that $q\mathbb{Z}^d \cap B_d^p(\ell) = \{0\}$ and $(\mathbb{Z}^d \setminus q\mathbb{Z}^d) \cap B_d^p(\ell) = (\mathbb{Z}^d \setminus \{0\}) \cap B_d^p(\ell) = B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\}$. To estimate the variance, let $f(\mathbf{x}) = \rho_s(\mathbf{x})\mathbb{1}[\mathbf{x} \in B_d^p(\ell)]$. We use Theorem 1 again to get that

$$
\begin{align*}
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [\rho_s(L \cap B_d^p(\ell))] \\
&= (q^{k-d} - q^{2(k-d)}) \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d} \sum_{\mathbf{u} \in \mathbb{Z}^d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} f(\mathbf{x}) f(\alpha\mathbf{x} + q\mathbf{u}) \\
&\le q^{k-d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} \sum_{\mathbf{x} \in \mathbb{Z}^d \setminus q\mathbb{Z}^d : \mathbf{x} \in B_d^p(\ell)} \sum_{\mathbf{u} \in \mathbb{Z}^d : \alpha\mathbf{x} + q\mathbf{u} \in B_d^p(\ell)} \rho_s(\mathbf{x}) \rho_s(\alpha\mathbf{x} + q\mathbf{u}) \\
&= q^{k-d} \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} (F(\alpha, \mathbb{Z}^d) - F(\alpha, q\mathbb{Z}^d))
\end{align*}
$$

where $F(\alpha, X) = \sum_{\mathbf{x} \in X : \mathbf{x} \in B_d^p(\ell)} \sum_{\mathbf{u} \in \mathbb{Z}^d : \alpha \mathbf{x} + q\mathbf{u} \in B_d^p(\ell)} \rho_s(\mathbf{x}) \rho_s(\alpha \mathbf{x} + q\mathbf{u})$. By Lemma 3, $F(\alpha, \mathbb{Z}^d) \le \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(\ell))$ for any $\alpha \in \mathbb{Z}_q \setminus \{0\}$ since $\ell < q/2$. Furthermore, $F(\alpha, q\mathbb{Z}^d) = 1$ since the only term in the sum is $\mathbf{x} = \mathbf{u} = 0$ due to the constraint that $\ell \le q$. Finally, we get that

$$
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [\rho_s(L \cap B_d^p(\ell))] \le q^{k-d}(q-1) \left( \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(\ell)) - 1 \right).
$$

For the lower bound, note that by Remark 2, we have that $F(1, \mathbb{Z}^d) \ge \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(\ell))$ and therefore

$$
\begin{align*}
\mathbb{V}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [\rho_s(L \cap B_d^p(\ell))] &= (q^{k-d} - q^{2(k-d)}) \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} (F(\alpha, \mathbb{Z}^d) - F(\alpha, q\mathbb{Z}^d)) \\
&= (q^{k-d} - q^{2(k-d)}) \sum_{\alpha \in \mathbb{Z}_q \setminus \{0\}} (F(\alpha, \mathbb{Z}^d) - 1) \\
&\ge (q^{k-d} - q^{2(k-d)})(F(1, \mathbb{Z}^d) - 1) \\
&\ge (q^{k-d} - q^{2(k-d)}) \left( \rho_{s/\sqrt{2}}(B_d^{p,\mathbb{Z}}(\ell)) - 1 \right).
\end{align*}
$$

□

Remark 8. The upper bound on the variance is essentially optimal when $q^{d-k}$ is large since in that case the lower bound matches the upper bound, up to a factor of $q$.

**Corollary 3.** For any $d \in \mathbb{N}$, $1 \le k \le d$, an odd prime number $q$, $0 \le \ell < q/2$ and $s > 0$,

$$
\mathrm{Pr}_{L \sim \mathcal{L}_{d,k,q}^{\perp}} [|\rho_s(L \cap B_d^p(\ell)) - 1 - \mu_{s,\ell}| > \alpha] \le q \cdot \frac{\mu_{s,\ell}}{\alpha^2}.
$$

where $\mu_{s,l} = q^{k-d} \rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\})$.
Proof. This is a direct application of Lemma 9 and Chebyshev's inequality. □

# 5 Application to the SIS problem

In this section, we apply the results of the previous section to solve the SIS problem. The algorithm is simple: given access to a Gaussian sampler, we sample many vectors and estimate the probability to obtain a short enough vector. The analysis, however, is not trivial and requires to estimate, in particular, the Gaussian mass of a random q-ary lattice and the Gaussian mass of a random q-ary lattice intersected with a ball. An interesting side-effect of this approach is that we can handle an arbitrary $\ell_p$-norm, including $p = \infty$.

Before going to the main result, it is worth making some remarks on the parameters. Consider $\text{SIS}_{d-k,d,q,\ell}^p$ for some $d, q \in \mathbb{N}$, $1 \le k \le d$ and $\ell > 0$. This is equivalent (Section 2.3) to finding a nonzero vector in $L \cap B_n^p(\ell)$ with $L \sim \mathcal{L}_{d,k,q}^1$. Most such lattices satisfy [29, Corollary 2] that

$$ \lambda_1(L) \approx \text{GH}(L) = \text{vol}(L)^{1/d} \sqrt{\frac{d}{2\pi e}} = q^{1-k/d} \sqrt{\frac{d}{2\pi e}} $$

since $\text{vol}(L) = q^{d-k}$ with probability close to 1. In particular, this means that the $\text{SIS}_{d-k,d,q,\ell}^p$ problem only makes sense for

$$ \ell = \alpha q^{1-k/d} \sqrt{\frac{d}{2\pi e}} \quad \text{and} \quad \alpha \ge 1. \qquad (4) $$

In cryptographic applications, we do not expect $\alpha$ to be too close to 1 since this would essentially be equivalent to the SVP problem. Nevertheless, $\alpha$ can still be a relatively small constant such as in the Kyber and Dilithium cryptosystems (Section 5.2) where $\alpha$ varies between 4 and 16 depending on the security level.

Our algorithm works by sampling vectors from the discrete Gaussian distribution until we get a short enough one. Since sampling is harder for smaller values of $s$, we do not want the value of $s$ to be too small. On the other hand, a higher value of $s$ means that samples will be longer on average, hence increasing the expected number of samples before obtaining a sufficiently short one. Therefore, there is a nontrivial trade-off between the complexity of the sampler and the number of samples. Recall that the expected length of such a vector sampled from the discrete Gaussian at width $s$ is $s\sqrt{\frac{d}{2\pi}}$. We want this quantity to be at least equal to $\ell$, so by (4), we always want to take

$$ s \ge \frac{\alpha}{\sqrt{e}} q^{1-k/d}. \qquad (5) $$

## 5.1 General result

In this section, we give a general statement on the complexity of the algorithm and its probability of success. Informally, our result says that if we have access
to a Gaussian sampler at width $s$ then there is an algorithm which solves $\text{SIS}_{...,\ell}^p$ and whose complexity essentially depends on the quantity

$$ \frac{\rho_s(B_d^{p,\mathbb{Z}}(\ell))}{\rho_s(\mathbb{Z}^d)}, $$

that is the Gaussian weight of the $\ell_p$-ball of radius $\ell$. The formal statement below is significantly more complicated and an informal explanation of the quantities appearing in the theorem is available below in Remark 9.

**Theorem 4.** Assume that Conjecture 1 holds. There is a randomized algorithm that for every $p \in [1, \infty]$, $d \in \mathbb{N}$, $1 \le k \le d$, odd prime number $q$, $s > 0$ and $0 \le \ell < q/2$, and on a fraction at least $1 - \varepsilon_{s,\ell} - \frac{\theta_s}{\nu_s^2}$ of random lattices $L$ according to $\mathcal{L}_{d,k,q}^1$, outputs in time $N\text{poly}(d)$ and polynomial space a nonzero vector of $L$ of $\ell_p$-norm at most $\ell$ with probability at least $1/2$, where

$$ \begin{aligned} N &= \Omega(1/x), & x &= \frac{\mu_{s,\ell}}{4\nu_s}, \\ \nu_s &= \rho_{s/q}(\mathbb{Z}^d) + q^{k-d}\rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d), & \varepsilon_{s,\ell} &= \frac{4q}{\mu_{s,\ell}}, \\ \theta_s &= q^{1+k-d}\rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d), & \mu_{s,\ell} &= q^{k-d}\rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\}). \end{aligned} $$

This algorithm requires access to a discrete Gaussian sampler for $L$ at width $s$ and makes $N$ queries to the sampler. In particular, this algorithm solves $\text{SIS}_{d-k,d,q,\ell}^p$ on a fraction at least $1 - \varepsilon_{s,\ell} - \frac{\theta_s}{\nu_s^2}$ of random lattices.

**Remark 9 (Informal description of the result).** Let us describe some of quantities appearing above and give some intuitions about their behaviour.

- $\mu_{s,\ell}$ is the Gaussian mass of the ball of radius $\ell$ multiplied by $q^{k-d}$. For large enough $\ell$, this quantity grows as $\ell^d q^{k-d}$ and $\ell \ge \sqrt{\frac{d}{2\pi e}} q^{1-k/d}$ by (4), making $\mu_{s,\ell}$ super-exponentially large in $d$.

- $\varepsilon_{s,\ell}$ measures the probability that a particular lattice $L$ is “bad” and that the algorithm will fail on it. By the above reasoning for $\mu_{s,\ell}$, we expect $\varepsilon_{s,\ell}$ to be negligible.

- $\nu_s$ is the expected value of the Gaussian mass of a random $q$-ary lattice.

*Proof.* Let $N$ to be fixed later. Consider the following algorithm:

- Sample $N$ vectors independently according to $D_{L,s}$.

- Return the shortest nonzero vector.

We will analyze this algorithm. First the running time is clearly $N\text{poly}(d)$ with $N$ queries to the sampler, and it only needs to store the shortest vector found so far. It remains to analyze the correctness.

Let $\mu_{s,\ell} = q^{k-d}\rho_s(B_d^{p,\mathbb{Z}}(\ell) \setminus \{0\})$. By Corollary 3 for $\alpha = \frac{\mu_{s,\ell}}{2}$, and with probability at least $1 - \varepsilon_{s,\ell}$ where $\varepsilon_{s,\ell} = q^{\frac{\mu_{s,\ell}}{\alpha^2}} = \frac{4q}{\mu_{s,\ell}}$ over the choice of $L$ we have

$$ |\rho_s(L \cap B_d^p(\ell)) - 1 - \mu_{s,\ell}| < \alpha $$
so in particular

$$ \rho_s(L \cap B_d^p(\ell)) \ge 1 + \mu_{s,\ell} - \alpha = 1 + \frac{\mu_{s,\ell}}{2}. \quad (6) $$

Let $\nu_s = \rho_{s/q}(\mathbb{Z}^d) + q^{k-d}\rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d)$ and $\theta_s = q^{1+k-d}\rho_{s\sqrt{2}/q}(\mathbb{Z}^d)\rho_{s/\sqrt{2}}(\mathbb{Z}^d)$. By Corollary 1 for $\beta = \nu_s$, and with probability at least $1 - \frac{\theta_s}{\beta^2}$ over the choice of $L$ we have

$$ |\rho_s(L) - \nu_s| < \nu_s $$

so in particular

$$ \rho_s(L) \le 2\nu_s. \quad (7) $$

By a union-bound, we get that (6) and (7) hold simultaneously with probability at least $1 - \varepsilon_{s,\ell} - \frac{\theta_s}{\nu_s}$. In particular, we have that

$$ \frac{\rho_s((L \setminus \{0\}) \cap B_d^p(\ell))}{\rho_s(L)} \ge x := \frac{\mu_{s,\ell}}{4\nu_s}. $$

We can now analyze the algorithm: since the samples are independent, the probability that each sample is non-zero and of length at most $\ell$ is $x$. Therefore if $N = \Omega(1/x)$, then with constant probability we will get a nonzero vector in $L \cap B_d^p(\ell)$. $\square$

The previous result is not easy to use because it depends on many nontrivial quantities to estimate, such as $\rho_{s/\sqrt{2}}(\mathbb{Z}^d)$. For precise values of all parameters, these quantities can be evaluated with good precision, but it makes it difficult to understand the behaviour in general. The next theorems gives asymptotic values for the parameters in a regime of interest of cryptography, for $p = 2$ and $p = \infty$ which are the two cases of most practical interest.

**Theorem 5.** Let $q := q(d)$, $k := k(d)$, $s := s(d)$ and $\ell := \ell(d)$ be such that $s = \omega(\log \sqrt{d})$, $q/s = \omega(\log \sqrt{d})$, $s > q^{1-k/d}$, $q = 2^{o(d)}$, and $\ell = \omega(1)$ as $d \to \infty$. Then the algorithm from Theorem 4 solves $\text{SIS}_{d-k,d,q,\ell}^{\infty}$ on a fraction at least $1 - \frac{q^{1+d-k}}{s^d \operatorname{erf}\left(\frac{\ell\sqrt{\pi}}{s}\right)^d} - 2^{-d/2+o(d)}$ of random lattices $L \sim \mathcal{L}_{d,k,q}^{\perp}$ using $N = \frac{e^{o(d)}}{\operatorname{erf}\left(\frac{\ell\sqrt{\pi}}{s}\right)^d}$ calls to a Gaussian sampler for $L$ at width $s$.

*Proof.* In what follows, we use notations from Theorem 4. By our assumption that $s = \omega(\sqrt{d})$ and that $q/s = \omega(\log \sqrt{d})$ and Lemma 5 it follows that

$$ \begin{aligned} \rho_s(\mathbb{Z})^d &= s^d(1 + o(1)), & \rho_{s/\sqrt{2}}(\mathbb{Z})^d &= s^d 2^{-d/2}(1 + o(1)), \\ \rho_{s/q}(\mathbb{Z})^d &= 1 + o(1), & \rho_{s\sqrt{2}/q}(\mathbb{Z})^d &= 1 + o(1). \end{aligned} $$

Therefore

$$ \theta_s = q^{1+k-d} \rho_{s\sqrt{2}/q}(\mathbb{Z}^d) \rho_{s/\sqrt{2}}(\mathbb{Z}^d) $$
$$ = q^{1+k-d} 2^{-d/2} s^d (1 + o(1)) $$

and

$$ \begin{aligned} \nu_s &= \rho_{s/q}(\mathbb{Z}^d) + q^{k-d} \rho_s(\mathbb{Z}^d \setminus q\mathbb{Z}^d) \\ &= 1 + o(1) + q^{k-d} s^d (1 + o(1)) \\ &= q^{k-d} s^d (1 + o(1)) \end{aligned} $$

where the last step comes from the fact that $s > q^{1-k/d}$. It follows that

$$ \frac{\theta_s}{\nu_s^2} = 2^{-d/2} q(1 + o(1)) \le 2^{-d/2 + o(d)} $$

since $q = 2^{o(d)}$. Furthermore, by Lemma 4,

$$ \begin{aligned} \mu_{s,\ell} &= q^{k-d} \rho_s(B_n^{\infty,\mathbb{Z}}(\ell) \setminus \{0\}) \\ &= q^{k-d} (\rho_s([-\ell, \ell] \cap \mathbb{Z})^d - 1) \\ &\le q^{k-d} \left( \left( 1 + s \operatorname{erf} \left( \frac{\ell\sqrt{\pi}}{s} \right) \right)^d - 1 \right). \end{aligned} $$

We now claim that $s \operatorname{erf}(\frac{\ell\sqrt{\pi}}{s}) = \Omega(\ell)$. Indeed$^\dagger$, if $\ell = o(s)$ then $s \operatorname{erf}(\frac{\ell\sqrt{\pi}}{s}) \sim s \frac{2}{\sqrt{x}} \frac{\ell\sqrt{\pi}}{s} = 2\ell$, and if $\ell = \Omega(s)$ then $s \operatorname{erf}(\frac{\ell\sqrt{\pi}}{s}) = \Omega(s) = \Omega(\ell)$ by the properties of the erf function. since $\ell = \omega(1)$, it follows that

$$ \mu_{s,\ell} = q^{k-d} s^d \operatorname{erf} \left( \frac{\ell\sqrt{\pi}}{s} \right)^d e^{o(d)}. $$

and

$$ p = \frac{\mu_{s,\ell}}{4\nu_s} = \operatorname{erf}\left(\frac{\ell\sqrt{\pi}}{s}\right)^d e^{o(d)}. $$

Finally,

$$ \varepsilon_{s,\ell} = \frac{4q}{\mu_{s,\ell}} = \frac{q^{1+d-k}}{s^d \operatorname{erf}\left(\frac{\ell\sqrt{\pi}}{s}\right)^d e^{o(d)}}. $$

□

**Theorem 6.** Let $q := q(d)$, $k := k(d)$, $s := s(d)$ and $\ell := \ell(d)$ be such that $s = \omega(\log \sqrt{d})$, $q/s = \omega(\log \sqrt{d})$, $s > q^{1-k/d}$, $q = 2^{o(d)}$, $\ell^2 \le \frac{d(s^2+\pi-\sqrt{\pi^2+2\pi s^2})}{2\pi}$ and $\ell = \omega(\sqrt{d})$ as $d \to \infty$. Then the algorithm from Theorem 4 solves $\text{SIS}_{d-k,d,q,\ell}^2$ on a fraction at least $1-q^{1+d-k}e^{\pi\ell^2/s^2+o(d)}(\frac{d}{2\pi e \ell^2})^{d/2}$ of random lattices $L \sim \mathcal{L}_{d,k,q}^\perp$ using $N = e^{\pi\ell^2/s^2+o(d)}(\frac{ds^2}{2\pi e \ell^2})^{d/2}$ calls to a Gaussian sampler for $L$ at width $s$.

<footnote>$^\dagger$ Here to simplify the proof, we are assuming that either $\ell = o(s)$ or $\ell = \Omega(s)$. This is not technically always true but a more formal reasoning can be done if necessary to obtain the same result.</footnote>
Proof. In what follows, we use notations from Theorem 4. By the same reasoning as in Theorem 5, we have that

$$
\begin{align*}
\rho_s(\mathbb{Z})^d &= s^d(1 + o(1)), & \rho_{s/\sqrt{2}}(\mathbb{Z})^d &= s^d 2^{-d/2}(1 + o(1)), \\
\rho_{s/q}(\mathbb{Z})^d &= 1 + o(1), & \rho_{s\sqrt{2}/q}(\mathbb{Z})^d &= 1 + o(1)
\end{align*}
$$

and

$$
\nu_s = q^{k-d} s^d (1 + o(1)), \quad \frac{\theta_s}{\nu_s^2} \le 2^{-d/2 + o(d)}.
$$

Furthermore, by Lemma 6,

$$
\begin{align*}
\mu_{s,\ell} &= q^{k-d} \rho_s(B_n^{2,\mathbb{Z}}(\ell) \setminus \{0\}) \\
&\ge q^{k-d\ell d} e^{-\pi\ell^2/s^2} \left(\frac{2\pi e}{d}\right)^{d/2} e^{o(d)}.
\end{align*}
$$

Therefore

$$
p = \frac{\mu_{s,\ell}}{4\nu_s} \ge \left(\frac{\ell}{s}\right)^d e^{-\pi\ell^2/s^2} \left(\frac{2\pi e}{d}\right)^{d/2} e^{o(d)}.
$$

Finally,

$$
\varepsilon_{s,\ell} = \frac{4q}{\mu_{s,\ell}} \le \frac{q}{q^{k-d\ell d} e^{-\pi\ell^2/s^2} \left(\frac{2\pi e}{d}\right)^{d/2} e^{o(d)}}.
$$

□

5.2 Application to Dilithium

The parameter of SIS∞ for the Dilithium signature scheme [17] can be found in
Figure 3.

We have applied Theorem 4 to those instances. In order to do so, we use the MCMC Gaussian sampler (Theorem 2) from [37] on a β-BKZ reduced basis of the lattice. The complexity of this sampler can be estimated (Theorem 3) using [31] and the complexity of BKZ using standard results in the literature. A key factor affecting the choice of the sampler is that we need to be able to sample the discrete Gaussian distribution at relatively low width (s). Samplers such as the Klein sampler run in polynomial time but place a limit to how small s can be depending on the reduction quality of the basis (see Section 2.5). This is not ideal for our attack because it does not give a lot of freedom in the choices of parameters and leads to poor attack complexities. The MCMC sampler, in contrast, allows us to sample at arbitrary values s at the cost of a higher sampling time. This opens up more interesting choices where we can lower s, resulting a smaller number of required samples (N) but an increased cost of producing each sample.

Since the choice of $\beta$ and $s$ is not clear, we wrote an optimizer to find the
optimal choice in each instance. The results are given in Figure 4. We recall that
these estimates rely on the GSA and also ignore polynomial factors, therefore
those figures should be taken as rough estimates of the complexity of the problem.
<table><caption>Fig. 3. SIS$^{∞}$ parameters for the Dilithium.</caption><thead><tr><th>NIST Level</th><th>m</th><th>n</th><th>q</th><th>l</th></tr></thead><tbody><tr><td>2</td><td>256 · 9</td><td>256 · 4</td><td>8380417</td><td>350209</td></tr><tr><td>3</td><td>256 · 12</td><td>256 · 6</td><td>8380417</td><td>724481</td></tr><tr><td>5</td><td>256 · 16</td><td>256 · 8</td><td>8380417</td><td>769537</td></tr></tbody></table>

<table><thead><tr><th>Scheme</th><th>log<sub>2</sub> T<sub>attack</sub></th><th>β</th><th>s</th><th>log<sub>2</sub> N</th><th>log<sub>2</sub> T<sub>sample</sub></th><th>log<sub>2</sub> T<sub>BKZ</sub></th></tr></thead><tbody><tr><td>NIST Level 2</td><td>202</td><td>609</td><td>346702</td><td>39</td><td>159</td><td>201</td></tr><tr><td>NIST Level 3</td><td>289</td><td>919</td><td>723749</td><td>55</td><td>230</td><td>288</td></tr><tr><td>NIST Level 5</td><td>400</td><td>1314</td><td>769533</td><td>74</td><td>323</td><td>400</td></tr></tbody></table>

Fig. 4. Estimated time cost of our attack on SIS$^{∞}$ for Dilithium. The $T_{sample}$ column corresponds to the cost of the MCMC sampler (to produce one sample) and $T_{BKZ}$ is the cost of reducing the basis. $N$ is the number of Gaussian samples used by the attack. The total cost of the attack is $T_{attack} = T_{BKZ} + N \cdot T_{sample}$, ignoring polynomial factors. Note that $T_{BKZ} \approx N \cdot T_{sample}$ in the results, meaning that the cost of BKZ is roughly balanced with the total cost of sampling the vectors. Columns $β$ and $s$ give the parameters of the attacks (BKZ block size and width of the Gaussian sampler).

## References

1. Lattice Attacks on NTRU and LWE: A History of Refinements, p. 15–40. London Mathematical Society Lecture Note Series, Cambridge University Press (2021)

2. Aggarwal, D., Chen, Y., Kumar, R., Shen, Y.: Improved (provable) algorithms for the shortest vector problem via bounded distance decoding. In: Bläser, M., Mon- mege, B. (eds.) 38th International Symposium on Theoretical Aspects of Com- puter Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 187, pp. 4:1–4:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.4

3. Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the short- est vector problem in 2$^n$ time using discrete gaussian sampling: Extended abstract. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. pp. 733–742. ACM (2015). https://doi.org/10.1145/2746539. 2746606

4. Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Com- puting. p. 99–108. STOC ’96, Association for Computing Machinery, New York, NY, USA (1996). https://doi.org/10.1145/237814.237838, https://doi.org/ 10.1145/237814.237838

5. Ajtai, M.: The shortest vector problem in l2 is np-hard for randomized reductions (extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. p. 10–19. STOC ’98, Association for Computing Machinery, New York, NY, USA (1998). https://doi.org/10.1145/276698.276705
6. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Journal of Mathematical Cryptology 9, 169 – 203 (2015), https://github.com/malb/lattice-estimator

7. Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296, 625–635 (1993)

8. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. pp. 10–24. SIAM (2016). https://doi.org/10.1137/1.9781611974331.CH2, https://doi.org/10.1137/1.9781611974331.ch2

9. Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. p. 575–584. STOC ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2488608.2488680

10. Chen, Y., Liu, Q., Zhandry, M.: Quantum algorithms for variants of average-case lattice problems via filtering. In: Advances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 – June 3, 2022, Proceedings, Part III. p. 372–401. Springer-Verlag, Berlin, Heidelberg (2022). https://doi.org/10.1007/978-3-031-07082-2_14, https://doi.org/10.1007/978-3-031-07082-2_14

11. Chen, Y.: Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. Ph.D. thesis (2013), http://www.theses.fr/2013PA077242, thèse de doctorat dirigée par Nguyen, Phong Q. Informatique Paris 7 2013

12. Chuengsatiansup, C., Prest, T., Stehlé, D., Wallet, A., Xagawa, K.: Modfalcon: Compact signatures based on module-ntru lattices. In: Proceedings of the 15th ACM Asia Conference on Computer and Communications Security. p. 853–866. ASIA CCS ’20, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3320269.3384758, https://doi.org/10.1145/3320269.3384758

13. Chung, K.M., Dadush, D., Liu, F.H., Peikert, C.: On the lattice smoothing parameter problem. In: 2013 IEEE Conference on Computational Complexity. pp. 230–241 (2013). https://doi.org/10.1109/CCC.2013.31

14. Dadush, D., Regev, O., Stephens-Davidowitz, N.: On the closest vector problem with a distance guarantee. In: 2014 IEEE 29th Conference on Computational Complexity (CCC). pp. 98–109 (2014). https://doi.org/10.1109/CCC.2014.18

15. Ducas, L., Engelberts, L., Loyer, J.: Wagner’s algorithm provably runs in subexponential time for SIS$^{∞}$. In: Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part I. p. 353–384. Springer-Verlag, Berlin, Heidelberg (2025). https://doi.org/10.1007/978-3-032-01855-7_12, https://doi.org/10.1007/978-3-032-01855-7_12

16. Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: Crystals-dilithium algorithm specifications and supporting documentation (2017), https://apisemanticscholar.org/CorpusID:198994007

17. Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: Crystals-dilithium: A lattice-based digital signature scheme. Transactions on Cryptographic Hardware and Embedded Systems 2018, Issue 1,
238-268 (2018). https://doi.org/10.13154/tches.v2018.i1.238-268, https://tches.iacr.org/index.php/TCHES/article/view/839

18. Erez, U., Litsyn, S., Zamir, R.: Lattices which are good for (almost) everything. IEEE Transactions on Information Theory 51(10), 3401-3416 (2005). https://doi.org/10.1109/TIT.2005.855591

19. Espitau, T., Joux, A., Kharchenko, N.: On a Dual/Hybrid Approach to Small Secret LWE: A Dual/Enumeration Technique for Learning with Errors and Application to Security Estimates of FHE Schemes. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) Progress in Cryptology – INDOCRYPT 2020, vol. 12578, p. 440–462. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_20, series Title: Lecture Notes in Computer Science

20. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. p. 197–206. STOC ’08, Association for Computing Machinery, New York, NY, USA (2008). https://doi.org/10.1145/1374376.1374407

21. Hanrot, G., Pujol, X., Stehlé, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference. Lecture Notes in Computer Science, vol. 6841, p. 441. Springer (2011). https://doi.org/10.1007/978-3-642-22792-9_25, https://www.iacr.org/archive/crypto2011/68410441/68410441.pdf

22. Kirshanova, E., Nguyen, H., Stehlé, D., Wallet, A.: On the smoothing parameter and last minimum of random orthogonal lattices. Des. Codes Cryptogr. 88(5), 931–950 (2020). https://doi.org/10.1007/S10623-020-00719-W, https://doi.org/10.1007/s10623-020-00719-w

23. Klein, P.: Finding the closest lattice vector when it’s unusually close. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. p. 937–941. SODA ’00, Society for Industrial and Applied Mathematics, USA (2000)

24. Li, J., Nguyen, P.Q.: A complete analysis of the BKZ lattice reduction algorithm. IACR Cryptol. ePrint Arch. p. 1237 (2020), https://eprint.iacr.org/2020/1237

25. Ling, C., Luzzi, L., Belfiore, J.C., Stehlé, D.: Semantically secure lattice codes for the gaussian wiretap channel. IEEE Transactions on Information Theory 60(10), 6399–6416 (2014). https://doi.org/10.1109/TIT.2014.2343226

26. Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-lwe cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Cryptology – EUROCRYPT 2013. pp. 35–54. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)

27. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. In: 45th Annual IEEE Symposium on Foundations of Computer Science. pp. 372–381 (2004). https://doi.org/10.1109/FOCS.2004.72

28. Micciancio, D., Regev, O.: Lattice-based Cryptography, pp. 147–191. Springer Berlin Heidelberg, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_5

29. Pouly, A., Shen, Y.: Provable dual attacks on learning with errors. In: Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26–30, 2024, Proceedings, Part VII. p. 256–285. Springer-Verlag, Berlin, Heidelberg (2024). https://doi.org/10.1007/978-3-031-58754-2_10, https://doi.org/10.1007/978-3-031-58754-2_10

30. Pouly, A., Shen, Y.: Solving the shortest vector problem in $2^{0.63269n+o(n)}$ time on random lattices. Cryptology ePrint Archive, Paper 2024/1805 (2024), https://eprint.iacr.org/2024/1805
31. Pouly, A., Shen, Y.: Discrete gaussian sampling for bkz-reduced basis. In: Post-Quantum Cryptography: 16th International Workshop, PQCrypto 2025, Taipei, Taiwan, April 8–10, 2025, Proceedings, Part II. p. 63–88. Springer-Verlag, Berlin, Heidelberg (2025). https://doi.org/10.1007/978-3-031-86602-9_3, https://doi.org/10.1007/978-3-031-86602-9_3

32. Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. pp. 145–156. Springer Berlin Heidelberg, Berlin, Heidelberg (2003)

33. Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53(2), 201–224 (jun 1987)

34. Stehlé, D., Steinfeld, R.: Making ntru as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) Advances in Cryptology – EUROCRYPT 2011. pp. 27–47. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

35. Stephens-Davidowitz, N.: On the Gaussian measure over lattices. Phd thesis, New York University (2017)

36. Wang, Z., Ling, C.: Lattice gaussian sampling by markov chain monte carlo: Bounded distance decoding and trapdoor sampling. IEEE Transactions on Information Theory 65(6), 3630–3645 (2019). https://doi.org/10.1109/TIT.2019.2901497

37. Wang, Z., Ling, C.: Lattice gaussian sampling by markov chain monte carlo: Bounded distance decoding and trapdoor sampling. IEEE Transactions on Information Theory 65(6), 3630–3645 (2019). https://doi.org/10.1109/TIT.2019.2901497

38. Zamir, R., Nazer, B., Kochman, Y., Bistritz, I.: Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation and Multisuser Information Theory. Cambridge University Press (2014). https://doi.org/10.1017/CBO9781139045520