講演名	2017-07-14 DeepLLLを用いたSVP解読報告 山口 純平(九大), 安田 雅哉(九大),
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	格子暗号の安全性は最短ベクトル問題（SVP）や最近ベクトル問題（CVP）などの格子問題の計算量的困難 性に基づいている．格子問題に対する効率的な攻撃法として，格子基底縮約アルゴリズムがよく利用される．最も有 名な縮約アルゴリズムはLLLアルゴリズムであり，DeepLLLやBKZはその改良方式として知られている．本稿では DeepLLLの高速化手法を与え，その高速化したDeepLLLとBKZを組み合わせたアルゴリズムであるDeepBKZを 提案する．そしてDeepBKZの優位性を，従来BKZとの比較（計算時間，出力基底の質，ツアー回数）やDarmstadt SVP challengeでの新記録を基に示す．
抄録(英)	Lattice-based cryptography is based on the computational herdbess of lattice problems such as Shortest vector problem (SVP) and Closest vector problem (CVP). Lattice basis reduction algorithm have been used as a good tool for cryptoanalysis. The most famous one is LLL algorithm, LLL algorithm with deep insertions (DeepLLL) and BKZ are its improvement. In this paper, we give the speeding-up method of DeepLLL. And then, we propose the DeepBKZ algorithm which is combined DeepLLL and BKZ, and we show its superiority by the comparison with BKZ and new records of Darmstadt SVP challenge.
キーワード(和)	格子 / 最短ベクトル問題（SVP） / 格子縮約 / DeepLLL / BKZ / Darmstadt SVP Challenge
キーワード(英)	Lattice / Shortest vector problem (SVP) / lattice reduction / DeepLLL / BKZ / Darmstadt SVP Challenge
資料番号	ISEC2017-23,SITE2017-15,ICSS2017-22,EMM2017-26
発行日	2017-07-07 (ISEC, SITE, ICSS, EMM)

研究会情報
研究会	SITE / EMM / ISEC / ICSS / IPSJ-CSEC / IPSJ-SPT
開催期間	2017/7/14(から2日開催)
開催地（和）	内田洋行東京本社ショールーム
開催地（英）
テーマ（和）	セキュリティ、一般
テーマ（英）
委員長氏名（和）	岡田 仁志(NII) / 岩村 惠市(東京理科大) / 小川 一人(NHK) / 白石 善明(神戸大)
委員長氏名（英）	Hitoshi Okada(NII) / Keiichi Iwamura(TUC) / Kazuto Ogawa(NHK) / Yoshiaki Shiraishi(Kobe Univ.)
副委員長氏名（和）	森住 哲也(神奈川大) / 小川 賢(神戸学院大) / 日置 尋久(京大) / 栗林 稔(岡山大) / 藤岡 淳(神奈川大) / 盛合 志帆(NICT) / 植田 武(三菱電機) / 高倉 弘喜(NII)
副委員長氏名（英）	Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) / Hirohisa Hioki(Kyoto Univ.) / Minoru Kuribayashi(Okayama Univ.) / Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) / Takeshi Ueda(Mitsubishi Electric) / Hiroki Takakura(NII)
幹事氏名（和）	芳賀 高洋(岐阜聖徳学園大) / 川口 嘉奈子(東京藝術大) / 生源寺 類(静岡大) / 藤吉 正明(首都大東京) / 水木 敬明(東北大) / 大東 俊博(東海大) / 吉岡 克成(横浜国大) / 神谷 和憲(NTT)
幹事氏名（英）	Takahiro Haga(Gifu Shotoku Gakuen Univ.) / Kanako Kawaguchi(Tokyo Univ. of the Arts) / Rui Shogenji(Shizuoka Univ.) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Takaaki Mizuki(Tohoku Univ.) / Toshihiro Ohigashi(Tokai Univ.) / Katsunari Yoshioka(Yokohama National Univ.) / Kazunori Kamiya(NTT)
幹事補佐氏名（和）	壁谷 彰慶(千葉大) / 加藤 尚徳(KDDI) / 姜 玄浩(東京高専) / 村田 晴美(中京大) / 江村 恵太(NICT) / 駒野 雄一(東芝) / 須賀 祐治(インターネットイニシアティブ) / 笠間 貴弘(NICT) / 山田 明(KDDI labs.)
幹事補佐氏名（英）	Akiyoshi Kabeya(Chiba Univ.) / Hisanori Kato(KDDI) / Kan Hyonho(NIT, Tokyo) / Harumi Murata(Tyukyo Univ.) / Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) / Takahiro Kasama(NICT) / Akira Yamada(KDDI labs.)

講演論文情報詳細
申込み研究会	Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Enriched MultiMedia / Technical Committee on Information Security / Technical Committee on Information and Communication System Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust
本文の言語	JPN
タイトル（和）	DeepLLLを用いたSVP解読報告
サブタイトル（和）
タイトル（英）	Report of solving SVP's by using DeepLLL
サブタイトル（和）
キーワード(1)（和/英）	格子 / Lattice
キーワード(2)（和/英）	最短ベクトル問題（SVP） / Shortest vector problem (SVP)
キーワード(3)（和/英）	格子縮約 / lattice reduction
キーワード(4)（和/英）	DeepLLL / DeepLLL
キーワード(5)（和/英）	BKZ / BKZ
キーワード(6)（和/英）	Darmstadt SVP Challenge / Darmstadt SVP Challenge
第 1 著者 氏名（和/英）	山口 純平 / Junpei Yamaguchi
第 1 著者 所属（和/英）	九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.)
第 2 著者 氏名（和/英）	安田 雅哉 / Masaya Yasuda
第 2 著者 所属（和/英）	九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.)
発表年月日	2017-07-14
資料番号	ISEC2017-23,SITE2017-15,ICSS2017-22,EMM2017-26
巻番号（vol）	vol.117
号番号（no）	ISEC-125,SITE-126,ICSS-127,EMM-128
ページ範囲	pp.115-122(ISEC), pp.115-122(SITE), pp.115-122(ICSS), pp.115-122(EMM),
ページ数	8
発行日	2017-07-07 (ISEC, SITE, ICSS, EMM)