The Travelling Salesman Cipher

Abstract

A new scheme of public key cryptosystem based partly on the popular travelling salesman problem which is NP-complete and partly on a database ciphering scheme proposed by Davida, Wells and Kam which is based on the Chinese Remainder Theorem is presented. The scheme provides secrecy but no authentication.

Indexing terms:

• Cipher Secrecy
• Knapsack
• Travelling salesman problem
• NP-complete
• Chinese remainder theorem
• Public key