Traveling salesman cryptosystem using Gaussian integer

摘要

We propose a public key cryptosystem using the traveling salesman problem that is a NP complete problem. Gaussian integers are assigned to edges of the graph. The cipher text is obtained by using the mixed sum and product operations of Gaussian integers. This cryptosystem is secure against the attacks using LLL algorithm and Shamir algorithm.