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

DOI Web Site 参考文献44件 オープンアクセス
  • 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

抄録

<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>

収録刊行物

参考文献 (44)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