In a maze ... do you know the way back? How to find out if I know a secret.

So we all know that passwords are nearing the end of their usefulness, and that hashed version of passwords can often be cracked. So what other method do we have for proving things? Let's play a game that's easy for you, but difficult for others.

Into the maze

Now we have a complex maze in front of us, and I want to know if you know the secret way through the maze, but others are listening, so how do I make sure you know?

This is a common problem in zero-knowledge proofs. In this case Peggy wants to make sure that Victor knows the secret (the way though the maze), but does not want him to reveal it. For this we have a Hamiltonian cycle - which is the route through a maze which returns to the same point, and where we visit each of the junctions (vertices) on the maze. If the maze is complex, and Peggy provides a map of the maze which has different labels for the junctions, it will be difficult for Eve to find the Hamiltonian cycle.

As an example let's take an extremely simple maze:

We could walk from 1 to 3 to 5 and then back to 1, but we have missed out 2 and 3. So what is a solution for us to be able to visit each junction (vertice) just once? In this case the Hamiltonian cycle will be 1 -> 5 -> 4 -> 2 -> 3 -> 1, and which return as back to 1, and having visited all the junctions (vertices) in the maze.

In this case we have 10 Hamiltonian cycle routes, with two which will return to the starting point (1):

1 -> 5 -> 4 -> 2 -> 3 -> 1

1 -> 3 -> 2 -> 4 -> 5 -> 1

3 -> 2 -> 4 -> 5 -> 1 -> 3

3 -> 1 -> 5 -> 4 -> 2 -> 3

2 -> 4 -> 5 -> 1 -> 3 -> 2

2 -> 3 -> 1 -> 5 -> 4 -> 2

5 -> 4 -> 2 -> 3 -> 1 -> 5

5 -> 1 -> 3 -> 2 -> 4 -> 5

4 -> 5 -> 1 -> 3 -> 2 -> 4

4 -> 2 -> 3 -> 1 -> 5 -> 4

We have 12 Hamiltonian paths - which are routes where we go to every node, but don't have to end at the same one:

1 -> 5 -> 4 -> 2 -> 3

1 -> 3 -> 5 -> 4 -> 2

1 -> 3 -> 2 -> 4 -> 5

3 -> 2 -> 4 -> 5 -> 1

3 -> 1 -> 5 -> 4 -> 2

2 -> 4 -> 5 -> 1 -> 3

2 -> 3 -> 1 -> 5 -> 4

5 -> 4 -> 2 -> 3 -> 1

5 -> 1 -> 3 -> 2 -> 4

4 -> 2 -> 3 -> 5 -> 1

4 -> 5 -> 1 -> 3 -> 2

4 -> 2 -> 3 -> 1 -> 5

While this looks simple; for a complex graph, it is computationally infeasible to find the Hamiltonian cycle as it is a know as NP-complete. Peggy just has to show to Victor that she knows the Hamiltonian cycle, and then Victor will know that she knows the secret.

So let's go

Both Peggy and Victor know the original graph (G) of the maze, and Peggy knows the Hamiltonian cycle for it. Peggy then recreates a new graph (H) with the same connections, but with different names for the nodes (vertices). As the graphs are the same in their structure, Peggy will easily be able to translate between the two graphs. For example, she can change the labels to letters ('A', 'B',...):

?As it's the same structure for the graph (G), Peggy will be able to find the Hamiltonian cycles, but others, such as Eve, will have to search for them, and which is an extremely difficult problem for a complex graph.

Victor will then ask Peggy some questions. He can either ask her to show how she converted from G to H, or to reveal a Hamiltonian cycle in H. If she reveals the Hamiltonian cycle, she will show the translation (the route) for it to Victor. Eve will struggle to find a Hamiltonian cycle within reasonable time limits.

So what?

This solution is an example of the travelling salesman problem (TSP) where a salesman must visit each city only once, and return to the same city they started from. This is known to be a NP-complete problem, and is perfect for a puzzle which is easy to solve if we know the answer, and difficult if we don't. In this way we have a puzzle which is easy for Peggy to solve, but Eve will find it difficult with a new graph each time.

So, increasingly we will see puzzles appearing, and which aim to be easy to solve if you are how you say you are, but difficult - if not near impossible - if you are not.

Well ... here's a little calculator that can be used to compute the Hamiltonian edges and cycles [link]: