Presentation 2002/12/9
Discussion on security of the TSP cryptosystem
Takahiro MINAMI, Akira HAYASHI,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) The traveling-salesman cryptosystem is a public key cryptosystem to which the traveling-salesman problem is applied. The well-known traveling-salesman problem is a difficult problem that belongs to the class of NP complete problems. The inventors of this cryptosystem have claimed that this system is safe against the low density attack, because the density associated with this system can be greater tha unity. We will, however, report in this paper that this system can be broken by the Lagarias-Odlyzko attack and its variants,
Keyword(in Japanese) (See Japanese page)
Keyword(in English) NP complete problem / traveling-salesman problem / public key cryptosystem / cryptanalysis
Paper # ISEC2002-101
Date of Issue

Conference Information
Committee ISEC
Conference Date 2002/12/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) Discussion on security of the TSP cryptosystem
Sub Title (in English)
Keyword(1) NP complete problem
Keyword(2) traveling-salesman problem
Keyword(3) public key cryptosystem
Keyword(4) cryptanalysis
1st Author's Name Takahiro MINAMI
1st Author's Affiliation Kanazawa Institute of Technology()
2nd Author's Name Akira HAYASHI
2nd Author's Affiliation Kanazawa Institute of Technology
Date 2002/12/9
Paper # ISEC2002-101
Volume (vol) vol.102
Number (no) 511
Page pp.pp.-
#Pages 4
Date of Issue