Measure inequalities and the transference theorem in the geometry of numbers

Tian, Chengliang; Liu, Mingjie; Xu, Guangwu

doi:10.1090/S0002-9939-2013-11744-2

Measure inequalities and the transference theorem in the geometry of numbers
HTML articles powered by AMS MathViewer

by Chengliang Tian, Mingjie Liu and Guangwu Xu PDF

Proc. Amer. Math. Soc. 142 (2014), 47-57 Request permission

Abstract:

The measure inequalities of Banaszczyk have been important tools in applying discrete Gaussian measure over lattices to lattice-based cryptography. This paper presents an improvement of Banaszczyk’s inequalities and provides a concise and transparent proof. This paper also generalizes the transference theorem of Cai to general convex bodies. The bound is better than that obtained by simply generalizing the $l_2$ norm using the canonical norm inequalities.

References

Dorit Aharonov and Oded Regev. A lattice problem in quantum NP. In Proceedings of FOCS 2003, pages 210-219.
Dorit Aharonov and Oded Regev, Lattice problems in $\rm NP\cap coNP$, J. ACM 52 (2005), no. 5, 749–765. MR 2176561, DOI 10.1145/1089023.1089025
W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), no. 4, 625–635. MR 1233487, DOI 10.1007/BF01445125
W. Banaszczyk, Inequalities for convex bodies and polar reciprocal lattices in $\textbf {R}^n$, Discrete Comput. Geom. 13 (1995), no. 2, 217–231. MR 1314964, DOI 10.1007/BF02574039
W. Banaszczyk, Inequalities for convex bodies and polar reciprocal lattices in $\mathbf R^n$. II. Application of $K$-convexity, Discrete Comput. Geom. 16 (1996), no. 3, 305–311. MR 1410163, DOI 10.1007/BF02711514
Jin-Yi Cai, A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor, Discrete Appl. Math. 126 (2003), no. 1, 9–31. Fifth Annual International Computing and Combinatorics Conference (COCOON’99) (Tokyo). MR 1955767, DOI 10.1016/S0166-218X(02)00216-0
Jin-yi Cai, Ajay Nerurkar. An Improved Worst-Case to Average-Case Reduction for Lattice Problems. In Proceedings of FOCS 1997, pp. 468-477.
Daniele Micciancio and Oded Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), no. 1, 267–302. MR 2306293, DOI 10.1137/S0097539705447360
Wolfgang Ebeling, Lattices and codes, Second revised edition, Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Braunschweig, 2002. A course partially based on lectures by F. Hirzebruch. MR 1938666, DOI 10.1007/978-3-322-90014-2
Oded Regev, New lattice-based cryptographic constructions, J. ACM 51 (2004), no. 6, 899–942. MR 2145258, DOI 10.1145/1039488.1039490
Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 84–93. MR 2181605, DOI 10.1145/1060590.1060603