Paper 2019/029

Upper Bound on λ1(Λ(A))

Huiwen Jia, Chunming Tang, and Yanhua Zhang

Abstract

It has been shown that, for appropriate parameters, solving the 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 βO~(n), where typically β=O(nlogn) such that random SIS instances admit a solution. In this work, we show that β=O(1), i.e., β is essentially upper-bounded by a constant. This directly gives us a poly-time exhaustive search algorithm for solving the SIS problem (resulting in approximating certain worst-case lattice problems to within O~(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.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
security of lattice-based cryptographyshortest vector problemworst-castaverage-case reductionthe smoothing parameter
Contact author(s)
hwjia @ gzhu edu cn
History
2019-01-23: withdrawn
2019-01-15: received
See all versions
Short URL
https://ia.cr/2019/029
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.