ブロック簡約基底に対する最短ベクトル探索の最悪時計算量評価

• Item type: SIG Technical Reports(1)
• 公開日: 2016-07-07
• タイトル: ブロック簡約基底に対する最短ベクトル探索の最悪時計算量評価
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者名: 高安, 敦; 國廣, 昇
• 著者名(英): Atsushi, Takayasu; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Walter (ICITS 2015) は，BKZ 簡約と slide 簡約という二つのブロック型格子簡約アルゴリズムを事前処理として用いた際の最短ベクトル探索の計算量を解析した．これまでの既存研究では，LLL 簡約や quasi-HKZ 簡約という極端に弱い，または強い事前処理を適用した基底に対してしかこの解析はされておらず，Walter はこれらの結果の補間を試みた．この研究は理論的にも実用的にも非常に大きな意味があるが，Walter 自身が指摘しているように彼が導出した最短ベクトル探索の計算量は決して最適ではない．だが，この結果は最短ベクトル問題の困難性を評価するうえで興味深いものであることは間違いない．本稿では，Walter の結果を再考する．まず，Walter の解析はいくつもの理論的妥当性に欠ける点があり，これらを全て修正する．最も大きな点としては，Gama と Nguyen (STOC 2008) の提案した slide 簡約アルゴリズムはブロックサイズが格子の次元を割り切るときしか定義されていないが，Walter はそれがそも任意の値を許すかのように扱っている点で明らかに妥当ではない．そのため，我々は Gama-Nguyen の slide 簡約を任意のブロックサイズに拡張する一般化した定義を与え，それを下に解析を行う．その結果，slide 簡約基底に対する最短ベクトル探索は Walter が指摘していたほど高速ではないことを示す．一方で，BKZ 簡約基底に対しては Walter の結果より高速に，次元 n の格子の最短ベクトルを時間 √nn+o(n) で探索できることを示す．さらに，Gram-Schmidt ベクトルのノルムが単調に減少するという仮定の下で，BKZ 簡約基底と slide 簡約基底はいずれも時間 √nn/e+o(n) という最適な計算量で最短ベクトルを探索できることを示す．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12628305
• 書誌情報: 研究報告セキュリティ心理学とトラスト（SPT）; 巻 2016-SPT-19, 号 28, p. 1-8, 発行日 2016-07-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8671
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会