| 講演名 | 2000/11/6 巡回セールスマン問題の公開鍵暗号への応用 安細 勉, 松山 博明, 早田 孝博, 小林 邦勝, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | NP完全問題の一つである巡回セールスマン問題を公開鍵暗号に応用し, その暗号アルゴリズムを提案する.セールスマンの辿る経路(巡路)を平文に, その経路長を暗号文に対応させ, 初めに, 平文と暗号文が1:1に対応するための各都市間の距離が満たすべき条件について検討する.本文では, フィボナッチ数を各都市間の距離として与えた場合について考察し, これらの数値をモジュラー変換した値を公開鍵とする暗号アルゴリズムを求める.次に, バックトラッキング手法を用いて暗号文から平文を求める復号アルゴリズムを示す.本暗号は加算タイプのナップザック暗号と同じく線形暗号であることから, 線形暗号に対する代表的な解読法であるLLLアルゴリズムに対して耐性評価を行い, 公開鍵ベクトルの密度と都市数を変化させた時の解読率を数値的に検討する. |
| 抄録(英) | We propose a public key cryptosysmtem using the traveling salesman problem that is a NP complete probrem. A cycle corresponds to a plaintext and the total distance correspond to the ciphertext. We use Fibonacci numbers as the distance between the cities. In case of a plaintext and the ciphertext show one to one correspondence, by using the backtracking method, we can decrypt the ciphertext uniquely. We examine the security of this cryptosystem against LLL algorithm numerically. |
| キーワード(和) | NP完全問題 / 巡回セールスマン問題 / 公開鍵暗号 / フィボナッチ数 / バックトラッキング / LLLアルゴリズム |
| キーワード(英) | NP complete problem / the traveling salesman problem / public key cryptosystem / Fibonacci number / backtracking method / LLL algorithm |
| 資料番号 | ISEC2000-91 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2000/11/6(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 巡回セールスマン問題の公開鍵暗号への応用 |
| サブタイトル（和） | |
| タイトル（英） | An Application of the Traveling Salesman Problem to Public Key Cryptosystem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | NP完全問題 / NP complete problem |
| キーワード(2)（和/英） | 巡回セールスマン問題 / the traveling salesman problem |
| キーワード(3)（和/英） | 公開鍵暗号 / public key cryptosystem |
| キーワード(4)（和/英） | フィボナッチ数 / Fibonacci number |
| キーワード(5)（和/英） | バックトラッキング / backtracking method |
| キーワード(6)（和/英） | LLLアルゴリズム / LLL algorithm |
| 第 1 著者 氏名（和/英） | 安細 勉 / Tsutomu ANSAI |
| 第 1 著者 所属（和/英） | 山形大学工学部情報科学科 Faculty of Engineering, Yamagata University |
| 第 2 著者 氏名（和/英） | 松山 博明 / Hiroaki MATSUYAMA |
| 第 2 著者 所属（和/英） | 山形大学工学部情報科学科 Faculty of Engineering, Yamagata University |
| 第 3 著者 氏名（和/英） | 早田 孝博 / Takahiro HAYATA |
| 第 3 著者 所属（和/英） | 山形大学工学部情報科学科 Faculty of Engineering, Yamagata University |
| 第 4 著者 氏名（和/英） | 小林 邦勝 / Kunikatsu KOBAYASHI |
| 第 4 著者 所属（和/英） | 山形大学工学部情報科学科 Faculty of Engineering, Yamagata University |
| 発表年月日 | 2000/11/6 |
| 資料番号 | ISEC2000-91 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 421 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |