Explicit Relation between Low-Dimensional LLL-Reduced Bases and Shortest Vectors

DOI Web Site 44 References Open Access
  • MATSUDA Kotaro
    Graduate School of Information Science and Technology, The University of Tokyo
  • TAKAYASU Atsushi
    Graduate School of Information Science and Technology, The University of Tokyo National Institute of Advanced Industrial Science and Technology
  • TAKAGI Tsuyoshi
    Graduate School of Information Science and Technology, The University of Tokyo

Description

<p>The Shortest Vector Problem (SVP) is one of the most important lattice problems in computer science and cryptography. The LLL lattice basis reduction algorithm runs in polynomial time and can compute an LLL-reduced basis that provably contains an approximate solution to the SVP. On the other hand, the LLL algorithm in practice tends to solve low-dimensional exact SVPs with high probability, i.e., >99.9%. Filling this theoretical-practical gap would lead to an understanding of the computational hardness of the SVP. In this paper, we try to fill the gap in 3,4 and 5 dimensions and obtain two results. First, we prove that given a 3,4 or 5-dimensional LLL-reduced basis, the shortest vector is one of the basis vectors or it is a limited integer linear combination of the basis vectors. In particular, we construct explicit representations of the shortest vector by using the LLL-reduced basis. Our analysis yields a necessary and sufficient condition for checking whether the output of the LLL algorithm contains the shortest vector or not. Second, we estimate the failure probability that a 3-dimensional random LLL-reduced basis does not contain the shortest vector. The upper bound seems rather tight by comparison with a Monte Carlo simulation.</p>

Journal

References(44)*help

See more

Related Projects

See more

Details 詳細情報について

Report a problem

Back to top