The only way is zero … Can you get past the Troll?

The only way is zero … Can you get past the Troll?

With GDPR well under way, companies will have to invest in new ways of authenticating systems, and the storing and revealing of passwords, even in a hashed form. Overall the usage of passwords and a login ID is an archaic method and which needs to be replaced by ever-changing challenges. A key element of this is the concept of NP-complete — a problem which can be solved in polynomial times (eg x²) with a non-deterministic method. This article outlines one of the basic methods which can be used for zero-knowledge proof — and where someone knows something, but does not reveal their core knowledge, and proves that they know it instead.

A demonstration of the method used in this article is here.

Into the maze

I want you to pick my secret treasure which is in a maze, and which is guarded by a troll. I’ve told the troll that I will send someone to pick up the treasure, and that they can tell whom I send because the will find their way through the maze.

So I show you the maze, and you set off. When you get there, there are a whole lot of people there who also say I have sent them, and want to get into the maze. But how do the troll know I sent you, as others are listening? Let’s say you are Victor and the troll is named Peggy (which is a nice name for a troll!), and that Eve, the Beast, is listening to every word that you say.

This is a common problem in zero-knowledge proofs. In this case Peggy (the troll) wants to make sure that Victor (you) know the secret (the way through 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 known 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), Victor will be able to find the Hamiltonian cycles, but others, such as Eve the Best, will have to search for them, and which is an extremely difficult problem for a complex graph.

Peggy (the troll) will then ask Victor some questions. She can either ask him to show how he converted from G to H, or to reveal a Hamiltonian cycle in H. If he reveals the Hamiltonian cycle, he will show the translation (the route) for it to Peggy. 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].

Conclusions

We need more puzzles, and continual changes. We also give away too much of our identity when we enter our personal details. Every time you enter your password, you are at risk. We must move to systems which show that you known you password, or your date of birth, without actually giving it away.

Get Best Software Deals Directly In Your Inbox