Paper 2026/2756

Refined Bounds for the Smoothing Parameter of Lattices

Abstract

The smoothing parameter $\eta_\varepsilon(\Lambda)$ is a fundamental invariant in lattice-based cryptography. Zheng, Zhao, and Xu (AAECC 2021) proved $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{44})/\pi}$ and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln(n - 1 + \frac{2n}{\varepsilon})/\pi}\,\mathrm{bl}(\Lambda)$. Guo, Liu, Wang, and Tian (PLOS One 2025) proposed $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{m})/\pi}$ for $0 < \varepsilon \le \frac{4}{m} - \frac{172}{m^6}$ ($m \ge 3$) and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln((n - 1)(1 + \frac{2}{\varepsilon}))/\pi}\,\mathrm{bl}(\Lambda)$ under $\sqrt{\frac{24n+1}{n^2-1}} \le \varepsilon \le \sqrt{2}-1$. We establish three strictly sharper bounds that uniformly dominate both while removing the artificial lower bound on $\varepsilon$. First, for $0 < \varepsilon \le \rho(\mathbb{Z})-1 \approx 0.086435$, \[ \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4} - \frac{3\varepsilon^5}{32}\right)}{\pi}} < \eta_\varepsilon(\mathbb{Z}) \le \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4}\right)}{\pi}}; \] since Guo et al.'s condition forces $\frac{\varepsilon}{m} > \frac{\varepsilon^2}{4}$, our bound is strictly tighter for all admissible $(\varepsilon, m)$, improving the worst-case gap from $O(\varepsilon^2)$ to $O(\varepsilon^6)$. Second, for all $n \ge 2$ and $0 < \varepsilon < \min\{1, (\rho(\mathbb{Z})-1)n\}$, \[ \eta_\varepsilon(\Lambda) \le \sqrt{\frac{\ln\!\left(\frac{2}{\delta_n} + \frac{\delta_n^2}{4}\right)}{\pi}}\,\mathrm{bl}(\Lambda) < \sqrt{\frac{\ln\!\left(\frac{2n}{\varepsilon} + (n - 1) - \frac{(n^2 - 1)\varepsilon}{6n(1 + \varepsilon)}\right)}{\pi}}\,\mathrm{bl}(\Lambda), \] where $\delta_n = (1+\varepsilon)^{1/n} - 1$; the rational bound is strictly tighter than Guo et al.'s across $100\%$ of their validity window, while remaining valid as $\varepsilon \to 0^+$. Third, for any basis $\mathbf{B}$ with Gram--Schmidt vectors $\mathbf{b}_i^*$ and $M = \max_i \|\mathbf{b}_i^*\|$, define $N_\varepsilon(\mathbf{B}) = \sum_{i=1}^n (\varepsilon/2)^{M^2/\|\mathbf{b}_i^*\|^2 - 1} \in [1, n]$; then \[ \eta_\varepsilon(\Lambda) \le \sqrt{\ln\!\left(\frac{2}{\delta_{\mathrm{eff}}} + \frac{\delta_{\mathrm{eff}}^2}{4}\right)/\pi}\,M, \] where $\delta_{\mathrm{eff}} = \frac{n}{N_\varepsilon(\mathbf{B})}((1+\varepsilon)^{1/n}-1)$. For reduced bases with geometrically decaying Gram--Schmidt lengths, $N_\varepsilon(\mathbf{B}) = O(1)$ is independent of $n$, eliminating the $O(n)$ factor inside the logarithm.

Note: This is a preprint. No prior publication.