Efficient Physical ZKP Protocols for Hamiltonian Cycle Problem and Traveling Salesman Problem

Abstract

The Hamiltonian cycle problem is a well-known NP-complete problem in graph theory. This problem relates to lots of practical problems such as designing very large scale integration (VLSI) and travel-ling salesman problem (TSP). Since it is NP-complete, there is no efficient algorithm to solve the Hamiltonian cycle problem, and hence, its solution is valuable. In this paper, we propose new physical zero-knowledge proof protocols for the Hamiltonian cycle problem, whereby an entity can prove its knowledge of a solution to another entity without leaking any information about the valuable solution. Our protocols are more efficient than the previous protocols. We also propose a physical zero-knowledge proof protocol for TSP, one of whose building blocks is a new representation of an integer commitment with a secure addition protocol.