<p>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 <a href="http://en.wikipedia.org/wiki/Secure_multi-party_computation">Secure Multi-Party Computation</a>.</p>

<p>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 <a href="http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/4035458/4035896/04036100.pdf?arnumber=4036100&amp;authDecision=-203">here</a> for example). So Alice and Bob simply calculate $|J \cup K|$.</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-01T16:12:17.830Z
Thank you! Your answer is clear, consise, and satisfying. I appreciate the effort you put into your answer.
this.josh
CC BY-SA 3.0
2011-05-01T19:58:54.353Z
@this.josh: No problem. Hope it helps.
Joe Fitzsimons
CC BY-SA 3.0
2011-05-01T12:41:26.430Z
2011-05-01T12:49:53.250Z
2011-05-01T12:49:53.250Z
Joe Fitzsimons
<p>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.</p>

<p>Player 1 has J locations where $$J &lt; N$$</p>

<p>Player 2 has K locations where $$K &lt; N$$</p>

<p>And for this problem we assume $$(J + K) &gt; N$$</p>

<p>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 $$</p>

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

<p>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?</p>

<hr>

<p>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.</p>

<ol>
<li>Player 1 picks a point on the map x1,y1 </li>
<li>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' </li>
<li>Player 1 picks a point on the map x3,y3 for which at least one his points falls inside the triangle</li>
</ol>

<p>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'.</p>

<p>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.</p>

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

<p>This problem is based on the <a href="https://networkchallenge.darpa.mil/Default.aspx" rel="nofollow">DARPA Network Challenge</a></p>

<pre><code>N items=10 red balloons
map=the continental United States
prize=$40,000 
distance error of E &lt; 1.0 mile
</code></pre>

CC BY-SA 3.0
2011-04-30T07:47:59.833Z
I am not too familiar with zero-knowledge, but I am not sure how the triangle game is zero knowledge. For instance: player 1 picks $x_1,y_1$ and then player 2 picks $x_2,y_2 = x_1,y_1$ or really close if exact is not allowed (and conditions of "point on triangle"). Doesn't this reveal a lot of info about Player 1's point?
Artem Kaznatcheev
CC BY-SA 3.0
2011-04-30T10:35:35.273Z
Why the players do not settle for [oblivious transfer](http://en.wikipedia.org/wiki/Oblivious_transfer)?
Sadeq Dousti
CC BY-SA 3.0
2011-04-30T11:20:15.103Z
Perhaps this can help http://cs.adelaide.edu.au/~yingpeng/Privacy%20Preserving%20Set%20Intersection%20Protocol%20Secure%20Against%20Malicious%20Behaviors.pdf (see also references at the bottom or other papers that cite it). You can also "Google around" using keywords: Zero knowledge set intersection
Marzio De Biasi
CC BY-SA 3.0
2011-04-30T21:37:20.463Z
There is something wrong with the definitions; are $J$ and $K$ integers or sets?
Jukka Suomela
CC BY-SA 3.0
2011-05-01T04:34:09.713Z
Artem Kaznatcheev: The point is anywhere inside the the triangle. Sadeq Dousti: because each point has value, if player 1 give a point to player 2 and then player 2 leaves, he has received something with nothing in return.  Vor: thank you Jukka Suomela: I think integers would be the better description, because I think using the error limit you can divide the map up into blocks of equal size.
this.josh
CC BY-SA 3.0
2011-05-01T06:04:06.787Z
@this.josh: That's the problem OT seeks to solve! Take a look at the [original paper](https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=1NNsAGWFaxNp2O2h3-AAqP2uMfPXdliUJ2BIsdXScbK3ZYx7GJMXvE1hS7uKI&hl=en) to see what I mean. Moreover, as Jukka says, if they are integers, their union is meaningless. If they are sets, their sum is meaningless. This is easy to correct though!
Sadeq Dousti
CC BY-SA 3.0
2011-05-01T06:21:47.013Z
@Sadeq Dousti: Does OT still work if the players do not have the same number of points? i.e. Player 1 has 7 unique points and Player 2 has 3 unique points. Does OT require them to both have the same number of secrets to exchange?
this.josh
<cr.crypto-security><communication-complexity><it.information-theory><zero-knowledge>
Existence of zero-knowledge proof for location
this.josh
# Existence of zero-knowledge proof for location

(Asked by: username_0 on 2011-04-30)

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.

Player 1 picks a point on the map x1,y1 
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' 
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

**Tags:** cr.crypto-security, communication-complexity, it.information-theory, zero-knowledge

> **Comments:**
> **username_1**: I am not too familiar with zero-knowledge, but I am not sure how the triangle game is zero knowledge. For instance: player 1 picks $x_1,y_1$ and then player 2 picks $x_2,y_2 = x_1,y_1$ or really close if exact is not allowed (and conditions of "point on triangle"). Doesn't this reveal a lot of info about Player 1's point?  
> **username_2**: Why the players do not settle for [oblivious transfer](http://en.wikipedia.org/wiki/Oblivious_transfer)?  
> **username_3**: Perhaps this can help http://cs.adelaide.edu.au/~yingpeng/Privacy%20Preserving%20Set%20Intersection%20Protocol%20Secure%20Against%20Malicious%20Behaviors.pdf (see also references at the bottom or other papers that cite it). You can also "Google around" using keywords: Zero knowledge set intersection  
> **username_4**: There is something wrong with the definitions; are $J$ and $K$ integers or sets?  
> **username_0**: username_1: The point is anywhere inside the the triangle. username_2: because each point has value, if player 1 give a point to player 2 and then player 2 leaves, he has received something with nothing in return.  Vor: thank you username_4: I think integers would be the better description, because I think using the error limit you can divide the map up into blocks of equal size.  
> **username_2**: @username_0: That's the problem OT seeks to solve! Take a look at the [original paper](https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=1NNsAGWFaxNp2O2h3-AAqP2uMfPXdliUJ2BIsdXScbK3ZYx7GJMXvE1hS7uKI&hl=en) to see what I mean. Moreover, as Jukka says, if they are integers, their union is meaningless. If they are sets, their sum is meaningless. This is easy to correct though!  
> **username_0**: @username_2: Does OT still work if the players do not have the same number of points? i.e. Player 1 has 7 unique points and Player 2 has 3 unique points. Does OT require them to both have the same number of secrets to exchange?  

---

## 1 answers

### Answer by username_5 on 2011-05-01. Score: 10 | Accepted answer

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](http://en.wikipedia.org/wiki/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](http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/4035458/4035896/04036100.pdf?arnumber=4036100&authDecision=-203) 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.

> **Comments:**
> **username_0**: Thank you! Your answer is clear, consise, and satisfying. I appreciate the effort you put into your answer.  
> **username_5**: @username_0: No problem. Hope it helps.  

---

