Emergency! Lynch Mob coming. Can you help?

[bonanova]

There was a killing last night at the *gasp* Double-R-Bar Ranch out between Dry Gulch and Tombstone. Each town's sheriff has investigated a list that contains the eight men who are the only possible suspects. And kudos to them both, because already each sheriff has a short list of just two suspects. They intend to compare their lists via telephone call and, if they agree on exactly one person, an arrest will be made.

Unfortunately some of the town-folk know the names of the original eight suspects, and they instead intend to lynch the culprit, if they can identify him. Wait, there's more. They have tapped the sheriffs' telephone. If, by listening to the sheriffs' conversation, the mob can identify the culprit with certainty, the bad guy will be lynched before he can be arrested.

How can the sheriffs, who have never met*, discuss their findings, opaquely to the eavesdropping lynchers but with clarity to each other, so that the mob is left in the dark, while both sheriffs end up knowing the culprit -- and thus allow either sheriff to make the arrest?

*Specifically, they have no commonly-held information to use as an encryption key.

(If something is not clear, please ask.)

[Molly Mae]

From what I know of Diffie-Hellman, this shouldn't be too difficult!

Can I use the Diffie-Hellman key exchange as an answer?  Or are we trying to come up with a way that doesn't involve common key agreement algorithms?

[bonanova]

@Molly Mae Consider that the sheriffs are simply talking to each other, using statements like, "my pair of suspects has this property: (describes property.)" Would generating and using common key agreements be doable with such low-complexity statements?

[Molly Mae]

9 hours ago, bonanova said:

@Molly Mae Consider that the sheriffs are simply talking to each other, using statements like, "my pair of suspects has this property: (describes property.)" Would generating and using common key agreements be doable with such low-complexity statements?

If the list of suspects can be ordered publicly, they could use a key exchange to come up with a secret and use that to identify a particular number using a public modulus.  I'll type up a demonstration when I get a moment.

[Molly Mae]

All right, here we go:

1. Let the sheriffs publicly order the list from 1-8
2. They publish two prime numbers, p₁ and p₂.
3. Each sheriff chooses a secret number, a and b.
4. The first sheriff calculates p₁^a mod p₂ and sends the result publicly to the second sheriff.  We'll call this result A.
5. The second sheriff calculates p₁^b mod p₂ and sends this result to the first sheriff.  We'll call this result B.
6. The first sheriff can take B^a and the second sheriff can take A^b to arrive at the same secret result, even though the first sheriff never knows b and the second sheriff never knows a (and the public never knows either).

We can then use any public arithmetic to arrive at a result without giving away our secret number, and hence our accusation.

This is the basis for any kind of secure internet connection that doesn't involve a pre-shared key or well-known trusted certificate.

 

An alternative:

The sheriffs can take turns eliminating non-suspects from the list or passing.  They can easily get down to a list of 2.  If, at any time, one sheriffs list has been eliminated, he can announce it.  The sheriffs don't agree.  If they ever reach a list of 3 where both sheriffs have both of their suspects, the sheriff will pass.  They must agree on at least one suspect.  The sheriffs can restart as many times as they like, without ever publicly revealing who is actually on their list.

I'm trying to determine how many times they could do that before the public can deduce the identities of the suspects.

It kind of turns into reverse Mastermind.

My second method actually doesn't work.  It lets the sheriffs know that they share a suspect (or don't), but doesn't tell them who the shared suspect is.

[plasmid]

Would that be equivalent to the following?

Spoiler

I’ll be the first sheriff to speak. I’ll tell the other sheriff to write down the eight suspects’ names in a circle in the order that I specify, going clockwise with 45 degrees between each name. Unbenknownst to the other sheriff or the eavesdroppers, I’ll arrange the names in the list such that my two suspects are at opposite ends of a diameter of the circle. I’ll ask the other sheriff to name who’s halfway between his two suspects on the list along the shortest arc that joins them (and if his suspects are say #1 and #4 then he should say the midpoint is between names #2 and #3). I’ll know that the midpoint that he specifies – between the guilty party and an innocent that’s less than 180 degrees away – is closer to the guilty than to my innocent suspect so I’ll know who the guilty suspect is. Then I can tell the other sheriff whether to go clockwise or counterclockwise from his midpoint to find the guilty suspect. The eavesdroppers shouldn’t be able to tell who’s guilty with that approach.

 

[Molly Mae]

16 minutes ago, plasmid said:

Would that be equivalent to the following?

  Hide contents

I’ll be the first sheriff to speak. I’ll tell the other sheriff to write down the eight suspects’ names in a circle in the order that I specify, going clockwise with 45 degrees between each name. Unbenknownst to the other sheriff or the eavesdroppers, I’ll arrange the names in the list such that my two suspects are at opposite ends of a diameter of the circle. I’ll ask the other sheriff to name who’s halfway between his two suspects on the list along the shortest arc that joins them (and if his suspects are say #1 and #4 then he should say the midpoint is between names #2 and #3). I’ll know that the midpoint that he specifies – between the guilty party and an innocent that’s less than 180 degrees away – is closer to the guilty than to my innocent suspect so I’ll know who the guilty suspect is. Then I can tell the other sheriff whether to go clockwise or counterclockwise from his midpoint to find the guilty suspect. The eavesdroppers shouldn’t be able to tell who’s guilty with that approach.

 

Does that allow the other sheriff to make the arrest, though?  That was the stumbling block I was having with my second approach.

[plasmid]

6 minutes ago, Molly Mae said:

Does that allow the other sheriff to make the arrest, though?  That was the stumbling block I was having with my second approach.

Yep, in the next-to-last sentence you give him an instruction that lets him know which of his two suspects are guilty without letting the eavesdroppers know.