| Presentation | 2006-03-16 On the Complexity of the Closest Vector Problem for Regular Lattices Shingo HASEGAWA, Shuji ISOBE, Hiroki SHIZUYA, Yuichi FUTA, Motoji OHMORI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Recently, lattice cryptosystems receive much attention in a sense that these cryptosystems do not depend on the difficulty of the integer factoring problem or the discrete logarithm problem. Lattice cryptosystems depend on lattice problems such as the shortest vector problem and the closest vector problem. These problems are known to be NP-hard, and their approximate versions are widely studied. However, since lattices to construct practical cryptosystems have some structural property, there could exist an efficient algorithm which solve lattice problems using the property. In this paper, we explore the complexity of the closest vector problem from the viewpoint of lattice structure, and show that this problem restrictred to the regular lattices remains NP-hard. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | lattice / closest vector problem / γ-reducibility |
| Paper # | IT2005-83,ISEC2005-140,WBS2005-97 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2006/3/9(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 | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Complexity of the Closest Vector Problem for Regular Lattices |
| Sub Title (in English) | |
| Keyword(1) | lattice |
| Keyword(2) | closest vector problem |
| Keyword(3) | γ-reducibility |
| 1st Author's Name | Shingo HASEGAWA |
| 1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Shuji ISOBE |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Hiroki SHIZUYA |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 4th Author's Name | Yuichi FUTA |
| 4th Author's Affiliation | Matsushita Electric Industrial Co. |
| 5th Author's Name | Motoji OHMORI |
| 5th Author's Affiliation | Matsushita Electric Industrial Co. |
| Date | 2006-03-16 |
| Paper # | IT2005-83,ISEC2005-140,WBS2005-97 |
| Volume (vol) | vol.105 |
| Number (no) | 663 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |