| 講演抄録／キーワード |
| 講演名 |
2006-09-13 15:45
高密度数列を用いる条件付ナップザック暗号
○小林邦勝（山形大） |
| 抄録 |
（和） |
あらまし 密度が1.44と高いフィボナッチ数列を用いた条件付ナップザック暗号を提案する。フィボナッチ数列の連続する要素を２つずつに区切り，そのいずれかをナップザックに詰め込むことが条件になる。フィボナッチ数列の要素はある種の超増加性をもつため，これらの要素を秘密鍵として用いた場合には，その超増加性を用いて一意に復号することができる。公開鍵は秘密鍵aiを法pのもとでアフィン変換 して生成するが，アフィン変換の定数の値をa2i毎にいろいろ変化させることにより，絶対値が等しいか１だけ異なる公開鍵を複数作ることが出来る。公開鍵に絶対値が等しいか１だけ異なるものが複数存在することは，これらの公開鍵と暗号文からなる格子基底にLLLアルゴリズムを適用したときに，ベクトルのノルムが短いベクトル（格子）が沢山現れることを意味しており，格子の中の短いベクトルを求めるLLLアルゴリズムではノルムが最短ではない平文ベクトルを求めることが難しくなる。 |
| （英） |
We propose a conditional knapsack cryptosystem using the Fibonacci sequence. The condition is to pack either of two serial elements of the Fibonacci sequence. Each element ai of the Fibonacci sequence is transformed by Affine transformation αai + β, and these transformed elements are used for public keys. We can generate plural public keys with the same absolute value by using the different β. By using plural public keys with the same absolute value, a lot of short vectors, their norm equal to 2 or 3, exist in lattice. Accordingly, cryptanalysis of the proposed conditional knapsack cryptosystem by LLL algorithm is hard. |
| キーワード |
（和） |
条件付ナップザック暗号 / フィボナッチ数列 / フィボナッチ超増加 / アフィン変換 / LLLアルゴリズム / / / |
| （英） |
Conditional knapsack cryptosystem / Fibonacci sequence / Fibonacci super increasing / Affine transformation / LLL algorithm / / / |
| 文献情報 |
信学技報, vol. 106, no. 235, ISEC2006-84, pp. 91-95, 2006年9月. |
| 資料番号 |
ISEC2006-84 |
| 発行日 |
2006-09-06 (ISEC) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|