An Accelerated Algorithm for Solving SVP Based on Statistical Analysis

• Masaharu, Fukase

• Kenji, Kashiwabara

抄録

In this paper, we propose an accelerated algorithm for solving the shortest vector problem (SVP). We construct our algorithm by using two novel ideas, i.e., the choice of appropriate distributions of the natural number representation and the reduction of the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. These two ideas essentially depend on statistical analysis. The first technique is to generate lattice vectors expected to be short on a particular distribution of natural number representation. We determine the distribution so that more very short lattice vectors have a chance to be generated while lattice vectors that are unlikely to be very short are not generated. The second technique is to reduce the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. For that, we restrict the insertion index of a new lattice vector. We confirmed by theoretical and experimental analysis that the smaller the sum is, the more frequently a short lattice vector tends to be found. We solved an SVP instance in a higher dimension than ever, i.e., dimension 132 using our algorithm.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online)------------------------------

In this paper, we propose an accelerated algorithm for solving the shortest vector problem (SVP). We construct our algorithm by using two novel ideas, i.e., the choice of appropriate distributions of the natural number representation and the reduction of the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. These two ideas essentially depend on statistical analysis. The first technique is to generate lattice vectors expected to be short on a particular distribution of natural number representation. We determine the distribution so that more very short lattice vectors have a chance to be generated while lattice vectors that are unlikely to be very short are not generated. The second technique is to reduce the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. For that, we restrict the insertion index of a new lattice vector. We confirmed by theoretical and experimental analysis that the smaller the sum is, the more frequently a short lattice vector tends to be found. We solved an SVP instance in a higher dimension than ever, i.e., dimension 132 using our algorithm.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online)------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 55 (11), 2014-11-15

  一般社団法人情報処理学会

キーワード

• [一般論文] lattice, SVP, Gram-Schmidt orthogonalized vectors, RSR, normal distribution

詳細情報

• CRID: 1050845762835781248
• NII論文ID: 110009843053
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00106966/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles