A Note on Banaszczyk’s Inequality
arXiv:2605.10461v1 [cs.CR] 11 May 2026
Hongyuan Qu, Chengliang Tian, and Guangwu Xu
Abstract. Banaszczyk’s inequality establishes a tail estimate for the discrete Gaussian measure on a lattice in Rn . This classic result has been influential and plays an important role in lattice-based cryptography. An improvement of the inequality with a transparent proof was given by Tian, Liu and Xu. In this note, we further improve this inequality by imposing an appropriate condition, obtaining a significantly better bound. This refined inequality can be used to investigate dual attacks against the Learning With Errors (LWE) problem.
1
Introduction
Banaszczyk’s inequality, introduced by Banaszczyk in 1993 [2], plays an important role in lattice-based cryptography. In essence, this inequality states that after removing the contribution of some short vectors from a lattice, the remaining Gaussian mass is exponentially small relative to the total Gaussian mass on the lattice. This inequality was originally used to prove the following transference theorem [2]: Theorem 1 (Transference Theorem [2]). Let L ⊂ Rn be an n-dimensional lattice, L∗ its dual, and λi (L) the successive minima of L. Then λi (L)λn−i+1 (L∗ ) ≤ n,
i = 1, . . . , n.
Later, Aharonov and Regev used Banaszczyk’s inequality to prove that certain lattice problems belong to N P ∩ coN P [1]. Their work introduced the idea of using Banaszczyk’s inequality for distinguishing distributions. Recently, Pouly and Shen proposed a framework of provable dual attacks on LWE [3], which was further improved by Qu and Xu [4]. The core of these provable dual attacks is the use of Banaszczyk’s inequality to distinguish between correct and incorrect guesses. In 2014, Tian, Liu, and Xu gave a proof of an improved version of Banaszczyk’s inequality [7] with a more transparent argument. In this note, we restate the proof of this improvement to make it even more accessible. Furthermore, by imposing an additional natural condition on the lattice, we obtain a further improvement of Banaszczyk’s inequality by an exponential factor.
2
Preliminaries
In this section, we present some necessary knowledge for understanding Banaszczyk’s inequality.
For vectors x, y ∈ Rn , their inner product is written as ⟨x, y⟩, and the Euclidean norm of x is ∥x∥. The open ball of radius r > 0 centered at x is defined as B(x, r) = {y ∈ Rn : ∥y − x∥ < r}. A lattice in Rn is a discrete subgroup of the additive group (Rn , +). Discreteness means there exists δ > 0 such that B(0, δ) ∩ L = {0}. Every lattice L ⊂ Rn has a basis: linearly independent vectors b1 , . . . , br ∈ L with L = {u1 b1 + · · · + ur br | u1 , . . . , ur ∈ Z}. The integer r is the rank of L and n is its dimension. L is called full-rank when r = n. The successive minima of L are λi (L) = min {t > 0 | dim (span {v ∈ L | ∥v∥ ≤ t}) ≥ i} , i = 1, . . . , r. The dual lattice of L is L∗ = {u ∈ span(L) : ⟨u, v⟩ ∈ Z for all v ∈ L}, and one has (L∗ )∗ = L. For x ∈ Rn , its distance to L is dist(x, L) = min ∥x − v∥. v∈L
The Fourier transform of a rapidly decreasing smooth function1 h : Rn → R is Z ĥ(w) =
h(x)e−2πi⟨x,w⟩ dx,
w ∈ Rn .
Rn 2
2
For s > 0 and x ∈ Rn , define the Gaussian function ρs (x) = e−π∥x∥ /s . 2 2 Its Fourier transformPis ρ̂s (y) = sn e−πs ∥y∥ = sn ρ1/s (y). For a discrete set S ⊂ Rn , set ρs (S) = v∈S ρs (v). A key tool is the Poisson summation formula, we state it just for the function ρs (x): Lemma 1 (Poisson summation formula [5]). For an n-dimensional lattice L, s > 0, and t ∈ Rn , we have sn ρ1/s (L∗ ). det(L) X sn 2. ρs (L + t) = e2πi⟨t,w⟩ ρ1/s (w). det(L) ∗
1. ρs (L) =
w∈L
1
This means that h and all its (partial) derivatives Dβ h are rapidly decreasing in the sense that supx∈Rn |xα Dβ h(x)| < ∞ for every α, β ∈ Nn . Such a function is said to be in the Schwartz space[6].
2
3
Banaszczyk’s Inequality: Proof and Improvement
In this section, we begin with the classic measure inequality of Banaszczyk [2, Lemma 1.5]. The following statement is taken from [7] (Theorem 3.1 and its remark), which improves Banaszczyk’s inequality by removing the extra factor 2 that appears in the estimate for cosets (i.e., when t ̸= 0). Here we also present a concise proof which makes the argument more accessible. Lemma 2 (Banaszczyk’s inequality, refined version [2, 7]). Let L ⊂ Rn be a lattice of dimension n and s > 0. Then for any c ≥ 1 and t ∈ Rn , ρs
pn (L + t) \ B 0, cs 2π
√ n c2 ≤ c e · e− 2 .
ρs (L) Proof. r n ρs (L+t) \ B 0, cs = 2π
π
X
e− s2 ∥u∥
√n
u∈L+t
∥u∥≥cs
X
=
e
2
− sπ2 (1− c12 )∥u∥2
2π 2
c 2 s2 n
· e− s2 c2 ∥u∥ ≤ e− s2 (1− c2 ) 2π ρsc (L + t) π
π
1
√n
u∈L+t
∥u∥≥cs
2 − c 2−1 n
=e
2π c2 −1 sn cn X 2πi⟨t,w⟩ sn cn X e ρ sc1 (w) ≤ e− 2 n ρ 1s (w) det(L) det(L) ∗ ∗
w∈L
w∈L
2
− c 2−1 n n
=e
c ρs (L). ⊔ ⊓
The result follows since ρs (L) > 0.
Note that the Poisson summation formula is used twice in the preceding proof. As an application of Banaszczyk’s inequality, we introduce the following distinguishing inequality, which plays a crucial role in the formal analysis and parameter selection of provable dual attacks [4]. Corollary 1 (Distinguishing inequality[4, Corollary 1]). Let L ⊂ Rn be pn n an n-dimensional lattice and x ∈ R . Let τ = s 2π and rx = dist(x, L). If rx ≥ τ , then ρs (L + x) rx n n ρs (rx ) ≤ ≤ e 2 ρs (rx ). ρs (x) τ Moreover, the right-hand side is a decreasing function of rx . Proof. Let y ∈ L + x that has minimum norm, then ∥y∥ = rx . 3
The left hand side is a well-known fact ([2, 1]) whose proof is straightforward: using the fact that L is symmetric about the origin, we have 2 π 1 X − π2 ∥v+y∥2 e s + e− s2 ∥v−y∥ ρs (L + x) = 2 v∈L 2π 1 X − π2 ∥v∥2 − π2 ∥y∥2 − 2π2 ⟨v,y⟩ = e s e s + e s2 ⟨v,y⟩ ≥ ρs (L)ρs (rx ). e s 2 v∈L pn . Then rx ≥ τ is equivalent to For the right hand side, write rx = cs 2π √
c ≥ 1. Noting that c = rxs√n2π = rτx , by Lemma 2 we have √ n 2 n ρs (L + x) √ rx e − πr2 x2 rx n n − c2 s n ≤ c e·e = ·e = e 2 ρs (rx ). ρs (L) τ τ √ c2 For c > 1, the expression c e · e− 2 is monotonically decreasing in c, while rx n n increases with c. Consequently, the composite term rτx e 2 ρs (rx ) is monotonically decreasing in rx . ⊔ ⊓ It is natural to take the length of the shortest non-zero vector in our consideration. We impose an additional condition that λ1 (L) is suitably large and obtain the following improved inequality: Lemma 3 (Improved Banaszczyk Inequality). Let L ⊂ Rn be a lattice. pn Assume that λ1 (L) ≥ kcs 2π where k > 1. Then for any c ≥ 1 and t ∈ Rn , n2 2 r e1−c n ≤ , ρs (L + t) \ B 0, cs 2π 1−ϵ √ n k2 where ϵ = k e · e− 2 . Proof. We have r n ρs (L + t) \ B 0, cs = 2π
X
2
e− s2 (1− c2 )∥v∥ · e− s2 c2 ∥v∥ π
1
π
2
v∈L+t √n ∥v∥≥cs 2π
n2 π 1 c 2 s2 n 2 ≤ e− s2 (1− c2 ) 2π · ρsc (L + t) ≤ e1−c · ρsc (L). pn Since λ1 (L) ≥ kcs 2π , using Lemma 2 we obtain pn n ρsc (L\B(0, kcs 2π )) √ k2 ρsc (L) − 1 = ≤ k e · e− 2 . ρsc (L) ρsc (L) √ n k2 1 Let ϵ = k e · e− 2 . For k > 1, ϵ < 1. Then ρsc (L) ≤ 1−ϵ .Thus we have ρs
n r 1−c2 2 n e 2 n 2 (L + t) \ B 0, cs ≤ e1−c · ρsc (L) ≤ . 2π 1−ϵ
⊔ ⊓ 4
Since ρs (L) > 1 for any s > 0, the following is immediate by Lemma 3: n n Corollary p n 2. Let L ⊂ R and psn> 0. Let x ∈ R and rx = dist(x, L). Assume rx ≥ cs 2π and λ1 (L) ≥ kcs 2π for c ≥ 1 and k > 1, then
n2 2 e1−c ρs (L + x) ρs (rx ) ≤ ≤ , ρs (L) 1−ϵ √ n k2 where ϵ = k e · e− 2 . In a typical application, n ≥ 500 (e.g., [3, 4]). The distinguishing inequality can be improved to n Corollary 3 (Improved distinguishing inequality). > 0. p n Let L ⊂ R and sp n n Let x ∈ R and rx = dist(x, L). Assume rx ≥ cs 2π and λ1 (L) ≥ kcs 2π where c ≥ 1 and k ≥ 1.04. Assume n ≥ 500, then
ρs (rx ) ≤
n2 2 ρs (L + x) . ≤ 2 e1−c ρs (L)
Proof. When k ≥ 1.04 and n ≥ 500, we have √ n k2 k e · e− 2 < 0.5. Then the result follows from Corollary 2.
⊓ ⊔
n2 2 Remark 1. Note that in Corollary 3, the term 2 e1−c can be equivalently n
π
2
2 2
expressed as 2e 2 e s2 (rx −r c ) ρs (rx ). Hence, the above improved distinguishing inequality can be written equivalently in the following unified form, where the same factor ρs (rx ) appears on both sides: ρs (rx ) ≤ Observe that
2 2 2 π n ρs (L + x) ≤ 2e 2 e s2 (rx −r c ) ρs (rx ). ρs (L)
n √ c2 c e · e− 2 cn = . n 2 2 e1−c2 2
Here, the numerator is the upper bound given by Banaszczyk inequality. For c > 1, we obtain an improvement of Banaszczyk inequality by an exponential factor.
References 1. Aharonov, D., Regev, O.: Lattice problems in NP ∩ coNP. J. ACM 52(5), 749–765 (Sep 2005), https://doi.org/10.1145/1089023.1089025
5
2. Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296, 625–635 (1993) 3. Pouly, A., Shen, Y.: Provable Dual Attacks on Learning with Errors. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024. pp. 256– 285. Springer Nature Switzerland, Cham (2024), https://doi.org/10.1007/978-3-03158754-2_10 4. Qu, H., Xu, G.: On the Provable Dual Attack for LWE by Modulus Switching. Cryptology ePrint Archive, Paper 2025/859 (2025), https://eprint.iacr.org/2025/859 5. Serre, J.P.: A Course in Arithmetic, vol. 7. Springer Science & Business Media (2012) 6. Stein, E.M., Shakarchi, R.: Fourier analysis: An Introduction, vol. 1. Princeton University Press (2003) 7. Tian, C., Liu, M., Xu, G.: Measure inequalities and the transference theorem in the geometry of numbers. Proceedings of the American Mathematical Society 142(1), 47–57 (2014)
6