# Two Sheriffs and Eavesdroppers

Two sheriffs are working on a case to find one culprit. There were initially 8 suspects; through independent work, each sheriff has narrowed this down to a list of 2. Because they are good sheriffs, they can be sure that both of their lists contain the culprit. They plan to make a phone call tonight to see if they can combine their information to find the culprit. However, the locals (who know the 8 suspects, but neither of the narrowed lists) have tapped their phone line. If the locals can figure out the culprit based on this phone call, then they will lynch him before he can be brought to justice.

How can the sheriffs conduct their conversation so that they can both deduce the culprit, when possible*, but the locals can't?

*If the sheriffs have the same list of 2 suspects, then they won't be able to deduce the culprit. As long as their lists are different, they can. The lists cannot be disjoint, since they both contain the unique culprit.

Source: Mathematical Puzzles, a Connoisseur's Collection, Peter Winkler

• Are the Sherriffs on mobile phones? – DJClayworth Mar 30 '15 at 20:41
• Can't the Sheriffs goes like "Hey I think it's suspect #1,#3", "#1,#2 here, so I think it's suspect #1" and only they know who's #1 on the list – Alex Mar 30 '15 at 21:03
• @Alex, that doesn't work, since this assumes they had a secret encoding, mapping suspects to numbers, that the locals didn't know about. Any such encoding must be agreed upon over the phone. – Mike Earnest Mar 30 '15 at 22:49
• they can exchange public keys, à la Alice and Bob. – njzk2 Mar 31 '15 at 21:13
• This problem admits a solution for 7 suspects. Solution is not mine. I've asked this problem as a separate question here: Two Sheriffs and Eavesdroppers - 2 puzzling.stackexchange.com/questions/12555/… – Alexey Ustinov Apr 22 '15 at 5:53

Let's say S1 has the list {a,b} and say S2 has {a,c}.

S1: {a,b}, {c,d}, {e,f}, {g,h} - one of these is my list.

S2: {a,c}, {b,d}, {e,g}, {f,h} - one of these is mine.

Now both S1,S2 know their sets are inside {a,b,c,d}, whereas because of symmetry, it could be {e,f,g,h} or {a,b,c,d} as far as eavesdroppers are concerned.

So S1 and S2 play a game revealing info but keeping this info symmetric in the other set too.

S1: {a,e}, {b,f} - These lists have my suspects. S2: Knows the culprit is a (since he knows S1's set now).

S2: {a,e} - The culprit is in this list. S1: Knows the culprit is a.

Each time, the eavesdroppers can't distinguish between the two sets; finally they can't distinguish between a and e.

• My solution also works, but yours is neater! +1 :-) – Rand al'Thor Mar 30 '15 at 23:14
• Well done! Even cleaner than the answer I had. I think it's good to emphasize that $S_1$ chooses his first four sets arbitrarily, but $S_2$ chooses them to create the desired symmetry. Also, after $S_1$'s first statement, $S_2$ might say, "My pair is in that list" and hang up – Mike Earnest Mar 30 '15 at 23:14
• @Mike: Except that $S_2$'s pair is not in the list. – Ian MacDonald Mar 30 '15 at 23:59
• A sufficiently motivated mob would lynch both individuals in the final set. – FreeAsInBeer Apr 1 '15 at 15:03
• @FreeAsInBeer lol... well, sufficiently motivated mob would lynch all the 8 suspects since they are not literate enough to tap a phone line :D – Ennar Apr 1 '15 at 20:09

I think it's pretty obvious.

They discuss a meeting place on the phone and then talk about it in person.

;)

Alternatively,

one sheriff reads his two suspects' names. The other sheriff says nothing and goes to arrest the culprit.

• trololololololol – Mike Earnest Mar 30 '15 at 20:45
• Haha that was going to be my original answer – Ben Mar 30 '15 at 20:49
• Since the phones are tapped, the lynch mob appoints a member to go spy on them. The second answer is golden. If the second sheriff has the same two names they can always say something like "Well that tells me nothing." – Michael Mar 31 '15 at 18:38
• +1 for best answer, since sheriffs are great at enforcing the law, but not so good at Set Theory. – Michael Mar 31 '15 at 18:38
• Aha, @Michael! I present: Quantum Cop! Casey & Andy, by Andy Weir. – Dacio Mar 31 '15 at 20:05

They each encrypt their list with the other sheriff's RSA public key. They then read the encrypted string over the phone to the other, and each sheriff then decrypts the other's list using his own private key :).

