Three colleagues want to know if one of them paid the bill, without revealing who
Three cryptographers are told their dinner has already been paid for — either by one of them, anonymously, or by an outside party like their employer. They want to determine which case is true, but if one of them did pay, that person's identity must stay completely secret, even from the other two. Each can only make a public statement to the group. How can they find out?
Reveal the answer
Each pair of neighbouring cryptographers secretly flips a coin only the two of them see, so everyone observes two coin outcomes: their own flip and their neighbour's. Each person then announces whether the two coins they saw matched or differed — except the payer, if there is one, who announces the opposite of what they actually saw. XOR the three public announcements together: an even result means no one at the table paid, an odd result means one of them did, with no way to tell who. David Chaum devised it in the 1980s as a founding idea behind anonymous communication networks.