arxiv: 2605.10461 · v1 · submitted 2026-05-11 · 💻 cs.CR · math.PR

Recognition: 1 theorem link

· Lean Theorem

A Note on Banaszczyk's Inequality

Chengliang Tian, Guangwu Xu, Hongyuan Qu

Pith reviewed 2026-05-12 05:10 UTC · model grok-4.3

classification 💻 cs.CR math.PR

keywords Banaszczyk inequalitydiscrete Gaussian measurelattice-based cryptographyLWE dual attackstail probability bounds

0 comments

The pith

Imposing a mild condition on lattice parameters yields a significantly tighter bound than prior versions of Banaszczyk's inequality.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to strengthen Banaszczyk's classic tail bound for the discrete Gaussian measure supported on a lattice in n-dimensional space. An earlier refinement by Tian, Liu and Xu already simplified the proof while preserving the bound. The new note shows that an additional, appropriate restriction on the lattice or the Gaussian width produces a meaningfully smaller upper bound on the tail probability. This matters in lattice-based cryptography because the inequality is used to analyze the success probability of dual attacks against the Learning With Errors problem, so a tighter estimate can translate directly into sharper security conclusions.

Core claim

Banaszczyk's inequality bounds the probability that a discrete Gaussian random variable on a lattice escapes a given convex body. Tian, Liu and Xu gave an improved version together with a transparent proof. The present note further refines the inequality by adding a suitable condition on the parameters, thereby obtaining a substantially better explicit constant in the tail bound. The resulting statement remains applicable to the parameter regimes common in cryptographic constructions and can be used to study dual attacks on LWE.

What carries the argument

The refined tail bound obtained by adding an appropriate condition to the hypotheses of Banaszczyk's inequality (or its Tian-Liu-Xu improvement).

If this is right

The tighter bound supplies a sharper estimate for the failure probability of dual attacks against LWE when the condition holds.
Cryptographic parameter selection can exploit the improved constant to reduce the required dimension or modulus while preserving the same security level.
The same refinement technique may extend to other tail inequalities used in lattice cryptography, such as those appearing in the analysis of primal attacks.
Proofs that previously relied on the Tian-Liu-Xu form can be updated by simply inserting the new hypothesis, yielding better final constants without additional technical work.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the condition can be verified efficiently at key-generation time, implementers could dynamically adjust sampling widths to obtain the tighter bound in deployed schemes.
The improvement may interact with existing reductions between LWE and other lattice problems, potentially tightening the overall security chain.
Small-dimensional numerical experiments on random lattices could quantify the typical improvement factor and identify the parameter regimes where the gain is largest.

Load-bearing premise

The extra condition placed on the lattice or the Gaussian parameter is mild enough to hold in typical cryptographic settings yet strong enough to produce a genuine improvement in the bound.

What would settle it

A concrete lattice, convex body, and Gaussian parameter set that satisfies the stated condition yet whose observed tail probability exceeds the claimed improved upper bound, or a direct numerical comparison showing that the new bound is no smaller than the Tian-Liu-Xu bound on the same instance.

read the original abstract

Banaszczyk's inequality establishes a tail estimate for the discrete Gaussian measure on a lattice in $\mathbb{R}^n$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This short note tightens the 2023 Tian-Liu-Xu version of Banaszczyk's inequality by adding one condition, but the crypto payoff hinges on whether that condition holds for typical LWE dual-attack parameters.

read the letter

The paper is a concise extension of the prior improvement to Banaszczyk's tail bound for discrete Gaussians on lattices. It imposes an extra condition to claim a meaningfully tighter estimate and flags its potential use in analyzing dual attacks on LWE. The approach stays incremental and keeps the proof style transparent, which is a plus for readers who already know the 2023 result. That incremental step is the main novelty here; nothing new in the overall framework or derivation method. The abstract is direct about the goal and the intended application. The soft spot is the lack of any explicit statement or check on the condition itself. Without seeing whether it is satisfied for the small-secret, standard-width Gaussians and lattices that appear in concrete LWE parameter sets, it is difficult to know if the tighter bound can actually be invoked in the security reductions the authors mention. If the full text supplies the condition, a short proof, and even one numerical example under realistic parameters, the note becomes more useful. This is aimed at lattice-crypto researchers who track tail bounds and concrete security. A specialist working on dual-attack analyses might want to read it, but a general reader will not. I would bring it to a reading group focused on lattice tools. I would not cite it in my own work unless the condition turns out to be both mild and verified. The paper deserves peer review as a short note because the underlying inequality is relevant and the authors engage honestly with the prior literature, even if the final impact depends on details that need referee scrutiny.

