Treasure Finding For Pirates: Meet Witness-based Encryption

Treasure Finding For Pirates: Meet Witness-based Encryption

And so the pirates have got together and pooled their gold and doubloons and put them all into a treasure chest. Now they bury it at a secret location on Pirate Island. In order to hide the location, they create a puzzle to be solved, and if someone can solve it, they will find out the location of the treasure and win the booty.

And so the pirate leader — Long John Silver XXII — creates a difficult Sudoku puzzle:

He then posts the details of the locations on the grid for which to find details of the secret treasure location. Now the pirates scratch their heads, as they are good pirates but they are not so good at solving puzzles … “Shiver me timbers! I be ah pirate and I’m not ee puzzle solver”.

But the pirates know people in the Ye Olde Ship Inn who know how to solve puzzles. Unfortunately their “day rate” is five pieces of silver. So young Jim Lad XXII decides to ask one of the puzzle solvers for a quote, and is told that this type of puzzle will take two days to solve. And so Jim Lad thinks it is worth paying for the answer, and so, after two days, the puzzle solver reveals the answer, and Jim Lad claims his prize.

What we have here is Witness encryption, and where Long John Silver XII knew exactly how much it would cost to solve his puzzle, and where Jim Lad solves one puzzle, but would then have to get another solver to solve the next one. In this way, Jim Lad hasn’t actually discovered how to solve the puzzle, and it will cost him more money the next time he does it.

The research around Witness encryption was proposed by Garg et al in 2013 [here], and now we see a new encryption method being defined [paper]:

At the core of their work is the integration of an NP-complete problem, and where we can define the difficulty level of the problem. In most solutions to this, we create a puzzle where the witness of the pirates would only have to reveal part of the solution. Basically what we have is a time-locked solution, and where we will know exactly how long the puzzle will take to be solved (and what the cost will be).

This is a common problem in zero-knowledge proofs, and where we must reveal a sub-solution to a problem. Let’s say that Peggy (the troll) wants to make sure that Victor (you) know a 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 [here].

The main contribution of this new paper is that it uses puzzles which reveal an exact solution. Along with Sudoku, they define Pentomino, and where the shapes on a board must fit exactly into an 8x8 grid and where we have P pieces (and with four squares removed in the centre):

Their solution is the creation of Pentomino-based witness encryption, Sudoku-based witness encryption and Nonogram-based witness encryption. With a Nonogram puzzle, we have an NP-complete problem and has an exact solution. We first create a board where rules must be followed for the rows and columns and which relates to the number of filled-in and empty squares. For example, we might have “3 1 1” for a row and where we need three filled-in squares and then spaces with single squares. There is then rules for columns, too. The following shows an example:

The authors hope to create a generalised encryption infrastructure, and where an NP-complete problem could be added as a puzzle.

Hah-har, Happy New Yeer!