Abstract
In this paper, we start with a discussion of discrete Gaussian measures on lattices. Several results of Banaszczyk are analyzed, a simple form of uncertainty principle for discrete Gaussian measure is formulated. In the second part of the paper we prove two new bounds for the smoothing parameter of lattices. Under the natural assumption that \(\varepsilon\) is suitably small, we obtain two estimations of the smoothing parameter:
-
1.
$$\begin{aligned} \displaystyle \eta _{\varepsilon }({{\mathbb {Z}}}) \le \sqrt{\frac{\ln \big (\frac{\varepsilon }{44}+\frac{2}{\varepsilon }\big )}{\pi }}. \end{aligned}$$
This is a practically useful case. For this case, our upper bound is very close to the exact value of \(\eta _{\varepsilon }({{\mathbb {Z}}})\) in that \(\sqrt{\frac{\ln \big (\frac{\varepsilon }{44}+\frac{2}{\varepsilon }\big )}{\pi }}-\eta _{\varepsilon }({{\mathbb {Z}}})\le \frac{\varepsilon ^2}{552}\).
-
2.
For a lattice \({{{\mathcal {L}}}}\subset {{\mathbb {R}}}^n\) of dimension n,
$$\begin{aligned} \displaystyle \eta _{\varepsilon }({{{\mathcal {L}}}}) \le \sqrt{\frac{\ln \big (n-1+\frac{2n}{\varepsilon }\big )}{\pi }}\tilde{bl}({{{\mathcal {L}}}}). \end{aligned}$$
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
This means that f and all its (partial) derivatives \(D^{\beta }f\) are rapidly decreasing in the sense that \(\sup _{{\mathbf {x}}\in {{\mathbb {R}}}^n} |{\mathbf {x}}^{\alpha }D^{\beta }f({\mathbf {x}})|<\infty\) for every \(\alpha , \beta \in {{\mathbb {N}}}^n\). Such a function is said to be in the Schwartz space.
References
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(4), 625–635 (1993)
Banaszczyk, W.: Inequalites for convex bodies and polar reciprocal lattices in \({\mathbb{R}}^n\). Discrete Comput. Geom. 13, 217–231 (1995)
Banaszczyk, W.: Inequalities for convex bodies and polar reciprocal lattices in \({\mathbb{R}}^n\) II: application of k-convexity. Discrete Comput. Geom. 16, 305–311 (1996)
Cai, J.: A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. Discrete Appl. Math. 126(1), 9–31 (2003)
Chung, K., Dadush, D., Liu, F., Peikert, C.: On the Lattice Smoothing Parameter Problem. In: IEEE Conference on Computational Complexity, pp. 230–241 (2013)
Donoho, D., Stark, P.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49, 906–931 (1989)
Gentry, C., Peikert, C., Vaikuntanathan, V.: How to use a short basis: trapdoors for hard lattices and wew cryptographic constructions, STOC, pp. 197–206. (2008) (full version: https://eprint.iacr.org/2007/432.pdf)
Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Publishers, Berlin (2002)
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)
Micciancio, D., Walter, M.: Gaussian sampling over the integers: efficient, generic, constant-time. Proc. CRYPTO 2017, 455–485 (2017)
Peikert, C.: Limits on the hardness of lattice problems in \(\ell _p\)-norms. In: IEEE Conference on Computational Complexity, pp 333–346 (2007)
Peikert, C.: An efficient and parallel Gaussian sampler for lattices. Proc. CRYPTO 2010, 80–97 (2010)
Pöppelmann, T., Ducas, L.: Güneysu T, pp. 353–370. Enhanced lattice-based signatures on reconfigurable hardware. In: International Workshop on Cryptographic Hardware and Embedded Systems (2014)
Serre, J-P.: A Course in Arithmetic, GTM 7, Spring (1977)
Stein, E., Shakarchi, R.: Fourier Analysis—An Introduction. Princeton University Press, Princeton (2003)
Tao, T: An uncertainty principle for cyclic groups of prime order, http://xxx.arxiv.cornell.edu/pdf/math.CA/0308286
Tian, C., Liu, M., Xu, G.: Measure inequalities and the transference theorem in the geometry of numbers. Proc. Am. Math. Soc. 142, 47–57 (2014)
Zheng, Z., Wang, X., Xu, G., Zhao, C.: Error Estimation of Practical Convolution Discrete Gaussian Sampling with Rejection Sampling, Science China, [Ser. F], (2019) (to appear). (https://eprint.iacr.org/2018/309)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Zheng, Z., Zhao, C. & Xu, G. Discrete Gaussian measures and new bounds of the smoothing parameter for lattices. AAECC 32, 637–650 (2021). https://doi.org/10.1007/s00200-020-00417-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-020-00417-z