**On the smoothing parameter and last minimum of random orthogonal lattices**

*Elena Kirshanova and Huyen Nguyen and Damien Stehlé and Alexandre Wallet *

**Abstract: **Let $X \in {\mathbb{Z}}^{n \times m}$, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice $\Lambda^\perp(X)$ of $X$, i.e., the set of vectors $\mathbf{v} \in {\mathbb{Z}}^m$ such that $X \mathbf{v}= \mathbf{0}$. In this work, we prove probabilistic upper bounds on the smoothing parameter and the $(m-n)$-th minimum of $\Lambda^\perp(X)$. These bounds improve and the techniques build upon prior works of Agrawal, Gentry, Halevi and Sahai [Asiacrypt'13], and of Aggarwal and Regev [Chicago J. Theoret. Comput. Sci.'16].

**Category / Keywords: **foundations / random lattices, last minimum, smoothing parameter, lattice-based cryptography, lattices and convex bodies

**Original Publication**** (in the same form): **Designs, Codes and Cryptography
**DOI: **10.1007/s10623-020-00719-w

**Date: **received 19 Jan 2020

**Contact author: **elenakirshanova at gmail com,damien stehle@gmail com,nthuyen math@gmail com,wallet alexandre@gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200121:184441 (All versions of this report)

**Short URL: **ia.cr/2020/057

[ Cryptology ePrint archive ]