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? Feel free to make suggestions below the line about how you might want to approach the problem. Please don’t give a complete solution if you know one, but do help each other and work in groups! I’ll be back at 5pm UK with a solution and further discussion. UPDATE: Read the solution here. I mentioned at the top that the 2021 Abel Prize honoured one of the pioneers of the zero-knowledge proof. His name is Avi Wigderson, aged 64, and he was awarded the prize together with László Lovász, aged 73, for their “leading role in shaping [theoretical computer science and discrete mathematics] into central fields of modern mathematics.” In the 1980s, Wigderson, together with Oded Goldreich and Silvio Micali, showed that any true mathematical statement has a zero-knowledge proof. At the time, this result was a purely theoretical advance, but in recent years zero-knowledge proofs have found important applications in digital security, especially in cryptocurrencies and authentication systems. The zero-knowledge proof allows two people to establish trust while revealing nothing. If you are interested in finding out more about the work honoured by the 2021 Abel prize, you may enjoy this short video I made for the Abel Prize that was broadcast during the announcement ceremony. It gives a layman’s summary of Lovász and Wigderson’s work and (from 4mins) gives an example of a zero-knowledge proof (which may be helpful in trying to solve today’s puzzle.)