文献

J-GLOBAL ID：201502216807373384   整理番号：15A0259595

統計分析に基づくSVPを解くための加速アルゴリズム

An Accelerated Algorithm for Solving SVP Based on Statistical Analysis

著者 (2件)： FUKASE Masaharu (Dokkyo Univ.) ,  KASHIWABARA Kenji (Dep. of General Systems Studies, The Univ. of Tokyo)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 23  号： 1  ページ： 67-80 (J-STAGE)  発行年： 2015年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,最短ベクトル問題を解くための加速アルゴリズムを提案する。自然数の表現の適切な配分の選択とグラムシュミット直交ベクトルの2乗長さ合計の削減によりアルゴリズム構築した。2つのアイデアは,基本的に統計分析に依存している。最初の技術は自然数表現の特定の分布に,短いことが期待される格子ベクトルを生成することである。筆者らは,非常に短い格子ベクトルが生成されない間,より短い格子ベクトルを生成するためのチャンスがあるように分布を決定した。第2の技術は,グラムシュミト直交ベクトルの自乗長さを減少させることである。そのため,新しい格子ベクトルの挿入を制限した。筆者らは,和が小さいほど,より頻繁に短い格子ベクトルが発見される傾向にあることを論理的および実験的分析で確認した。このアルゴリズムを使用し,ディメンション132以上のこれまでより高い次元でSVPインスタンスを解決した。(翻訳著者抄録)

シソーラス用語： プロトコル ,  *アルゴリズム ,  *統計解析 ,  整数 ,  配置 ,  次元 ,  *ベクトル ,  *問題
準シソーラス用語： ディメンション ,  *ベクトル問題 ,  最適配分 ,  自然数 ,  統計分析

分類 (3件)： 符号理論  (ND02030R) ,  計算理論  (JB02000A) ,  数値計算  (JE02000J)

引用文献 (16件)：

• [1] Ajtai, M.: The Shortest Vector Problem in L₂ is NP-hard for Randomized Reductions (Extended Abstract), Proc. 30th Annual ACM Symposium on Theory of Computing, pp.10-19 (1998).
• [2] Buchmann, J. and Ludwig, C.: Practical Lattice Basis Sampling Reduction, Proc. ANTS 2006, LNCS, Vol.4076, pp.222-237 (2005).
• [3] Chen, Y. and Nguyen, P.Q.: BKZ2.0: Better Lattice Security Estimates, ASIACRYPT 2011, LNCS, Vol.7073, pp.1-20 (2011).
• [4] Gama, N. and Nguyen, P.Q.: Predicting Lattice Reduction, EUROCRYPT 2008, LNCS, Vol.4965, pp.31-51 (2008).
• [5] Gama, N., Nguyen, P.Q. and Regev, O.: Lattice Enumeration Using Extreme Pruning, EUROCRYPT 2010, LNCS, Vol.6110, pp.257-278 (2010).

タイトルに関連する用語 (3件)： 統計分析 ,  加速 ,  アルゴリズム