| Presentation | 2023-11-16 Security Analysis of MP-LWE using Weighted Lattice Reduction Yudai Tagawa, Shinya Okumura, Atsuko Miyaji, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In 2017, Ro?ca et al. proposed the Middle-Product LWE (MP-LWE) problem, a new LWE problem variant. The MP-LWE problem mitigates the security risk of the Polynomial LWE in that its security depends on a particular polynomial. The MP-LWE problem can be viewed as a special case of the LWE problem. Therefore, we can use any of the known algorithms for the LWE problem to solve the MP-LWE problem. Two methods for solving the MP-LWE problem have been proposed: one applies the Primal Attack and the other applies Kannan's embedding method. In this study, we propose a method that combines Primal Attack on the MP-LWE problem and a method to control the output of a lattice reduction algorithm. Experimental results show that our attack has a higher success probability than Kannan's embedding method when the error coefficients are all even, as in the MP-LWE-based public key cryptosystem by Ro?ca et al. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Lattice based cryptography / MP-LWE / Weighted Primal Attack |
| Paper # | ICSS2023-57 |
| Date of Issue | 2023-11-09 (ICSS) |
| Conference Information | |
| Committee | ICSS |
|---|---|
| Conference Date | 2023/11/16(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | IT Business Plaza Musashi and Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Security, etc. |
| Chair | Daisuke Inoue(NICT) |
| Vice Chair | Akira Yamada(Kobe Univ.) / Toshihiro Yamauchi(Okayama Univ.) |
| Secretary | Akira Yamada(Mitsubishi Electric) / Toshihiro Yamauchi(Univ. of Electro-Comm.) |
| Assistant | Yo Kanemoto(NTT) / Masaya Sato(Okayama Prefectural Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information and Communication System Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Security Analysis of MP-LWE using Weighted Lattice Reduction |
| Sub Title (in English) | |
| Keyword(1) | Lattice based cryptography |
| Keyword(2) | MP-LWE |
| Keyword(3) | Weighted Primal Attack |
| 1st Author's Name | Yudai Tagawa |
| 1st Author's Affiliation | Osaka University(Osaka Univ.) |
| 2nd Author's Name | Shinya Okumura |
| 2nd Author's Affiliation | Osaka University(Osaka Univ.) |
| 3rd Author's Name | Atsuko Miyaji |
| 3rd Author's Affiliation | Osaka University(Osaka Univ.) |
| Date | 2023-11-16 |
| Paper # | ICSS2023-57 |
| Volume (vol) | vol.123 |
| Number (no) | ICSS-269 |
| Page | pp.pp.42-48(ICSS), |
| #Pages | 7 |
| Date of Issue | 2023-11-09 (ICSS) |