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

Elena Kirshanova, Huyen Nguyen, 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].

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Designs, Codes and Cryptography
DOI
10.1007/s10623-020-00719-w
Keywords
random latticeslast minimumsmoothing parameterlattice-based cryptographylattices and convex bodies
Contact author(s)
elenakirshanova @ gmail com
damien stehle @ gmail com
nthuyen math @ gmail com
wallet alexandre @ gmail com
History
Short URL
https://ia.cr/2020/057

CC BY

BibTeX

@misc{cryptoeprint:2020/057,
author = {Elena Kirshanova and Huyen Nguyen and Damien Stehlé and Alexandre Wallet},
title = {On the smoothing parameter and last minimum of random orthogonal lattices},
howpublished = {Cryptology ePrint Archive, Paper 2020/057},
year = {2020},
doi = {10.1007/s10623-020-00719-w},
note = {\url{https://eprint.iacr.org/2020/057}},
url = {https://eprint.iacr.org/2020/057}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.