| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-03-04 10:55 アニーリング計算を用いた最短ベクトル問題の求解 ～ 疑似マルチスピンフリップを用いたハミルトニアン生成 ～ ○山口純平（富士通研）・大輪拓也（九工大）・古川和快（富士通研）  IT2020-121 ISEC2020-51 WBS2020-40 |
|
| 抄録 | （和） | 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 / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 411, ISEC2020-51, pp. 58-65, 2021年3月. | |
| 資料番号 | ISEC2020-51 | |
| 発行日 | 2021-02-25 (IT, ISEC, WBS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2020-121 ISEC2020-51 WBS2020-40 |
|
| 研究会情報 | |
| 研究会 | WBS IT ISEC |
| 開催期間 | 2021-03-04 - 2021-03-05 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | WBS・IT・ISEC合同研究会 |
| テーマ（英） | Joint Meeting of WBS, IT, and ISEC |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2021-03-WBS-IT-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | アニーリング計算を用いた最短ベクトル問題の求解 |
| サブタイトル（和） | 疑似マルチスピンフリップを用いたハミルトニアン生成 |
| タイトル（英） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-03-04 10:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | IT2020-121, ISEC2020-51, WBS2020-40 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.410(IT), no.411(ISEC), no.412(WBS) |
| ページ範囲 | pp.58-65 |
| ページ数 | 8 |
| 発行日 | 2021-02-25 (IT, ISEC, WBS) |
[研究会発表申込システムのトップページに戻る]