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.)