Faster algorithms for SVP and CVP in the ℓ_∞ norm
share
Blomer and Naewe[BN09] modified the randomized sieving algorithm of Ajtai, Kumar and Sivakumar[AKS01] to solve the shortest vector problem (SVP). The algorithm starts with N = 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice. The running time of the sieving procedure is quadratic in N. We study this problem for the special but important case of the ℓ_∞ norm. We give a new sieving procedure that runs in time linear in N, thereby significantly improving the running time of the algorithm for SVP in the ℓ_∞ norm. As in [AKS02],[BN09], 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 ℓ_∞ norm. We also show that the heuristic sieving algorithms of Nguyen and Vidick [NV08] and Wang et.al.[WLTB11] can also be analyzed in the ℓ_∞ 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.
READ FULL TEXT