| Presentation | 2020-05-20 Improved Quantum Information Set Decoding Algorithm with Low Memory Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The security of code-based cryptoststems relates to the hardness of the syndrome decoding problem. The best decoding algorithms are known as information set decoding (ISD) algorithms proposed by E. Prange. In this paper, we propose a quantum ISD algorithm based on the L. Both ISD algorithm (PhD thesis, 2018) and the E. Kirshanova quantum walk (PQCrypto 2018). This results in an improvement of time complexity in the condition of low memory compared with existing quantum ISD algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Syndrome Decoding Problem / Information Set Decoding (ISD) Algorithm / Grover Algorithm / Quantum Walk |
| Paper # | ISEC2020-3 |
| Date of Issue | 2020-05-13 (ISEC) |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2020/5/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Shiho Moriai(NICT) |
| Vice Chair | Shoichi Hirose(Univ. of Fukui) / Tetsuya Izu(Fujitsu Labs.) |
| Secretary | Shoichi Hirose(NICT) / Tetsuya Izu(Tsukuba Univ.) |
| Assistant | Dai Yamamoto(Fujitsu Labs.) / Yuuji Suga(IIJ) |
| Paper Information | |
| Registration To | Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improved Quantum Information Set Decoding Algorithm with Low Memory |
| Sub Title (in English) | |
| Keyword(1) | Syndrome Decoding Problem |
| Keyword(2) | Information Set Decoding (ISD) Algorithm |
| Keyword(3) | Grover Algorithm |
| Keyword(4) | Quantum Walk |
| 1st Author's Name | Naoto Kimura |
| 1st Author's Affiliation | The University of Tokyo(Univ. Tokyo) |
| 2nd Author's Name | Atsushi Takayasu |
| 2nd Author's Affiliation | National Institute of Information and Communications Technology(NICT) |
| 3rd Author's Name | Tsuyoshi Takagi |
| 3rd Author's Affiliation | The University of Tokyo(Univ. Tokyo) |
| Date | 2020-05-20 |
| Paper # | ISEC2020-3 |
| Volume (vol) | vol.120 |
| Number (no) | ISEC-28 |
| Page | pp.pp.15-22(ISEC), |
| #Pages | 8 |
| Date of Issue | 2020-05-13 (ISEC) |