| Presentation | 2000/11/6 An Application of the Traveling Salesman Problem to Public Key Cryptosystem Tsutomu ANSAI, Hiroaki MATSUYAMA, Takahiro HAYATA, Kunikatsu KOBAYASHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | NP complete problem / the traveling salesman problem / public key cryptosystem / Fibonacci number / backtracking method / LLL algorithm |
| Paper # | ISEC2000-91 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2000/11/6(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) | An Application of the Traveling Salesman Problem to Public Key Cryptosystem |
| Sub Title (in English) | |
| Keyword(1) | NP complete problem |
| Keyword(2) | the traveling salesman problem |
| Keyword(3) | public key cryptosystem |
| Keyword(4) | Fibonacci number |
| Keyword(5) | backtracking method |
| Keyword(6) | LLL algorithm |
| 1st Author's Name | Tsutomu ANSAI |
| 1st Author's Affiliation | Faculty of Engineering, Yamagata University() |
| 2nd Author's Name | Hiroaki MATSUYAMA |
| 2nd Author's Affiliation | Faculty of Engineering, Yamagata University |
| 3rd Author's Name | Takahiro HAYATA |
| 3rd Author's Affiliation | Faculty of Engineering, Yamagata University |
| 4th Author's Name | Kunikatsu KOBAYASHI |
| 4th Author's Affiliation | Faculty of Engineering, Yamagata University |
| Date | 2000/11/6 |
| Paper # | ISEC2000-91 |
| Volume (vol) | vol.100 |
| Number (no) | 421 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |