Assign each suspect a number $1-7$. Define the xor of two numbers between $1$ and $7$ as follows: write them in binary, then xor them together bitwise. For example, $3 \oplus 6=011\oplus 110=101=5$.
Some observations:
$a\oplus b$ is different from both $a$ and $b$.
If $a\oplus b=c$ and $d\oplus e=f$, then the sets $\{a,b,c\}$ and $\{d,e,f\}$ have an element in common. This can be verified by checking the only sets of three numbers where two of them xor together to make the other are {1,2,3},{1,4,5},{1,6,7},{2,4,6},{3,4,7},{3,5,6},{2,5,7}, and that any two of these intersect.
The converstion: Lets say Alice has {a,b} and Bob has {a,c}. Alice announces $a\oplus b$ and Bob announces $a\oplus c$. If Alice and Bob say the same thing, then they know they have the same pair, and hang up. If not, there are two possibilities:
- $a\oplus b\neq c$. Then it also follows that $a\oplus c\neq b$, so neither Sheriff said a number in the others list. In this case, they each announce their pair, ${a,b}$ and ${a,c}$.
- $a\oplus b=c$, which also implies $a\oplus c=b$. They now each say a random pair whose xor is what they first announced, except for their actual pair.
Why the sheriffs know the killer: It's easy to see why they do in case 1, since they each heard the other's pair. In case, 2, when Alice hears Bob say $b$, she knows $b$ is not the killer, so it is $a$. Same thing happens for Bob.
Why the lynch mob doesn't: Suppose that they hear the numbers $a_1$ and $b_1$, followed by the pairs ${a_2,a_3}$ and ${b_2,b_3}$. It could be the case that Alice had the pair ${a_2,a_3}$ and Bob has the pair ${b_2,b_3}$, in which case the killer would be the intersection of these sets (this would be case 1). However, it could also be the case that Alice had $\{a_1\oplus b_1,b_1\}$ and Bob had $\{a_1\oplus b_1,a_1\}$. Here we are in case 2, where Alice and Bob just randomly chose to say $\{a_2,a_3\}$ and $\{b_2,b_3\}$. No matter what sets they randomly announced, by bullet point 2, they will always intersect, so this is really indistinguishable from case 1.
For example, here are two situations where the Sheriffs have the same conversation, but the killer is a different person.
Alice has {1,2}, while Bob has {1,5}. Alice says 3, Bob says 4. Since 4 is not in {1,2} and 3 is not in {1,5}, we are in the first bullet point. They then each announce their lists, {1,2} and {1,5}. They now both know that the killer is 1.
Alice has {4,7}, Sheriff 2 has {3,7}. Alice says 3, Bob says 4. Each number is in the other's list, we are in the second bullet point. They know now the killer is 7. Alice randomly announces one of the pairs {1,2} or {5,6}, since these are the pairs which xor together to make 3 (besides {4,7}). Let's say she chooses {1,2}. Similarly, Bob randomly says one of {1,5}, or {2,6}, and he randomly chooses {1,5}.
