文献

J-GLOBAL ID：201202255137140905   整理番号：12A1166383

拡張検索空間において非常に短い格子ベクトルを見つけること

Finding a Very Short Lattice Vector in the Extended Search Space

著者 (2件)： FUKASE Masaharu (Dokkyo Univ.) ,  YAMAGUCHI Kazunori (The Univ. of Tokyo)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 20  号： 3  ページ： 785-795 (J-STAGE)  発行年： 2012年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 最短非ゼロ格子ベクトルを近似する格子ベクトル(近似SVP)を見つける問題は,格子に関係する重大な問題である。いくつかの格子ベース暗号システムの秘密鍵の格子ベクトルを見つけることは,ある困難な近似SVPの解決と等価である。筆者らはそのようなベクトルを非常に短いベクトル(VSV)と呼ぶ。格子基底縮小は,VSVを見つけるための主要なツールである。しかしながら,主な格子基底縮小アルゴリズムは,次元~200以上で格子のVSVを見つけることができない。全数検索は,現在の格子基底縮小アルゴリズムを持つ制限の除去に向けた重要な技術であると考えることができる。しかしながら,全数検索を実行する既知の方法は,比較的低次元の格子で動作することができる。筆者らは,拡張検索空間(ESS)を定義し,ESSでの全数検索が既知のVSVから計算されたパラメータを持つ次元~200以上での格子のVSVを見つけることを可能にすることを実験的に確認した。本論文は筆者らの以前の研究の延長を提示した。筆者らは,既知のVSVなしでパラメータを選択する方法を提示することにより筆者らの手法の実際的な有効性を実証した。また,筆者らは分散検索の有効性を実証した。(翻訳著者抄録)

シソーラス用語： *格子 ,  暗号鍵 ,  縮小 ,  *検索 ,  次元 ,  暗号 ,  *ベクトル
準シソーラス用語： 格子基底縮小 ,  秘密鍵

分類 (1件)： 計算理論  (JB02000A)

引用文献 (19件)：

• [1] Ajtai, M. and Dwork, C.: A Public-Key Cryptosystem with worst-case/average-case equivalence, Proc. 29th STOC, pp.284-293 (1997).
• [2] Ajtai, M.: The Shortest Vector Problem in L₂ is NP-hard for Randomized Reductions (Extended Abstract), Proc. Thirtieth Annual ACM Symposium on Theory of Computing, pp.10-19 (1998).
• [3] Dagdelen, Ö. and Schneider, M.: Parallel Enumeration of Shortest Lattice Vectors, Euro-Par 2010, Vol.6272 of LNCS, pp.211-222 (2010).
• [4] Fukase, M. and Yamaguchi, K.: The Analysis of ESS for the Shortest Vector in Lattice, Proc. SICT 2010, pp.209-213 (2010).
• [5] Fukase, M. and Yamaguchi, K.: Exhaustive Search for Finding a Very Short Vector in High-Dimensional Lattices, Proc. (short papers) IWSEC 2010, pp.26-41 (2010).

タイトルに関連する用語 (4件)： 拡張 ,  検索 ,  格子 ,  ベクトル