**Upper Bound on $\lambda_1(\Lambda^{\bot}(\mathbf A))$**

*Huiwen Jia and Chunming Tang and Yanhua Zhang*

**Abstract: **It has been shown that, for appropriate parameters, solving the $\mathsf{SIS}$ problem in the average case is at least as hard as approximating certain lattice problems in the worst case %on any $n$-dimensional lattice
to within polynomial factor $\beta\cdot\widetilde{O}(\sqrt n)$, where typically $\beta=O(\sqrt{n\log n})$ such that random $\mathsf{SIS}$ instances admit a solution. In this work, we show that $\beta=O(1)$, i.e., $\beta$ is essentially upper-bounded by a constant. This directly gives us a poly-time exhaustive search algorithm for solving the $\mathsf{SIS}$ problem (resulting in approximating certain worst-case lattice problems to within $\widetilde{O}(\sqrt n)$ factor). Although the exhaustive search algorithm is rather inefficient for typical setting of parameters, our result indicates that lattice-based cryptography is not secure, at least in an asymptotical sense. Our work is based on an observation of the lower/upper bounds on the smoothing parameter for lattices.

**Category / Keywords: **public-key cryptography / security of lattice-based cryptography, shortest vector problem, worst-cast/average-case reduction, the smoothing parameter

**Date: **received 12 Jan 2019, last revised 17 Jan 2019, withdrawn 23 Jan 2019

**Contact author: **hwjia at gzhu edu cn

**Available format(s): **(-- withdrawn --)

**Version: **20190123:094626 (All versions of this report)

**Short URL: **ia.cr/2019/029

[ Cryptology ePrint archive ]