Witness-based Encryption — Using an NP Problem To Encrypt a Message

And so the pirates have gathered together and pooled their gold and doubloons, putting 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— creates a difficult Sudoku puzzle:

He then posts the details of the locations on the grid for which to find the 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 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…