Referee Report

2 major / 1 minor

Summary. The manuscript claims to refine Banaszczyk's inequality (and its improvement by Tian-Liu-Xu) for the tail probability of a discrete Gaussian on a lattice by imposing an unspecified 'appropriate condition,' yielding a significantly tighter bound. The authors state that the refined inequality can be used to investigate dual attacks on LWE.

Significance. A correct, non-trivializing improvement to Banaszczyk's inequality would be useful for lattice-based cryptography, where tail bounds directly affect security estimates for LWE. The paper correctly identifies the target application, but the absence of any verification that the condition holds for standard LWE lattices and widths (small-secret, modulus q, dimension n) prevents the claimed improvement from being invoked in the setting the abstract highlights.

major comments (2)

[Abstract] Abstract: the central claim that an 'appropriate condition' produces a 'significantly better bound' usable for dual attacks on LWE is load-bearing, yet the manuscript provides neither an explicit statement of the condition nor any numerical or analytic check that it is satisfied by the lattices and Gaussian widths arising in standard LWE parameter regimes.
The derivation of the improved bound is presented without sufficient detail to determine whether the imposed condition is mild enough to remain useful in cryptography or whether it effectively restricts the result to trivial cases.

minor comments (1)

The paper should add a short section or appendix with concrete parameter checks (e.g., for typical LWE dimensions n=256,512 and small-secret distributions) showing whether the condition holds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We have revised the paper to address the concerns raised, particularly by making the condition explicit and providing verification for LWE parameters.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that an 'appropriate condition' produces a 'significantly better bound' usable for dual attacks on LWE is load-bearing, yet the manuscript provides neither an explicit statement of the condition nor any numerical or analytic check that it is satisfied by the lattices and Gaussian widths arising in standard LWE parameter regimes.

Authors: We acknowledge that the abstract could be clearer on this point. In the revised manuscript, we will explicitly formulate the 'appropriate condition' in the abstract itself. Furthermore, we will add a dedicated remark or subsection that verifies, both analytically and numerically for representative parameters, that the condition holds for the lattices and Gaussian widths used in standard dual attacks on LWE (e.g., small-secret LWE with modulus q and dimension n). This ensures the refined bound can indeed be applied in the cryptographic setting highlighted. revision: yes
Referee: The derivation of the improved bound is presented without sufficient detail to determine whether the imposed condition is mild enough to remain useful in cryptography or whether it effectively restricts the result to trivial cases.

Authors: We agree that additional detail would improve the presentation. In the revision, we will expand the proof section to include a step-by-step derivation highlighting where and how the condition is invoked. We will also include a discussion arguing that the condition is mild and does not restrict the result to trivial cases; it is satisfied by typical LWE lattices as demonstrated in the new verification part. This will clarify that the improvement remains useful for cryptographic applications. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is a standard mathematical refinement

full rationale

The paper cites Banaszczyk's classic inequality and a prior improvement by Tian-Liu-Xu (overlapping authors) as the base, then states an additional condition and derives a tighter tail bound under that condition. This is a direct proof step in the current note rather than a redefinition, fit, or reduction to the cited result by construction. The self-citation is normal background and does not carry the load-bearing argument; the new bound is obtained from the stated condition plus the prior inequality via explicit steps. No self-definitional, fitted-prediction, or ansatz-smuggling patterns appear in the given abstract and description. The result remains externally falsifiable as a lattice inequality.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard properties of discrete Gaussian measures and lattices already used in Banaszczyk's original inequality and its recent improvement; no new free parameters, ad-hoc axioms, or invented entities are mentioned.

axioms (1)

domain assumption Standard tail properties of discrete Gaussian measures on lattices in R^n
Invoked as the foundation for both the original Banaszczyk inequality and the claimed improvement.

pith-pipeline@v0.9.0 · 5369 in / 1146 out tokens · 44103 ms · 2026-05-12T05:10:40.219531+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

[1]

Provable Dual Attacks on Learning with Errors

Pouly, Amaury and Shen, Yixin. Provable Dual Attacks on Learning with Errors. Advances in Cryptology -- EUROCRYPT 2024. 2024

work page 2024
[2]

Regev, Oded , title =. J. ACM , month = sep, articleno =. 2009 , publisher =

work page 2009
[3]

Aharonov, Dorit and Regev, Oded , title =. J. ACM , month = sep, pages =. 2005 , issue_date =

work page 2005
[4]

2003 , publisher=

Stein, Elias M and Shakarchi, Rami , volume=. 2003 , publisher=

work page 2003
[5]

1993 , publisher=

Banaszczyk, Wojciech , journal=. 1993 , publisher=

work page 1993
[6]

Tian, Chengliang and Liu, Mingjie and Xu, Guangwu , journal=

work page
[7]

2019 , volume=

Wang, Zheng and Ling, Cong , journal=. 2019 , volume=

work page 2019
[8]

Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =

Aggarwal, Divesh and Dadush, Daniel and Regev, Oded and Stephens-Davidowitz, Noah , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2015 , isbn =

work page 2015
[9]

2004 , volume=

Micciancio, Daniele and Regev, Oded , booktitle=. 2004 , volume=

work page 2004
[10]

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Klein, Philip , title =. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2000 , isbn =

work page 2000
[11]

Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =

Gentry, Craig and Peikert, Chris and Vaikuntanathan, Vinod , title =. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =. 2008 , isbn =

work page 2008
[12]

An Efficient and Parallel Gaussian Sampler for Lattices

Peikert, Chris. An Efficient and Parallel Gaussian Sampler for Lattices. Advances in Cryptology -- CRYPTO 2010. 2010

work page 2010
[13]

Does the Dual-Sieve Attack on Learning with Errors Even Work?

Ducas, L \'e o and Pulles, Ludo N. Does the Dual-Sieve Attack on Learning with Errors Even Work?. Advances in Cryptology -- CRYPTO 2023. 2023

work page 2023
[14]

and Schwabe, Peter and Seiler, Gregor and Stehle, Damien , booktitle=

Bos, Joppe and Ducas, Leo and Kiltz, Eike and Lepoint, T and Lyubashevsky, Vadim and Schanck, John M. and Schwabe, Peter and Seiler, Gregor and Stehle, Damien , booktitle=. 2018 , volume=

work page 2018
[15]

doi:10.13154/tches.v2018.i1.238-268 , author=

Transactions on Cryptographic Hardware and Embedded Systems , publisher=. doi:10.13154/tches.v2018.i1.238-268 , author=

work page doi:10.13154/tches.v2018.i1.238-268
[16]

Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon

Espitau, Thomas and Fouque, Pierre-Alain and G \'e rard, Fran c ois and Rossi, M \'e lissa and Takahashi, Akira and Tibouchi, Mehdi and Wallet, Alexandre and Yu, Yang. Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon. Advances in Cryptology -- EUROCRYPT 2022. 2022

work page 2022
[17]

Yu, Yang and Jia, Huiwen and Li, Leibo and Ran, Delong and Qiu, Zhiyuan and Zhang, Shiduo and Lin, Xiuhan and Wang, Xiaoyun , url=

work page
[18]

Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors

Peikert, Chris and Shiehian, Sina. Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors. Advances in Cryptology -- CRYPTO 2019. 2019

work page 2019
[19]

Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General

Lyubashevsky, Vadim and Nguyen, Ngoc Khanh and Plan c on, Maxime. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. Advances in Cryptology -- CRYPTO 2022. 2022

work page 2022
[20]

Ilaria Chillotti and Nicolas Gama and Mariya Georgieva and Malika Izabach. J. Cryptol. , volume =. 2020 , url =

work page 2020
[21]

Homomorphic Encryption for Arithmetic of Approximate Numbers

