Cryptology ePrint Archive: Report 2020/057

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

Date: received 19 Jan 2020

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

Available format(s): PDF | BibTeX Citation

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

Short URL:

[ Cryptology ePrint archive ]