| 講演名 | 2016-07-15 ブロック簡約基底に対する最短ベクトル探索の最悪時計算量評価 高安 敦(東大), 國廣 昇(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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$の格子の最短ベクトルを時間$sqrt{n}^{n+o(n)}$で探索できることを示す．さらに，Gram-Schmidtベクトルのノルムが単調に減少するという仮定の下で，BKZ簡約基底とslide簡約基底はいずれも時間$sqrt{n}^{n/e+o(n)}$という最適な計算量で最短ベクトルを探索できることを示す． |
| 抄録(英) | |
| キーワード(和) | 格子 / 最短ベクトル問題 / 最短ベクトル探索 / BKZ簡約 / slide簡約 |
| キーワード(英) | |
| 資料番号 | ISEC2016-33,SITE2016-27,ICSS2016-33,EMM2016-41 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |
| 研究会情報 | |
| 研究会 | EMM / ISEC / SITE / ICSS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| 開催期間 | 2016/7/14(から2日開催) |
| 開催地（和） | 中市コミュニティーホール Nac |
| 開催地（英） | |
| テーマ（和） | セキュリティ，一般 |
| テーマ（英） | security, etc |
| 委員長氏名（和） | 伊藤 彰則(東北大) / 満保 雅浩(金沢大) / 岡田 仁志(NII) / 三宅 優(KDDI研) |
| 委員長氏名（英） | Akinori Ito(Tohoku Univ.) / Masahiro Mambo(Kanazawa Univ.) / Hitoshi Okada(NII) / Yutaka Miyake(KDDI R&D Labs.) |
| 副委員長氏名（和） | 川村 正樹(山口大) / 日置 尋久(京大) / 小川 一人(NHK) / 藤岡 淳(神奈川大) / 森住 哲也(神奈川大) / 小川 賢(神戸学院大) / 白石 善明(神戸大) / 植田 武(三菱電機) |
| 副委員長氏名（英） | Masaki Kawamura(Yamaguchi Univ.) / Hirohisa Hioki(Kyoto Univ.) / Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) / Yoshiaki Shiraishi(Kobe Univ.) / Takeshi Ueda(Mitsubishi Electric) |
| 幹事氏名（和） | 薗田 光太郎(長崎大) / 岩田 基(阪府大) / 駒野 雄一(東芝) / 水木 敬明(東北大) / 多川 孝央(九大) / 芳賀 高洋(岐阜聖徳学園大) / 高倉 弘喜(NII) / 吉岡 克成(横浜国大) |
| 幹事氏名（英） | Kotaro Sonoda(Nagasaki Univ.) / Motoi Iwata(Osaka Pref. Univ.) / Yuichi Komano(Toshiba) / Takaaki Mizuki(Tohoku Univ.) / Takahiro Tagawa(Kyushu Univ.) / Takahiro Haga(Gifu Shotoku Gakuen Univ.) / Hiroki Takakura(NII) / Katsunari Yoshioka(Yokohama National Univ.) |
| 幹事補佐氏名（和） | 生源寺 類(静岡大) / 藤吉 正明(首都大東京) / 大東 俊博(東海大) / 須賀 祐治(インターネットイニシアティブ) / 猪俣 敦夫(東京電機大) / 川口 嘉奈子(東京藝術大) / 神谷 和憲(NTT) / 笠間 貴弘(NICT) |
| 幹事補佐氏名（英） | Rui Shogenji(Shizuoka Univ.) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Kanako Kawaguchi(Tokyo Univ. of the Arts) / Kazunori Kamiya(NTT) / Takahiro Kasama(NICT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ブロック簡約基底に対する最短ベクトル探索の最悪時計算量評価 |
| サブタイトル（和） | |
| タイトル（英） | Worst Case Short Lattice Point Enumeration on Block Reduced Bases |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 格子 |
| キーワード(2)（和/英） | 最短ベクトル問題 |
| キーワード(3)（和/英） | 最短ベクトル探索 |
| キーワード(4)（和/英） | BKZ簡約 |
| キーワード(5)（和/英） | slide簡約 |
| 第 1 著者 氏名（和/英） | 高安 敦 / Atsushi Takayasu |
| 第 1 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. Tokyo) |
| 第 2 著者 氏名（和/英） | 國廣 昇 / Noboru Kunihiro |
| 第 2 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. Tokyo) |
| 発表年月日 | 2016-07-15 |
| 資料番号 | ISEC2016-33,SITE2016-27,ICSS2016-33,EMM2016-41 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | ISEC-129,SITE-130,ICSS-131,EMM-132 |
| ページ範囲 | pp.177-184(ISEC), pp.177-184(SITE), pp.177-184(ICSS), pp.177-184(EMM), |
| ページ数 | 8 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |