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.
Fields of Study & Subjects
Formal Methods in Verification
Spacecraft Dynamics and Control
Vehicle Routing Optimization Methods
Publication details
- Journal / source
- IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences
- Publisher
- Institute of Electronics, Information and Communications Engineers (IEICE)
- Volume
- E109.A
- Issue
- 9
- Pages
- 1499–1509
- Publication date
- 25 March 2026
- Language
- EN