Zero Knowledge Proof using Hamiltonian Cycles

The last post explored the idea of Zero Knowledge Proofs (ZKPs) using simple examples. Now it is time to take a deep dive into a fully functional ZKP based on a mathematical problem instead of hidden doors amongst neighboring houses. The basic problem is very simple: A Hamiltonian path is a path through a given graph which visits every vertex exactly once. Hamiltonian paths are related1 to the better known Eulerian paths, which visit every edge exactly once.

Zero Knowledge Proofs of Knowledge

Proving one’s identity is hard business. Part of that hardness comes from philosophical questions like “If I stop liking computers, does that future me constitute a different person?”. In a way, some of these problems are repeated in the biometrics area, which have to distinguish between “real identities” and things that may look the same to their sensors, or even people that lose the things that provided their identity in accidents.