Earlier today I set the following puzzle, based on the remarkable mathematical concept of a ‘zero-knowledge proof,’ which has applications in cyber security. (To find out why this concept is so revolutionary, and how it relates to the puzzle, you can read the original article here.)

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.

SOLUTIONS

There are many solutions, each with strengths and weaknesses. Here are three of my favourites:

1. Computer says yes/no

Change one of your passwords (for any website) to the name of your suspect. Ask Annabel to log on to that website as you. If she gets in, that means she has typed in the same name. If she doesn’t get in, that means has not typed in the same name.

Pro: Very easy to implement. Con: do you trust the computer?

2. Book a flight

Call an airline and book a flight under the name of your suspect. Ask Annabel to call the airline and cancel the booking of the name of her suspect. If the person on the phone says ‘there is no one with that name on the plane’, you know that the suspects’ names dont match.

Pro: it’s amusing. Con: you are giving information away, even if you are giving it to someone who is bound to secrecy.

3. The 100 Cups

Agree on a numbering from 1 to 100 of the staff. Line up 100 identical cups so that each is in a position marked from 1 to 100. You and Annabel take 100 identical slips of paper. You each write YES on one piece of paper, NO on the other 99 slips, and fold them so you can’t see what is written on them.

You and Annabel place your YES slip in the cup of number of the person you each suspect, and the NO slips in the other cups. You then rearrange the cups so no one knows which is which.

Finally, you go through the cups unfolding the slips. If the two YES slips are in the same cup, then you know you are suspecting the same person. If there are not in the same cup, you are suspecting different people.

Pro: simple, involves no third party. Con: quite a faff sourcing the cups. Do you trust the randomisation process? Are you poker-faced enough not to give away when you put your YES in the cup?

Discussion

The three solutions above are inspired by the paper Comparing Information Without Leaking It by Ronald Fagin, Moni Naor and Peter Winkler. It has other suggestions too and is worth a read if you want to look more deeply into this area.

As I write this, more than 300 comments under the original article have generated some excellent other suggestions, many of them variations of the 100 Cups solution. Please carry on inventing more and post them below here.

Thanks for all the interaction – it’s been great fun. And look after your paper clips!

I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.

I’m the author of several books of puzzles, most recently the Language Lover’s Puzzle Book.