Paper 2016/222
TimeMemory TradeOff for Lattice Enumeration in a Ball
Paul Kirchner and PierreAlain Fouque
Abstract
Enumeration algorithms in lattices are a wellknown technique for solving the Short Vector Problem (SVP) and improving blockwise lattice reduction algorithms. Here, we propose a new algorithm for enumerating lattice point in a ball of radius $1.156\lambda_1(\Lambda)$ in time $3^{n+o(n)}$, where $\lambda_1(\Lambda)$ is the length of the shortest vector in the lattice $\Lambda$. Then, we show how this method can be used for solving SVP and the Closest Vector Problem (CVP) with approximation factor $\gamma=1.993$ in a $n$dimensional lattice in time $3^{n+o(n)}$. Previous algorithms for enumerating take superexponential running time with polynomial memory. For instance, Kannan algorithm takes time $n^{n/(2e)+o(n)}$, however ours also requires exponential memory and we propose different time/memory tradeoffs. Recently, Aggarwal, Dadush, Regev and StephensDavidowitz describe a randomized algorithm with running time $2^{n+o(n)}$ at STOC' 15 for solving SVP and approximation version of SVP and CVP at FOCS'15. However, it is not possible to use a time/memory tradeoff for their algorithms. Their main result presents an algorithm that samples an exponential number of random vectors in a Discrete Gaussian distribution with width below the smoothing parameter of the lattice. Our algorithm is related to the hill climbing of Liu, Lyubashevsky and Micciancio from RANDOM' 06 to solve the bounding decoding problem with preprocessing. It has been later improved by Dadush, Regev, StephensDavidowitz for solving the CVP with preprocessing problem at CCC'14. However the latter algorithm only looks for one lattice vector while we show that we can enumerate all lattice vectors in a ball. Finally, in these papers, they use a preprocessing to obtain a succinct representation of some lattice function. We show in a first step that we can obtain the same information using an exponentialtime algorithm based on a collision search algorithm similar to the reduction of Micciancio and Peikert for the SIS problem with small modulus at CRYPTO' 13.
Note: Submitted to ICALP 2016.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Contact author(s)
 paul kirchner @ ens fr
 History
 20160229: received
 Short URL
 https://ia.cr/2016/222
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/222, author = {Paul Kirchner and PierreAlain Fouque}, title = {TimeMemory TradeOff for Lattice Enumeration in a Ball}, howpublished = {Cryptology ePrint Archive, Paper 2016/222}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/222}}, url = {https://eprint.iacr.org/2016/222} }