Paper 2019/029
Upper Bound on $\lambda_1(\Lambda^{\bot}(\mathbf A))$
Huiwen Jia, 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 upperbounded by a constant. This directly gives us a polytime exhaustive search algorithm for solving the $\mathsf{SIS}$ problem (resulting in approximating certain worstcase 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 latticebased 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.
Metadata
 Available format(s)
  withdrawn 
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 security of latticebased cryptographyshortest vector problemworstcastaveragecase reductionthe smoothing parameter
 Contact author(s)
 hwjia @ gzhu edu cn
 History
 20190123: withdrawn
 20190115: received
 See all versions
 Short URL
 https://ia.cr/2019/029
 License

CC BY