11
$\begingroup$

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.

For convenience the original problem (from 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?

Also Yoav Kallus gave to referrences Efficient Private Matching and Set Intersection and Practical Private Set Intersection Protocols with Linear Complexity where more general problem is considered: compute the intersection of private datasets of two parties. (These articles give Private Matching protocols based on usual cryptographic assumptions and for large domains).

But I'm still looking for negative results: is it possible to give lower bound for the number of suspects when the problem admits a solution? (Of course not only for orginal problem but for more general situation: $N$ suspects, two lists of lengths $n_1$ and $n_2$, etc.)

$\endgroup$
4
$\begingroup$

One reformulation of the (original) problem that is easy to work with is given below. It shows that no strategy can work for $3$ suspects. I tried to prove the same for $4$ suspects, but there were too many cases, which I believe could be checked by a program.

Two players each hold one edge from a complete graph, whose intersection is one vertex. According to some protocol, in each step one of them can reveal that a certain edge is not hers. We can imagine that in every step each of them holds some graph, $G_A$ and $G_B$, which are getting smaller. The game ends when each edge $e$ of $G_A$ has a vertex $v$ such that every edge $f$ of $G_B$, that is not disjoint from $e$, intersects $e$ in $v$, and the respective condition for the each of edge $G_B$ has to also hold.

We call the above a run of the protocol. A run works for $(e,f)$ if $e\in G_A$ and $f\in G_B$ when the game ends. A run is secret, if the above $v$ vertex is not the same for every edge. The problem is solvable if they have a (non-deterministic) protocol that has for any $(e,f)$ a secret run that works for it.

To see that there is no protocol for $n=3$, notice that if a run is secret, then we need that both $G_A$ and $G_B$ have at least two edges. This leaves a few cases that are easy to check to see that this is impossible.

$\endgroup$
  • $\begingroup$ This comment is only about more general situation when intersection of two given lists may contain more than 1 element. One can try to reveal information like "only one edge from these three is mine". I think that in this case your reformulation will not be equivalent. $\endgroup$ – Alexey Ustinov Apr 20 '15 at 3:50
  • $\begingroup$ It is equivalent. It also works for bigger list sizes, you just have to replace graph with hypergraph. $\endgroup$ – domotorp Apr 20 '15 at 8:22
  • $\begingroup$ @AlexeyUstinov, since it is known a priori that one has only a single edge, revealing "only one edge from the set E is mine", is equivalent to revealing "for each edge d in the complement of E, d is not mine". $\endgroup$ – Yoav Kallus Apr 20 '15 at 12:51
  • 1
    $\begingroup$ For four suspects, suppose that Alice suspects (1,2) and Bob suspects (1,3). For the run to work, Alice must eliminate (2,3) and (3,4) for Bob, and Bob must eliminate (2,3) and (2,4) for Alice. The problem is they don't know in advance which edges they have to eliminate for the other sheriffs. They know they must eliminate their edge's complement, but if one starts with that deterministically, one tips Eve off to one's suspicion, and the game is lost. Therefore, in any possible protocol that does not start thus, they will each, in the worst case, let slip at least one extra eliminated edge. $\endgroup$ – Yoav Kallus Apr 21 '15 at 1:34
  • 1
    $\begingroup$ @Alexey: Until they say things that they can say for any input, they don't say anything. After the first communication happens that cannot be said for every input, an edge is excluded. $\endgroup$ – domotorp Apr 21 '15 at 18:48
2
$\begingroup$

A couple easy observations.

Let $\delta(N, l, m) = 1$ if the problem can be solved for sheriffs with lists of length $l$ and $m$ out of a total of $N$ suspects, $\delta = 0$ otherwise.

Obviously, $\delta(N,l,m) = 0$ unless $N \geq l + m - 1$ (since the sheriffs can't determine who the culprit is). Also, $\delta(N,l,m) = 0$ if $l=N$ or $m=N$, since then one of the sheriffs has no more knowledge than the eavesdropper.

If we have $\delta(N,l,m) = 1$ and $\delta(N,l,m-1) = 1$ then the the following algorithm shows that $\delta(N+1,l,m) = 1$:

  1. Sheriff 1: "I don't have $x$ on my list", where $x$ is randomly chosen from the suspects not on sheriff 1's list.

  2. If Sheriff 2 doesn't either, then he responds "neither do I" and both proceed as in the case with $N$ suspects and lists of lengths $l,m$.

  3. If Sheriff 2 has $x$ on his list, he responds "$x$ was on my list", removes $x$ from his list, and both proceed as in the case with $N$ suspects and lists of lengths $l,m-1$

This argument is of course symmetric wrt $l,m$.

In the case where $m = 1$ and $N \geq 2l$, the following algorithm works:

  1. Sheriff 1: "Which of the following pairs contain the suspect?" (He then lists $n$ pairs, each of which contains one suspect from his list, and one who isn't).

  2. Sheriff 2: Tells him which pair contains the suspect ($m=1$ so sheriff 2 has this information).

In particular, combining the above facts (and the fact that $\delta(3,2,2)=0$) we have that $\delta(N,2,2) = 1 \implies \delta(N+1,2,2) = 1$, so in this case the problem is in fact solvable for all $N$ above the lower bound.

$\endgroup$
  • $\begingroup$ I think that you should state at the beginning of your answer that you prove that if the problem is solvable for $N$ suspects, then it is also solvable for $N+1$ suspects for ANY fixed list sizes, at least it took me a while to realize that this is your statement. You could also state that to prove this, you use that for bigger lists the problem cannot get easier. $\endgroup$ – domotorp Apr 21 '15 at 6:33
  • $\begingroup$ That isn't my statement, it's the statement I'd like to make - I only proved it for l=m=2. Not sure what you mean by "easier" $\endgroup$ – Sam Clearman Apr 21 '15 at 15:12
  • $\begingroup$ Sorry, I was wrong. For the easier part, I thought that $\delta(N,l,m)=1$ implies $\delta(N-1,l,m-1)=1$, because for an instance of the latter we can add a new suspect that is only in the second list to obtain a special case of the first instance. But this might fail because the mob also has more info. $\endgroup$ – domotorp Apr 21 '15 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.