論文

査読有り
2017年3月

Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors

JOURNAL OF MATHEMATICAL CRYPTOLOGY
  • Masaya Yasuda
  • ,
  • Kazuhiro Yokoyama
  • ,
  • Takeshi Shimoyama
  • ,
  • Jun Kogure
  • ,
  • Takeshi Koshiba

11
1
開始ページ
1
終了ページ
24
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1515/jmc-2016-0008
出版者・発行元
WALTER DE GRUYTER GMBH

In 2015, Fukase and Kashiwabara proposed an efficient method to find a very short lattice vector. Their method has been applied to solve Darmstadt shortest vector problems of dimensions 134 to 150. Their method is based on Schnorr's random sampling, but their preprocessing is different from others. It aims to decrease the sum of the squared lengths of the Gram-Schmidt vectors of a lattice basis, before executing random sampling of short lattice vectors. The effect is substantiated from their statistical analysis, and it implies that the smaller the sum becomes, the shorter sampled vectors can be. However, no guarantee is known to strictly decrease the sum. In this paper, we study Fukase-Kashiwabara's method in both theory and practice, and give a heuristic but practical condition that the sum is strictly decreased. We believe that our condition would enable one to monotonically decrease the sum and to find a very short lattice vector in fewer steps.


リンク情報
DOI
https://doi.org/10.1515/jmc-2016-0008
DBLP
https://dblp.uni-trier.de/rec/journals/jmc/YasudaYSKK17
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000410408900001&DestApp=WOS_CPL
Dblp Url
https://dblp.uni-trier.de/db/journals/jmc/jmc11.html#YasudaYSKK17
ID情報
  • DOI : 10.1515/jmc-2016-0008
  • ISSN : 1862-2976
  • eISSN : 1862-2984
  • DBLP ID : journals/jmc/YasudaYSKK17
  • Web of Science ID : WOS:000410408900001

エクスポート
BibTeX RIS