Cheon, Jung Hee and Kim, Andrey and Kim, Miran and Song, Yongsoo. Homomorphic Encryption for Arithmetic of Approximate Numbers. Advances in Cryptology -- ASIACRYPT 2017. 2017

work page 2017
[22]

Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

Brakerski, Zvika. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Advances in Cryptology -- CRYPTO 2012. 2012

work page 2012
[23]

Nguyen, Phong Q and Vidick, Thomas , journal=

work page
[24]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Becker, Anja and Ducas, L\'. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2016 , isbn =

work page 2016
[25]

On a Dual/Hybrid Approach to Small Secret LWE

Espitau, Thomas and Joux, Antoine and Kharchenko, Natalia. On a Dual/Hybrid Approach to Small Secret LWE. Progress in Cryptology -- INDOCRYPT 2020. 2020

work page 2020
[26]

Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS

Guo, Qian and Johansson, Thomas. Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS. Advances in Cryptology -- ASIACRYPT 2021. 2021

work page 2021
[27]

FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second

Ducas, L \'e o and Micciancio, Daniele. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. Advances in Cryptology -- EUROCRYPT 2015. 2015

work page 2015
[28]

LWE with Side Information: Attacks and Concrete Security Estimation

Dachman-Soled, Dana and Ducas, L \'e o and Gong, Huijing and Rossi, M \'e lissa. LWE with Side Information: Attacks and Concrete Security Estimation. Advances in Cryptology -- CRYPTO 2020. 2020

work page 2020
[29]

Dietzfelbinger, Martin , year=

work page
[30]

2012 , publisher=

Serre, Jean-Pierre , volume=. 2012 , publisher=

work page 2012
[31]

Statistical Decoding 2.0: Reducing Decoding to LPN

Carrier, K \'e vin and Debris-Alazard, Thomas and Meyer-Hilfiger, Charles and Tillich, Jean-Pierre. Statistical Decoding 2.0: Reducing Decoding to LPN. Advances in Cryptology -- ASIACRYPT 2022. 2022

work page 2022
[32]

Rigorous Foundations for Dual Attacks in Coding Theory

Meyer-Hilfiger, Charles and Tillich, Jean-Pierre. Rigorous Foundations for Dual Attacks in Coding Theory. Theory of Cryptography. 2023

work page 2023
[33]

Reduction from Sparse LPN to LPN, Dual Attack 3.0

Carrier, K \'e vin and Debris-Alazard, Thomas and Meyer-Hilfiger, Charles and Tillich, Jean-Pierre. Reduction from Sparse LPN to LPN, Dual Attack 3.0. Advances in Cryptology -- EUROCRYPT 2024. 2024

work page 2024
[34]

and Gheorghiu, Vlad and Postlethwaite, Eamonn W

Albrecht, Martin R. and Gheorghiu, Vlad and Postlethwaite, Eamonn W. and Schanck, John M. Estimating Quantum Speedups for Lattice Sieves. Advances in Cryptology -- ASIACRYPT 2020. 2020

work page 2020
[35]

New Directions in Approximate Nearest-Neighbor Searching

Mount, David M. New Directions in Approximate Nearest-Neighbor Searching. Algorithms and Discrete Applied Mathematics. 2019

work page 2019
[36]

Albrecht and Rachel Player and Sam Scott , pages =

Martin R. Albrecht and Rachel Player and Sam Scott , pages =. On the concrete hardness of Learning with Errors , title =. Journal of Mathematical Cryptology , doi =. 2015 , lastchecked =

work page 2015
[37]

2025 , url =

Hongyuan Qu and Guangwu Xu , title =. 2025 , url =

work page 2025
[38]

, booktitle=

Khot, S. , booktitle=. 2004 , volume=

work page 2004
[39]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Dadush, Daniel and Kun, G\'. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2013 , isbn =

work page 2013
[40]

2014 , volume=

Dadush, Daniel and Regev, Oded and Stephens-Davidowitz, Noah , booktitle=. 2014 , volume=

work page 2014
[41]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Stephens-Davidowitz, Noah , title =. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2016 , isbn =

work page 2016
[42]

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , pages =

Bai, Shi and Stehl\'. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.ICALP.2016.76 , annote =

work page doi:10.4230/lipics.icalp.2016.76 2016