A Note on Banaszczyk's Inequality
This is an incremental improvement to a known inequality that may benefit lattice-based cryptography researchers working on LWE attacks.
The authors improve Banaszczyk's inequality for the discrete Gaussian measure on a lattice, obtaining a significantly better bound under an appropriate condition, which can be applied to dual attacks on the Learning With Errors (LWE) problem.
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.