Today’s puzzle is based on a ground-breaking mathematical concept which last week won one of its pioneers the Abel Prize, considered the Nobel Prize of maths.
The concept is the zero-knowledge proof, and it has many applications in digital cryptography. Let me briefly explain.
Usually in maths – and in life – when you want to prove a statement is true you need to give evidence to back up your claim. With a zero-knowledge proof, however, it is possible to prove a statement is true without revealing any supporting information.
For example, just say I have solved an extremely hard Sudoku, and I want to prove to you that I have solved it. A zero-knowledge proof will convince you that I have solved it without revealing anything at all about my solution.
Baffled? You are in good company. When the zero-knowledge proof first appeared in the 1980s, the wider mathematical community was agog. The whole idea seemed bizarre and counter-intuitive. Ultimately, however, it represented a conceptual revolution in how mathematicians think about proof, and it has found fantastic applications in cryptocurrencies and crypto-systems, where users want to establish trust but keep crucial information confidential.
Let’s get to the puzzle, and continue the discussion later.
The stolen paper clip
You work in an office of 100 people. One day your favourite paper clip is stolen. You have a pretty good idea of who did it. Your colleague Annabel tells you that she also has a pretty good idea.
You want to check with Annabel that you both suspect the same person, but neither of you are willing to identify your suspect just in case you are thinking of different people. (Because of office politics, no one wants to point fingers.)
Think of a method that allows you and Annabel to check whether your suspect and her suspect are the same person, without either of you revealing any information about your suspects.
What the puzzle is asking is this: can you and Annabel agree on a way to compare your information without giving anything away? At the end of your ‘comparison’ either you will have established that your suspects are the same person, or you will have established that they are not. In the latter case, you will not have leaked any information to Annabel, nor will she have leaked anything to you. The verification procedure is thus ‘zero-knowledge’, since no knowledge is divulged bar the truth, or falsity, of the verification itself.
I agree, it sounds impossible!
Here’s one thing you can’t do: you cannot share anything with Annabel that will identify your suspect. You can’t say, for example: ‘My suspect gets in late on Mondays,’ since that reveals some information about that person.
Usually in the column I say NO SPOILERS (in capital letters!). But today is different since I am asking you to contort your brain in a way you have probably never contorted it before. And there are many solutions, each with strengths and weaknesses.
Here’s one: Imagine that you and Annabel have a good friend Dan, who you both trust. Here’s a method involving Dan that works:
STEP 1 You and Annabel agree on a way to allocate a number from 1 to 100 to everyone in the office.
STEP 2 You write down the number of the person you suspect on a piece of paper. Annabel does the same.
STEP 3 You hand Dan the two pieces of paper, and you ask him to tell you if both pieces have the same number.
If Dan says the numbers are the same, you know the suspects are the same. If the numbers are different, the suspects are different, and neither you nor Annabel are any the wiser about who the other person suspects. Job done!
The Dan option isn’t perfect, however. First, it relies on there being a Dan, i.e. an independent and truthful verifier, which may not always be the case. More importantly, you are both revealing some information to Dan. The whole point of this exercise is to never reveal anything to anyone. Is there a way that does not involve anyone else?