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.

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 -> 11 -> 3 -> 2 -> 4 -> 5 -> 13 -> 2 -> 4 -> 5 -> 1 -> 33 -> 1 -> 5 -> 4 -> 2 -> 32 -> 4 -> 5 -> 1 -> 3 -> 22 -> 3 -> 1 -> 5 -> 4 -> 25 -> 4 -> 2 -> 3 -> 1 -> 55 -> 1 -> 3 -> 2 -> 4 -> 54 -> 5 -> 1 -> 3 -> 2 -> 44 -> 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 -> 31 -> 3 -> 5 -> 4 -> 21 -> 3 -> 2 -> 4 -> 53 -> 2 -> 4 -> 5 -> 13 -> 1 -> 5 -> 4 -> 22 -> 4 -> 5 -> 1 -> 32 -> 3 -> 1 -> 5 -> 45 -> 4 -> 2 -> 3 -> 15 -> 1 -> 3 -> 2 -> 44 -> 2 -> 3 -> 5 -> 14 -> 5 -> 1 -> 3 -> 24 -> 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.

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.

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

Coinmonks

Coinmonks is a non-profit Crypto educational publication.

Sign up for Coinmonks

By Coinmonks

A newsletter that brings you week's best crypto and blockchain stories and trending news directly in your inbox, by CoinCodeCap.com Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store