License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.35
URN: urn:nbn:de:0030-drops-99837
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9983/
Go to the corresponding LIPIcs Volume Portal

Aggarwal, Divesh ; Mukhopadhyay, Priyanka

Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm

pdf-format:
LIPIcs-ISAAC-2018-35.pdf (0.5 MB)

Abstract

Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional 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 non-zero 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:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9983},
  URN =		{urn:nbn:de:0030-drops-99837},
  doi =		{10.4230/LIPIcs.ISAAC.2018.35},
  annote =	{Keywords: Lattice, Shortest Vector Problem, Closest Vector Problem, l_infty norm}
}

Keywords: Lattice, Shortest Vector Problem, Closest Vector Problem, l_infty norm
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI