Comparing Information Without Leaking It

Bob comes to Ron, a manager at his company, with a complaint about a sensitive matter; he asks Ron to keep his identity confidential. A few months later, Moshe (another manager) tells Ron that someone has complained to him, also with a confidentiality request, about the same matter.

Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.

The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.

What can Ron and Moshe do in order not leak more information than necessary?

Discussion and pointers


Back to the Puzzler page