It's going to be a long phone call.

I haven't taken computer security in a while so I hope I got the process right, I was just kinda going off the top of my head.

• Creative, but there is a much more elegant solution, one that can be executed in just a couple minutes with no need for computer assistance or complex math. Also, there is a solutions which provably leaks no information, even if the townsmen have infinite computing power. RSA in theory can be broken by brute force. – Mike Earnest Mar 30 '15 at 20:39
• I figured as much; my answer was mainly just for people's amusement. I'm curious to see what the actual answer is though! – Ben Mar 30 '15 at 20:41
• on such a short message rsa can't be broken, since the message is shorter than the key – njzk2 Mar 31 '15 at 21:16
• This was my immediate solution. – dwjohnston Mar 31 '15 at 21:38
• @MikeEarnest: Are there any solutions which would in all cases leave the villagers with at least three possible suspects? Reducing the villagers' suspect pool from 8 to 2 constitutes releases some information (quite a lot, actually) even if it keeps one bit of information secret. – supercat Mar 31 '15 at 22:36

I'm finding one small issue with mine (in the worst case scenario), so hopefully this will help someone else.

One sheriff reads names NOT on his list ("I know it isn't ____) until he reads a name on the second sheriff's list. We know the first sheriff will have to say some name he knows it isn't that the second sheriff thinks it is, or the case is unsolvable.
The second Sheriff now knows the culprit. The second sheriff can now begin the same process ("I know it isn't ____") until he reads a name on the first sheriff's list. He needs to stop before the final name though if he gets that far, or he could still reveal who the culprit is (if the two sheriff's have together said it isn't 7 of the 8).

I realize this isn't fullproof, given the situation of:

If luck is really bad and the second sheriff reads the entire list and the two remaining names (the culprit, and last person unsaid to avoid giving too much away) are both suspects to the first sheriff. Then this way wouldn't work.

Call the suspects A, B, C, D, E, F, G, H, and assume the suspect-pairs listed by each sheriff are distinct (so that the problem is soluble).

• Sheriff 1 picks a size-4 subset $S_1$ of the suspects, including exactly one from 1's list, and asks 2 how many of $S_1$ are on 2's list. If 2 says "none" or "two", 1 knows who the culprit is. If 2 says "one", 1 asks whether the other suspect from his list (the one not in $S_1$) is on 2's list in order to determine the culprit.

• Sheriff 2 picks a size-4 subset $S_2$ whose intersection with $S_1$ has size 2 and which includes exactly one from 2's list (this is always possible, and if 2 said "one" before, he chooses $S_2$ to contain the person 1 then asked about). He then asks 1 how many of $S_2$ are on 1's list. If 1 says "none" or "two", 2 knows who the culprit is. If 1 says "one", 2 asks whether the other suspect from his list (the one not in $S_2$) is on 1's list in order to determine the culprit.

Let's see how this works from the point of view of the eavesdroppers. WLOG, say $S_1=\{A,B,C,D\}$ and $S_2=\{A,B,E,F\}$.

If 2 and 1 both say "two", all they know is the culprit is one of A,B. If 2 and 1 both say "none", all they know is it's one of G,H. If 2 says "two" and then 1 says "none", all they know is it's one of C,D. If 2 says "none" and then 1 says "two", all they know is it's one of E,F.

If 2 says "one", the person 1 then asks about must be one of E and F (by the way the strategy was set up). Say it's E, since the F case is similar. If 1 says "two", the locals know either that the culprit is one of A,B,E or that it's one of A,B,F (depending on 2's second answer). If 1 says "none", the locals know only that the culprit is one of C,D,G,H. If 1 says "one", he then has to answer a question on one of C,D,G,H, and the locals still have at least six possibilities (maybe even more, depending on 2's and 1's second answers).

So the locals cannot narrow down their possibilities to a single suspect, but both the sheriffs can if it's at all possible.

• I like your answer better than the accepted once, since it guarantees that the eavesdroppers will have at least three possible suspects. If the eavesdroppers get down to two they might just decide to lynch whichever one seemed more guilty. – supercat Mar 30 '15 at 23:37
• Unfortunately, no: in some cases they're down to two with my method too. But thanks :-) – Rand al'Thor Mar 30 '15 at 23:39
• I'm really, really confused by this answer. Could you list an actual sample conversation when someone says there's one of theirs in the subset? Right now, it seems like if 1 asks "is E on your list," 2 might say "yes" and that would mean that E is on both lists. – cpast Apr 1 '15 at 4:10
• Specifically, what happens if 1's list is {A,E}, 2's list is {C,E}, and $S_1$ is {A,B,C,D}? It would seem like 1 would say {A,B,C,D}, 2 would say "one", 1 would then ask about E, 2 would say "yes" (now the mob knows it's E). Or am I misinterpreting it? – cpast Apr 1 '15 at 4:18
• @cpast In the example you give, the mob would only know it's one of A,B,C,D,E. I'm assuming they don't know what strategy the sheriffs have decided on (since the sheriffs don't even need to communicate that to each other in order to get the info they need), so the only thing they know now is that 2's list consists of E and one of A,B,C,D. – Rand al'Thor Apr 1 '15 at 9:20

In actual conversation:

Suspects: 1 2 3 4 5 6 7 8

Sheriff A has 1 2

Sheriff B has 1 5

(Phone rings.)

A: Bad news, someone tapped me.

B: OK. Group suspects into 4 pairs with one pair being your shortlist

A: 12 34 56 78

B: Is it either 12 or 34?

A: Yes

B: (so culprit is 1) culprit is either 1 or 3

A: (so culprit is 1) let's go get him

(Both hang up the phone)

Revised Solution:

Denote suspects $S_A, S_B, S_C$ where $S_C$ is the culprit. Then Sheriff 1 has suspect set $(S_A, S_C)$ and Sheriff 2 has suspect set $(S_B, S_C)$. Sheriff 1 goes on the phone and says one of his suspects. Let us consider each of the cases: a. Sheriff 1 says $S_A$, so therefore Sheriff 2 knows that the other suspect of Sheriff 1 is the culprit. Then Sheriff 2 says $S_B$, and Sheriff 1 says "No." Then we know that Sheriff 1 knows it is his unsaid suspect, and Sheriff 2 knows it is his unsaid suspect. b. Sheriff 1 says $S_A$, so therefore Sheriff 2 knows that the other suspect of Sheriff 1 is the culprit. Then Sheriff 2 says $S_C$, and Sheriff 1 realizes that $S_C$ is the culprit. He says "Yes." But wouldn't that tell the townspeople? No, because had Sheriff 1 replied with $S_C$ first, then Sheriff 2 would've known it was $S_C$, and replied with $S_B$. Then Sheriff 2 could deduce that it must be $S_C$ since he does not have $S_B$, and he would have replied "Yes." In either case, the people would not know whether it was the first or the second said suspect if the reply was "Yes," and they wouldn't know the unsaid suspect if the reply was "No."

• Both of your cases begin with "Sheriff 1 says $S_A$...", was this intended? Also, you seem to be assuming the sheriff's suspect sets are different, it is possible that they both have the sets $\{S_C,S_D\}$, where $S_D$ is not the culprit. – Mike Earnest Mar 30 '15 at 21:26
• @MikeEarnest you're right, this solution doesn't work. I like this puzzle, though. – Addison Mar 30 '15 at 22:26

they number the suspects in binary, then each officer tells the other which digit he needs to incriminate the right suspect. the other officer can either give him that digit right away if he has it, or request a digit himself.

example

officer A has
011
101

officer B has
000
011

officer A needs either the first or second digit.
officer B needs either the second or third digit.
officer A tells B the third digit it 1.
officer B tells A the first digit is 0.

The crude answer to this is that they manually perform a Diffie-Hellman key exchange over the phone.

Then they can just encrypt their lists with AES with the key, and speak it. Surely this isn't the most efficient or effective way, but encryption is the catch-all when it comes to questions of communicating secrets in the open :)

• Equivalent to Ben's answer. – CodesInChaos Mar 31 '15 at 13:24
• @CodesInChaos Ah, missed it. I checked quickly for a cryptography answer. This is slightly different though – Cruncher Mar 31 '15 at 15:16
• @CodesInChaos This answer is better because it doesn't assume the sheriffs have public keys beforehand. – aebabis Mar 31 '15 at 21:55
• @acbabis neither does Ben's. Both parties make a public/private pair, and can safely transmit their public key in clear text(speech) – Cruncher Apr 1 '15 at 16:45
• @Cruncher I didn't say your answer was best. I'm just saying its better than assuming the sheriffs already have public keys in their wallets. (I keep a public key in my wallet BTW) – aebabis Apr 1 '15 at 16:52