Aggarwal, Divesh ;
Mukhopadhyay, Priyanka
Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm
Abstract
Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on ndimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest nonzero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer and Naewe, 2009] generalized the algorithm to other norms.
We study this problem for the special but important case of the l_infty norm. We give a new sieving procedure that runs in time linear in N, thereby improving the running time of the algorithm for SVP in the l_infty norm. As in [Ajtai et al., 2002; Blömer and Naewe, 2009], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the l_infty norm.
We also show that the heuristic sieving algorithms of Nguyen and Vidick [Nguyen and Vidick, 2008] and Wang et al. [Wang et al., 2011] can also be analyzed in the l_infty norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest.
BibTeX  Entry
@InProceedings{aggarwal_et_al:LIPIcs:2018:9983,
author = {Divesh Aggarwal and Priyanka Mukhopadhyay},
title = {{Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {35:135:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9983},
URN = {urn:nbn:de:0030drops99837},
doi = {10.4230/LIPIcs.ISAAC.2018.35},
annote = {Keywords: Lattice, Shortest Vector Problem, Closest Vector Problem, l_infty norm}
}
2018
Keywords: 

Lattice, Shortest Vector Problem, Closest Vector Problem, l_infty norm 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

2018 