| Presentation | 2021-03-04 Solving Shortest Vector Problem using annealing computation Junpei Yamaguchi, Takuya Ohwa, Kazuyoshi Furukawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Shortest Vector Problem / pseudo-multi-spin slip / annealing / Ising model |
| Paper # | IT2020-121,ISEC2020-51,WBS2020-40 |
| Date of Issue | 2021-02-25 (IT, ISEC, WBS) |
| Conference Information | |
| Committee | WBS / IT / ISEC |
|---|---|
| Conference Date | 2021/3/4(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Joint Meeting of WBS, IT, and ISEC |
| Chair | Masanori Hamamura(Kochi Univ. of Tech.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Shoichi Hirose(Univ. of Fukui) |
| Vice Chair | Takashi Shono(INTEL) / Masahiro Fujii(Utsunomiya Univ.) / Tetsuya Kojima(Tokyo Kosen) / Tetsuya Izu(Fujitsu Labs.) / Noboru Kunihiro(Tsukuba Univ.) |
| Secretary | Takashi Shono(Okayama Univ. of Science) / Masahiro Fujii(National Defence Academy) / Tetsuya Kojima(Yamaguchi Univ.) / Tetsuya Izu(Saga Univ.) / Noboru Kunihiro(Tsukuba Univ.) |
| Assistant | Duong Quang Thang(NAIST) / Masafumi Moriyama(NICT) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Takahiro Ohta(Senshu Univ.) / Kazuki Yoneyama(Ibaraki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Wideband System / Technical Committee on Information Theory / Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Solving Shortest Vector Problem using annealing computation |
| Sub Title (in English) | How to generate a hamiltonian using pseudo multispin flip method |
| Keyword(1) | Shortest Vector Problem |
| Keyword(2) | pseudo-multi-spin slip |
| Keyword(3) | annealing |
| Keyword(4) | Ising model |
| 1st Author's Name | Junpei Yamaguchi |
| 1st Author's Affiliation | Fujitsu Llaboratories(Fujitsu Llaboratories) |
| 2nd Author's Name | Takuya Ohwa |
| 2nd Author's Affiliation | Kyushu Institute of Technology(Kyushu Institute of Technology) |
| 3rd Author's Name | Kazuyoshi Furukawa |
| 3rd Author's Affiliation | Fujitsu Llaboratories(Fujitsu Llaboratories) |
| Date | 2021-03-04 |
| Paper # | IT2020-121,ISEC2020-51,WBS2020-40 |
| Volume (vol) | vol.120 |
| Number (no) | IT-410,ISEC-411,WBS-412 |
| Page | pp.pp.58-65(IT), pp.58-65(ISEC), pp.58-65(WBS), |
| #Pages | 8 |
| Date of Issue | 2021-02-25 (IT, ISEC, WBS) |