Existence of zero-knowledge proof for location

Question

N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance error of E.

Player 1 has J locations where $$J < N$$

Player 2 has K locations where $$K < N$$

And for this problem we assume $$(J + K) > N$$

Players 1 and 2 agree to pool their locations to win the prize, but not before they each determine that they have the location of all N items. i.e. $$ J \bigcup K = N $$

Each player wants proof that the other player has some number of locations which they themselves do not have.

Is it possible for a player to prove to the other that they have a location that the other player does not have without disclosing that location?

---

I call my best guess the triangle game (or sub-game if your prefer) Here is one round of Player 1 trying to prove a location to player 2.

1. Player 1 picks a point on the map x1,y1
2. Player 2 picks a point on the map x2,y2 and a condition 'player 1's point will be in the triangle formed by x1,y1 x2,y2 and x3,y3'
3. Player 1 picks a point on the map x3,y3 for which at least one his points falls inside the triangle

The condition in step 2 may also be 'player 1's point will not be in the triangle formed by x1,y1 x2,y2 and x3,y3'.

Player 2 will try to pick a point and a condition such that he can confirm that Player 1's point is not one of his K points.

The players may have to play this triangle game many rounds in order to verify a point.

This problem is based on the DARPA Network Challenge

N items=10 red balloons
map=the continental United States
prize=$40,000 
distance error of E < 1.0 mile

Answer 1

I think part of the problem you are having finding a solution is that you are using the wrong name for this concept. While it is indeed closely related to the idea of a zero knowledge proof, this type of protocol, accepting input from multiple parties, is known as either Secure Function Evaluation or Secure Multi-Party Computation.

Let's first simplify the game and assume it is played on a lattice, so that the points are discrete. It seems to me that you simply wish to compute $|J \cup K|$. Trivially, this is equal to $|J \cup K| = |J| + |K| - |J \cap K|$. Now, I assume you do not mind each party learning the number of locations the other party holds. In this case, $|J|$ and $|K|$ are public. In this case all that is required to determine $|J \cup K|$ is $|J \cap K|$. Now, if we think of the inputs of Player 1 (henceforth Alice) and Player 2 (henceforth Bob) as being a vector of length equal to the total number of locations possible, with zeros everywhere except for the location that player holds (which is set to 1). In this case $|J \cap K|$ is simply the inner product of their two vectors. Fortunately there are SFE protocols for exactly this inner product computation (see here for example). So Alice and Bob simply calculate $|J \cup K|$.

Now, what about the case you give, where the locations are not discrete, but are rather parameterised by a pair of real numbers which have some range associated with them? In this case it is not sufficient to determine whether two points exactly coincide, but we need to also determine which points are close enough to one another to overlap in the area covered. This can be done fairly easily: The first step is to discretize the set of possible locations, hence imposing some fixed resolution on the problem (in practice you only need the range covered by each location to extend a few pixels in each direction). Once you have done this, the protocol would proceed as follows: Bob prepares a register equal in size to the total number of possible discretized locations. Everywhere is zero, unless that location is within distance $D=2E$ of one of his locations in which case it is set to 1. Alice prepares her vector as before, with a 1 at only her discretized locations. Then Alice and Bob run the secure dot product protocol. The number returned by this is simply the number of locations held by Alice such that the area covered by that point overlaps with the area covered by some location held by Bob. (Adjusting the $D$ parameter can be done to set some minimum overlap if desired). In this way, Alice and Bob can count the number of points where the overlap exceeds some threshold, and the total number of distinct locations they would hold between them.