| 講演名 | 2019-11-01 射影格子上のDeepBKZ基底簡約とLWE問題の求解への応用 中邑 聡史(九大), 立岩 斉明(九大), 金城 皓羽(NTT), 池松 泰彦(九大IMI), 安田 雅哉(九大IMI), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年提案されている格子暗号の多くの方式の安全性は Learning with Errors（LWE）問題の求解困難性に基づいている．一方，LLL や BKZ などの格子基底簡約アルゴリズムは LWE 問題を求解する上で必須の技術である．近年，LLL の自然な一般化である DeepLLL 基底簡約を BKZ のサブルーチンとして呼ぶ出す DeepBKZ 基底簡約アルゴリズムが提案された．BKZ に比べて，DeepBKZ 基底簡約は小さなブロックサイズでもかなり短い格子ベクトルを見つけることができる．本稿では，射影格子上の DeepBKZ 基底簡約アルゴリズムを開発する．さらに，その基底簡約アルゴリズムを 2016 年から公開されている LWE チャレンジ問題の求解に適用し，その求解時間などを報告する． |
| 抄録(英) | The security of modern lattice-based schemes is based on the computational hardness of solving the learning with errors (LWE) problem. On the other hand, lattice basis reduction algorithms such as LLL and BKZ are mandatory for solving the LWE problem. Recently, “DeepBKZ” reduction algorithm was proposed, in which DeepLLL, a straightforward generalization of LLL, is called as a subroutine in the BKZ framework. In this paper, we develop an algorithm of DeepBKZ over projected lattices. We also apply it to solving the LWE challenge problems, which have been in public since 2016, and we report its running time. |
| キーワード(和) | LWE問題 / 格子基底簡約 / DeepBKZ / 射影格子 |
| キーワード(英) | LWE problems / lattice basis reduction / DeepBKZ / projected lattices |
| 資料番号 | ISEC2019-68,SITE2019-62,LOIS2019-27 |
| 発行日 | 2019-10-25 (ISEC, SITE, LOIS) |
| 研究会情報 | |
| 研究会 | ISEC / SITE / LOIS |
|---|---|
| 開催期間 | 2019/11/1(から2日開催) |
| 開催地（和） | 大阪大学 吹田キャンパス |
| 開催地（英） | Osaka Univ. |
| テーマ（和） | 情報セキュリティ，ライフログ活用技術，ライフインテリジェンス，オフィス情報システム，一般 |
| テーマ（英） | |
| 委員長氏名（和） | 盛合 志帆(NICT) / 森住 哲也(神奈川大) / 山田 智広(NEL) |
| 委員長氏名（英） | Shiho Moriai(NICT) / Tetsuya Morizumi(Kanagawa Univ.) / Tomohiro Yamada(NEL) |
| 副委員長氏名（和） | 廣瀬 勝一(福井大) / 伊豆 哲也(富士通研) / 小川 賢(神戸学院大) / 大谷 卓史(吉備国際大) / 小林 透(長崎大) |
| 副委員長氏名（英） | Shoichi Hirose(Univ. of Fukui) / Tetsuya Izu(Fujitsu Labs.) / Masaru Ogawa(Kobe Gakuin Univ.) / Takushi Otani(Kibi International Univ.) / Toru Kobayashi(Nagasaki Univ.) |
| 幹事氏名（和） | 江村 恵太(NICT) / 面 和成(筑波大) / 壁谷 彰慶(東洋英和女学院大) / 加藤 尚徳(KDDI総合研究所) / 岡本 基(情報・システム研究機構) / 永徳 真一郎(NTT) |
| 幹事氏名（英） | Keita Emura(NICT) / Kazunari Omote(Tsukuba Univ.) / Akiyoshi Kabeya(Toyo Eiwa Univ.) / Hisanori Kato(KDDI Research) / Motoi Okamoto(Research Organization of Information and Systems) / Shinichiro Eitoku(NTT) |
| 幹事補佐氏名（和） | 山本 大(富士通研) / 須賀 祐治(インターネットイニシアティブ) / 吉永 敦征(山口県立大) / 鈴木 大助(北陸大) / 荒井 研一(長崎大学) |
| 幹事補佐氏名（英） | Dai Yamamoto(Fujitsu Labs.) / Yuuji Suga(IIJ) / Nobuyuki Yoshinaga(Yamaguchi Pref Univ.) / Daisuke Suzuki(Hokuriku Univ.) / Kenichi Arai(Nagasaki Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Life Intelligence and Office Information Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 射影格子上のDeepBKZ基底簡約とLWE問題の求解への応用 |
| サブタイトル（和） | |
| タイトル（英） | Lattice basis reduction over projected lattices and its application to solving the LWE problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | LWE問題 / LWE problems |
| キーワード(2)（和/英） | 格子基底簡約 / lattice basis reduction |
| キーワード(3)（和/英） | DeepBKZ / DeepBKZ |
| キーワード(4)（和/英） | 射影格子 / projected lattices |
| 第 1 著者 氏名（和/英） | 中邑 聡史 / Satoshi Nakamura |
| 第 1 著者 所属（和/英） | 九州大学大学院数理学府(略称：九大) Faculty of Mathematics, Kyushu University(略称：Kyushu Univ.) |
| 第 2 著者 氏名（和/英） | 立岩 斉明 / Nariaki Tateiwa |
| 第 2 著者 所属（和/英） | 九州大学大学院数理学府(略称：九大) Faculty of Mathematics, Kyushu University(略称：Kyushu Univ.) |
| 第 3 著者 氏名（和/英） | 金城 皓羽 / Koha Kinjo |
| 第 3 著者 所属（和/英） | NTTセキュアプラットフォーム研究所(略称：NTT) NTT Secure Platform Laboratories(略称：NTT) |
| 第 4 著者 氏名（和/英） | 池松 泰彦 / Yasuhiko Ikematsu |
| 第 4 著者 所属（和/英） | 九州大学マス・フォア・インダストリ研究所(略称：九大IMI) Institute of Mathematics for Industry, Kyushu University(略称：Kyushu Univ. IMI) |
| 第 5 著者 氏名（和/英） | 安田 雅哉 / Masaya Yasuda |
| 第 5 著者 所属（和/英） | 九州大学マス・フォア・インダストリ研究所(略称：九大IMI) Institute of Mathematics for Industry, Kyushu University(略称：Kyushu Univ. IMI) |
| 発表年月日 | 2019-11-01 |
| 資料番号 | ISEC2019-68,SITE2019-62,LOIS2019-27 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | ISEC-257,SITE-258,LOIS-259 |
| ページ範囲 | pp.41-48(ISEC), pp.41-48(SITE), pp.41-48(LOIS), |
| ページ数 | 8 |
| 発行日 | 2019-10-25 (ISEC, SITE, LOIS) |