The Felix problem

Say you have a multiplayer game where there is no central server. You need to indicate to a pair of players if they are within a certain distance from each other, but you can’t let any of the players know the actual positions of any other players. Could you do it?

I was driving us back from the 2014 Biological Data Science meeting at Cold Spring Harbor when Felix posed this problem to me. The drive was alternatingly boring and annoying as we hit pockets of over polite New York drivers on the way out (Though there was a stretch of road along the Hutchinson River Parkway that was SPECTACULAR in terms of fall foliage. We didn’t take any pictures, but that alone made driving to and from the conference worth it)

As a complete aside, Felix had the GPS voice on his phone on and we were entertained by numerous howlers, one them being the voice calling it the “Hutchinson River Peek-wee” (pkwy) and the other being: “Take I95 New Hampshire minus Maine” which Felix declared would simply be New Hampshire, since there is no intersection between the two sets.

Anyhow, back on point, to relieve the boredom Felix was telling me crypto related things and came up with this question, which he claimed he did not have a definitive answer to.

Here are my attempts during the drive:

Players A, B want their distance checked. Players C, D are “third-parties”

Scheme 1 (Fails)

Player A sends their position along with N-1 random positions to C. Each position has a tag. Only A knows the correct position by tag. Player B does the same

Screen Shot 2014-11-08 at 11.10.02 PM

Player C computes N^2 position combinations and returns the results to both A and B.

Screen Shot 2014-11-08 at 11.10.11 PM

My idea was that when they get the results back A and B will be able to pick the correct results, because they’ll know which is their tag, but, at this point, I realized the scheme will fail, because each will get back N results with their tag in it, but not know which was the original one.

But, this led me to the second scheme which works:

Scheme 2

Player A and B send their position, along with N-1 random positions, tagged, to C. They also separately they send their tags to D.

Screen Shot 2014-11-08 at 11.13.42 PM

C sends the N^2 computation results to D who then matches the correct answer based on the tag pair from A and B and then sends the result back to A and B

Screen Shot 2014-11-08 at 11.14.03 PM

Scheme 3 – nice refinement of 2

I then realized that you can save on the large number of computations (N^2 even if they are simple) by doing the following: A adds a random number to their position (p_a + q_a) and sends this to C. B sends a similarly randomly offset number to C (p_b + q_b). Both A and B send the random offsets to D.

Screen Shot 2014-11-08 at 11.17.52 PM

C computes r_1 = (p_a + q_a) - (p_b + q_b) and sends it to D.

Screen Shot 2014-11-08 at 11.17.59 PM

D then subtracts the difference of the offsets from the result from C r_2 = r_1 - (q_a - q_b), which is r_2 = (p_a + q_a) - (p_b + q_b) - (q_a - q_b) i.e. r_2 = p_a - p_b.

Screen Shot 2014-11-08 at 11.18.06 PM

This last is the computation we want and D broadcasts the flag “In range” or “Out of range”. Note that neither C nor D know the actual positions of A and B, and A and B don’t know each others’ positions either.

I was pretty happy at arriving at this solution and by this time we had meandered our way out of New Rochelle.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s