“The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.

Two sheriffs in neighboring towns are on the track of a killer, in a case involving eight suspects. By virtue of independent, reliable detective work, each has narrowed his list to only two. Now they are engaged in a telephone call; their object is to compare information, and if their pairs overlap in just one suspect, to identify the killer.

The difficulty is that their telephone line has been tapped by the local lynch mob, who know the original list of suspects but not which pairs the sheriffs have arrived at. If they are able to identify the killer with certainty as a result of the phone call, he will be lynched before he can be arrested.

Can the sheriffs, who have never met, conduct their conversation in such a way that they both end up knowing who the killer is (when possible), yet the lynch mob is still left in the dark?

It has different solutions. But the question is why this puzzle is unsolvable for seven suspects?

Original problem was discussed at Puzzling. There are some solutions here.

EDT. Let me summarize the discussion from comments.

1. Formal success conditions (due to usul): "A deterministic communication protocol such that, for any singly-overlapping sets held by the sheriffs, the sheriffs always deduce the correct suspect, and the mob has no deterministic strategy to always guess the correct suspect."

2. It is a mathematical problem. Original problem has absolutely consistent solution. (It does not use any cryptographic assumptions.)

3. Puzzling solution is wrong and the number of suspects is important here.

4. (Due to usul.) This problem is very close to many types of problems in CS, such as zero-knowledge proofs and secure multiparty communication, but so far it is not clear if exactly this type of problem being studied.

• Your question is perhaps more suitable for the puzzling stack exchange website? – coudy Apr 17 '15 at 12:39
• What are the rules governing their conversation? If they can simply use public-key cryptography, then the problem is not particularly interesting! – James Cranch Apr 17 '15 at 14:55
• I think there is a valid mathematical question here that is better asked either here or MSE, depending on what level it is, rather than on a puzzle site. However, to fit MO, you should at least link to what is known. You can use a spoiler mark-up: Start each paragraph with >! to hide it until you mouse over it. – Douglas Zare Apr 17 '15 at 15:13
• Clearly the lynch mob can break public-key cryptography, so you can't use it. – Yakky Apr 17 '15 at 17:20
• Privacy-preserving joint computation is an important, and increasingly relevant problem in computer science. I don't know the state of knowledge about the set intersection problem, but you should check out the following papers: dx.doi.org/10.1007/978-3-540-24676-3_1 and dx.doi.org/10.1007/978-3-642-14577-3_13 – Yoav Kallus Apr 17 '15 at 17:47

Here's a solution for the case of seven suspects that uses the Fano plane. Let the seven points of the Fano plane represent the seven suspects. Alice and Bob both reveal the name of the suspect completing a line with the two suspects on their list. There are now two cases to consider:

1. Alice and Bob did not name suspects on each other's lists. Then the suspicion (among the sheriffs) is reduced to the four suspects not named and not completing a line with the two suspects named. Alice knows that Bob is uncertain if Alice's list is the list which is correct or its complement. Same for Bob. Alice reveals her list. Bob reveals his. Both now know the culprit. Eve would also know, assuming she knew that we are in case 1, but she doesn't.

2. Alice named one of Bob's suspects, and since we are assuming their suspect lists have an intersection of size 1, Bob named one of Alice's suspects. Both sheriffs know this, but Eve doesn't. Also, both sheriffs now know who the culprit is. The rest of the conversation is only in order to not reveal to Eve that case 2 is occurring. Alice names two suspects that make a line with her first-announced suspect, but don't include Bob's first-announced suspect. Bob does the same.

The protocol is not deterministic when it falls into case 2, requiring arbitrary choice, but I fail to see why you want determinism.

• Re your last sentence, but the protocol can be made deterministic by making one of the arbitrary choices. – usul Apr 18 '15 at 20:57
• Brilliant to use the Fano plane! – Joseph O'Rourke Apr 18 '15 at 21:02
• Note that Bob's last action in case 2 is a little more constrained, to avoid giving away that they're in case 2; the list Bob reveals has to overlap the one Alice reveals. So he has to pick one of the two points Alice named, together with the remaining point on the line between it and the point he originally named. – Harry Altman Apr 18 '15 at 21:49
• @HarryAltman Bob does not need to be careful since there will always be exactly one point of intersection for all four possible choices of the last steps. – Tony Huynh Apr 18 '15 at 23:27
• @usul, I don't think it can. Note that from Eve's point of view after Alice and Bob's first announcements, one instance of case 2 can match four different instances of case 1. If Alice and Bob have a deterministic choice in case 2, then they have to pick a single instance of case 1 to mimic, which means that the other three instances are never mimicked and always correspond to case 1. – Yoav Kallus Apr 19 '15 at 0:49