| Presentation | 2019-11-01 Lattice basis reduction over projected lattices and its application to solving the LWE problem Satoshi Nakamura, Nariaki Tateiwa, Koha Kinjo, Yasuhiko Ikematsu, Masaya Yasuda, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The security of modern lattice-based schemes is based on the computational hardness of solving the learning with errors (LWE) problem. On the other hand, lattice basis reduction algorithms such as LLL and BKZ are mandatory for solving the LWE problem. Recently, “DeepBKZ” reduction algorithm was proposed, in which DeepLLL, a straightforward generalization of LLL, is called as a subroutine in the BKZ framework. In this paper, we develop an algorithm of DeepBKZ over projected lattices. We also apply it to solving the LWE challenge problems, which have been in public since 2016, and we report its running time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | LWE problems / lattice basis reduction / DeepBKZ / projected lattices |
| Paper # | ISEC2019-68,SITE2019-62,LOIS2019-27 |
| Date of Issue | 2019-10-25 (ISEC, SITE, LOIS) |
| Conference Information | |
| Committee | ISEC / SITE / LOIS |
|---|---|
| Conference Date | 2019/11/1(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Osaka Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Shiho Moriai(NICT) / Tetsuya Morizumi(Kanagawa Univ.) / Tomohiro Yamada(NEL) |
| Vice Chair | Shoichi Hirose(Univ. of Fukui) / Tetsuya Izu(Fujitsu Labs.) / Masaru Ogawa(Kobe Gakuin Univ.) / Takushi Otani(Kibi International Univ.) / Toru Kobayashi(Nagasaki Univ.) |
| Secretary | Shoichi Hirose(NICT) / Tetsuya Izu(Tsukuba Univ.) / Masaru Ogawa(Toyo Eiwa Univ.) / Takushi Otani(KDDI Research) / Toru Kobayashi(Research Organization of Information and Systems) |
| Assistant | Dai Yamamoto(Fujitsu Labs.) / Yuuji Suga(IIJ) / Nobuyuki Yoshinaga(Yamaguchi Pref Univ.) / Daisuke Suzuki(Hokuriku Univ.) / Kenichi Arai(Nagasaki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Life Intelligence and Office Information Systems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Lattice basis reduction over projected lattices and its application to solving the LWE problem |
| Sub Title (in English) | |
| Keyword(1) | LWE problems |
| Keyword(2) | lattice basis reduction |
| Keyword(3) | DeepBKZ |
| Keyword(4) | projected lattices |
| 1st Author's Name | Satoshi Nakamura |
| 1st Author's Affiliation | Faculty of Mathematics, Kyushu University(Kyushu Univ.) |
| 2nd Author's Name | Nariaki Tateiwa |
| 2nd Author's Affiliation | Faculty of Mathematics, Kyushu University(Kyushu Univ.) |
| 3rd Author's Name | Koha Kinjo |
| 3rd Author's Affiliation | NTT Secure Platform Laboratories(NTT) |
| 4th Author's Name | Yasuhiko Ikematsu |
| 4th Author's Affiliation | Institute of Mathematics for Industry, Kyushu University(Kyushu Univ. IMI) |
| 5th Author's Name | Masaya Yasuda |
| 5th Author's Affiliation | Institute of Mathematics for Industry, Kyushu University(Kyushu Univ. IMI) |
| Date | 2019-11-01 |
| Paper # | ISEC2019-68,SITE2019-62,LOIS2019-27 |
| Volume (vol) | vol.119 |
| Number (no) | ISEC-257,SITE-258,LOIS-259 |
| Page | pp.pp.41-48(ISEC), pp.41-48(SITE), pp.41-48(LOIS), |
| #Pages | 8 |
| Date of Issue | 2019-10-25 (ISEC, SITE, LOIS) |