Cryptology ePrint Archive: Report 2019/029

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 ]