WEKO3
アイテム
Finding a Very Short Lattice Vector in the Extended Search Space
https://ipsj.ixsq.nii.ac.jp/records/83184
https://ipsj.ixsq.nii.ac.jp/records/83184a003802f-8d81-443e-8505-6eae21f0ce71
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL707027 (387.0 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-07-15 | |||||||||
| タイトル | ||||||||||
| タイトル | Finding a Very Short Lattice Vector in the Extended Search Space | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Finding a Very Short Lattice Vector in the Extended Search Space | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [一般論文] lattice, approximate SVP, exhaustive search, enumeration | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| Dokkyo University | ||||||||||
| 著者所属 | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Dokkyo University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者名 |
Masaharu, Fukase
× Masaharu, Fukase
× Kazunori, Yamaguchi
|
|||||||||
| 著者名(英) |
Masaharu, Fukase
× Masaharu, Fukase
× Kazunori, Yamaguchi
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The problem of finding a lattice vector approximating a shortest nonzero lattice vector (approximate SVP) is a serious problem that concerns lattices. Finding a lattice vector of the secret key of some lattice-based cryptosystems is equivalent to solving some hard approximate SVP. We call such vectors very short vectors (VSVs). Lattice basis reduction is the main tool for finding VSVs. However, the main lattice basis reduction algorithms cannot find VSVs in lattices in dimensions ～200 or above. Exhaustive search can be considered to be a key technique toward eliminating the limitations with current lattice basis reduction algorithms. However, known methods of carrying out exhaustive searches can only work in relatively low-dimensional lattices. We defined the extended search space (ESS) and experimentally confirmed that exhaustive searches in ESS make it possible to find VSVs in lattices in dimensions ～200 or above with the parameters computed from known VSVs. This paper presents an extension of our earlier work. We demonstrate the practical effectiveness of our technique by presenting a method of choosing the parameters without known VSVs. We also demonstrate the effectiveness of distributed searches. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.785 ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The problem of finding a lattice vector approximating a shortest nonzero lattice vector (approximate SVP) is a serious problem that concerns lattices. Finding a lattice vector of the secret key of some lattice-based cryptosystems is equivalent to solving some hard approximate SVP. We call such vectors very short vectors (VSVs). Lattice basis reduction is the main tool for finding VSVs. However, the main lattice basis reduction algorithms cannot find VSVs in lattices in dimensions ～200 or above. Exhaustive search can be considered to be a key technique toward eliminating the limitations with current lattice basis reduction algorithms. However, known methods of carrying out exhaustive searches can only work in relatively low-dimensional lattices. We defined the extended search space (ESS) and experimentally confirmed that exhaustive searches in ESS make it possible to find VSVs in lattices in dimensions ～200 or above with the parameters computed from known VSVs. This paper presents an extension of our earlier work. We demonstrate the practical effectiveness of our technique by presenting a method of choosing the parameters without known VSVs. We also demonstrate the effectiveness of distributed searches. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.785 ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116647 | |||||||||
| 書誌情報 |
情報処理学会論文誌 巻 53, 号 7, 発行日 2012-07-15 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7764 | |||||||||
