| Presentation | 2011-11-14 A Lattice Attack against (u|u+v)Σ PKC Atsushi NAGAO, Yosuke TODO, Masakatu MORII, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In 2010, Kasahara et al. proposed a knapsack cryptosystem secure against a low-density attack. The cryptosystem were attacked by Murakami et al. with the low-density attack and indicated the safety in 2011. However Murakami's attack was not optimized for (u|u+v)Σ PKC. In this paper, we propose an effective lattice attack against the cryptosystem and evaluate the safety. In our attack, we first guess parts of the plaintext and generate a new lattice smaller than the previous lattice. Next, we execute the lattice reduction algorithm against the small lattice and recover all of the plaintext. By using the proposed attack, we solved all challenge problems which are presented by Kasahara in short time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | public-key cryptosystem / knapsack cryptosystem / (u|u+v)Σ PKC / lattice attack / cryptanalysis |
| Paper # | ISEC2011-35,LOIS2011-29 |
| Date of Issue |
| Conference Information | |
| Committee | LOIS |
|---|---|
| Conference Date | 2011/11/7(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Life Intelligence and Office Information Systems (LOIS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Lattice Attack against (u|u+v)Σ PKC |
| Sub Title (in English) | |
| Keyword(1) | public-key cryptosystem |
| Keyword(2) | knapsack cryptosystem |
| Keyword(3) | (u|u+v)Σ PKC |
| Keyword(4) | lattice attack |
| Keyword(5) | cryptanalysis |
| 1st Author's Name | Atsushi NAGAO |
| 1st Author's Affiliation | Faculty of Engineering, Kobe University() |
| 2nd Author's Name | Yosuke TODO |
| 2nd Author's Affiliation | Graduate School of Engineering, Kobe University |
| 3rd Author's Name | Masakatu MORII |
| 3rd Author's Affiliation | Graduate School of Engineering, Kobe University |
| Date | 2011-11-14 |
| Paper # | ISEC2011-35,LOIS2011-29 |
| Volume (vol) | vol.111 |
| Number (no) | 286 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |