| 講演名 | 2021-03-04 アニーリング計算を用いた最短ベクトル問題の求解 山口 純平(富士通研), 大輪 拓也(九工大), 古川 和快(富士通研), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | NIST 耐量子計算機暗号標準化の有力候補とされる格子暗号は最短ベクトル問題（SVP）の計算困難性を安全性の根拠とする暗号である．SVP の求解法として，汎用計算機を用いた格子基底簡約やenumeration，sieving などのアルゴリズムが広く研究されている．一方で近年，アニーリングと呼ばれる計算原理を用いたハードウェアの大規模化が実現してきており，アニーリング計算機を用いたSVP の計算量評価が重要となっている．これまでにSVPをアニーリング計算機上で解く方法がいくつか提案されているが，バイナリ変数の1 つの0?1 を反転させることでより小さな解を探索するシングルスピンフリップによるアニーリング計算では局所解にとどまることが多く，最短ベクトルを計算するには多くの計算時間が必要であった．そこで本稿では，SVP 求解において，シングルスピンフリップで疑似的に複数個のバイナリ変数を反転させることで局所解からの脱出を早めさせる技術である疑似マルチスピンフリップ法を提案する．Darmstadt SVP Challenge の40 次元seed=0 のSVP を用いた実験では，疑似マルチスピンフリップ法では約8.4 秒と，従来の方法と比較しておよそ81.9 倍高速に最短ベクトルを計算することに成功した． |
| 抄録(英) | Lattice-based cryptography is mainly based on the security of the Shortest Vector Problem (SVP) and considered to be a prime candidate for post-quantum cryptography in the NIST Post-Quantum Cryptography Standardization. Recently, annealing computers have been realized on a large-scale, then it becomes necessary to estimate the computational hardness of the SVP with respect to them. Some techniques are proposed to solve the SVP on them, however, it takes enough annealing time to solve SVP with these techniques. In this paper, we propose pseudo-multi-spin flip algorithm to solve the SVP faster than the original techniques. In our experiments, we succeeded in solving a SVP on a 40-dimensional lattice in 8.4 seconds, which is 81.9 times faster than using the original techniques. |
| キーワード(和) | 最短ベクトル問題 / 疑似マルチスピンフリップ / アニーリング / イジングモデル |
| キーワード(英) | Shortest Vector Problem / pseudo-multi-spin slip / annealing / Ising model |
| 資料番号 | IT2020-121,ISEC2020-51,WBS2020-40 |
| 発行日 | 2021-02-25 (IT, ISEC, WBS) |
| 研究会情報 | |
| 研究会 | WBS / IT / ISEC |
|---|---|
| 開催期間 | 2021/3/4(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | WBS・IT・ISEC合同研究会 |
| テーマ（英） | Joint Meeting of WBS, IT, and ISEC |
| 委員長氏名（和） | 浜村 昌則(高知工科大) / 和田山 正(名工大) / 廣瀬 勝一(福井大) |
| 委員長氏名（英） | Masanori Hamamura(Kochi Univ. of Tech.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Shoichi Hirose(Univ. of Fukui) |
| 副委員長氏名（和） | 庄納 崇(インテル) / 藤井 雅弘(宇都宮大) / 小嶋 徹也(東京高専) / 伊豆 哲也(富士通研) / 國廣 昇(筑波大学) |
| 副委員長氏名（英） | Takashi Shono(INTEL) / Masahiro Fujii(Utsunomiya Univ.) / Tetsuya Kojima(Tokyo Kosen) / Tetsuya Izu(Fujitsu Labs.) / Noboru Kunihiro(Tsukuba Univ.) |
| 幹事氏名（和） | 荒井 伸太郎(岡山理科大) / 中村 僚兵(防衛大) / 野崎 隆之(山口大) / 廣友 雅徳(佐賀大) / 面 和成(筑波大) / 山本 大(富士通研) |
| 幹事氏名（英） | Shintaro Arai(Okayama Univ. of Science) / Ryohei Nakamura(National Defence Academy) / Takayuki Nozaki(Yamaguchi Univ.) / Masanori Hirotomo(Saga Univ.) / Kazunari Omote(Tsukuba Univ.) / Dai Yamamoto(Fujitsu Labs.) |
| 幹事補佐氏名（和） | Duong Quang Thang(奈良先端大) / 森山 雅文(NICT) / 木下 雅之(千葉工大) / 太田 隆博(専修大) / 米山 一樹(茨城大) |
| 幹事補佐氏名（英） | Duong Quang Thang(NAIST) / Masafumi Moriyama(NICT) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Takahiro Ohta(Senshu Univ.) / Kazuki Yoneyama(Ibaraki Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Wideband System / Technical Committee on Information Theory / Technical Committee on Information Security |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | アニーリング計算を用いた最短ベクトル問題の求解 |
| サブタイトル（和） | 疑似マルチスピンフリップを用いたハミルトニアン生成 |
| タイトル（英） | Solving Shortest Vector Problem using annealing computation |
| サブタイトル（和） | How to generate a hamiltonian using pseudo multispin flip method |
| キーワード(1)（和/英） | 最短ベクトル問題 / Shortest Vector Problem |
| キーワード(2)（和/英） | 疑似マルチスピンフリップ / pseudo-multi-spin slip |
| キーワード(3)（和/英） | アニーリング / annealing |
| キーワード(4)（和/英） | イジングモデル / Ising model |
| 第 1 著者 氏名（和/英） | 山口 純平 / Junpei Yamaguchi |
| 第 1 著者 所属（和/英） | 富士通研究所(略称：富士通研) Fujitsu Llaboratories(略称：Fujitsu Llaboratories) |
| 第 2 著者 氏名（和/英） | 大輪 拓也 / Takuya Ohwa |
| 第 2 著者 所属（和/英） | 九州工業大学(略称：九工大) Kyushu Institute of Technology(略称：Kyushu Institute of Technology) |
| 第 3 著者 氏名（和/英） | 古川 和快 / Kazuyoshi Furukawa |
| 第 3 著者 所属（和/英） | 富士通研究所(略称：富士通研) Fujitsu Llaboratories(略称：Fujitsu Llaboratories) |
| 発表年月日 | 2021-03-04 |
| 資料番号 | IT2020-121,ISEC2020-51,WBS2020-40 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IT-410,ISEC-411,WBS-412 |
| ページ範囲 | pp.58-65(IT), pp.58-65(ISEC), pp.58-65(WBS), |
| ページ数 | 8 |
| 発行日 | 2021-02-25 (IT, ISEC, WBS) |