patternMinor
Anonymous Visibility Check in P2P networks
Viewed 0 times
anonymousnetworksvisibilitycheckp2p
Problem
I'm working on a problem for a P2P network for games. The problem is the following:
Consider two opponents on a grid, each stores it's own position.
Player 1 wants to know if it sees player 2. In other words, if player 2 should send it's positional data to player 1 without revealing it’s position in the process.
The problem is sort of obvious, in order to know if player 2 should send it's data it needs the position of player 1, thus player 1 has to reveal it's position. I'm wondering if anyone knows about a system which does this visibility check anonymously, without revealing the position of players.
Right now I have an algorithm/policy which only reveals if player 1 is above, below, to the left or to the right of player 2 but does not reveal the exact coordinates of player 1 to player 2. It's based on the homomorphic properties of certain cyphers, but this is still a big limitations in certain games, especially first person shooters where knowing the approximate direction of your enemy can be very helpful? Note, I am NOT looking for fully homomorphic cryptography here, only something which can solve this specific problem of checking whether a point is inside of a "visibility field" or not without revealing positional (or visibility field) information.
This question might be a stretch since there probably isn't such an algorithm out there, but I thought I'd ask anyway :)
Consider two opponents on a grid, each stores it's own position.
Player 1 wants to know if it sees player 2. In other words, if player 2 should send it's positional data to player 1 without revealing it’s position in the process.
The problem is sort of obvious, in order to know if player 2 should send it's data it needs the position of player 1, thus player 1 has to reveal it's position. I'm wondering if anyone knows about a system which does this visibility check anonymously, without revealing the position of players.
Right now I have an algorithm/policy which only reveals if player 1 is above, below, to the left or to the right of player 2 but does not reveal the exact coordinates of player 1 to player 2. It's based on the homomorphic properties of certain cyphers, but this is still a big limitations in certain games, especially first person shooters where knowing the approximate direction of your enemy can be very helpful? Note, I am NOT looking for fully homomorphic cryptography here, only something which can solve this specific problem of checking whether a point is inside of a "visibility field" or not without revealing positional (or visibility field) information.
This question might be a stretch since there probably isn't such an algorithm out there, but I thought I'd ask anyway :)
Solution
Ok, so after realizing my previous solution didn't work I've put this problem on ice for a while, but now I have one in which I am fairly confident. If you find any obvious flaws, please let me know. This is the first time I'm answering a question, and I'm trying to be as transparent as possible where all my ideas came from so that anyone can find errors easier. Thus my answer will be quite long.
To start with, I've limited it to determining if the distance between two players (two points) is bellow a certain therhold. It can however be extended to a vision field.
My current solution relies on a homographic encryption which can do addition (such as Paillier).
To start with I note the expression which I ultimately want to evaluate, which is the distance between two points being within a certain distance:
\begin{equation}
(x_a -x_b)^2 + (y_a - y_b)^2 - d
-
Player a sends $\mathcal{E}(x_a)$, $\mathcal{E}(y_a)$, $\mathcal{E}(x_a^2)$, $\mathcal{E}(y_a^2)$ and $\mathcal{E}$.
-
Player b sends:
-
Player a then:
\begin{equation}
[rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2] + x_a[-2r x_b + C_1] + y_a[-2r y_b + C_2]
\end{equation}
which Equates to:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd
\end{equation}
I hope this answer was clear, or at least understandable. When I used the [ ] brackets it was only to notate what came as one number, so from the perspective of player a, everything inside of a bracket is just one number.
A thing to note here is that it's player a can still cheat by just refusing to send the position ( and Player b could for example send vision checks where he shouldn't), but this sort of cheating can be caught by keeping a log of all player positions (and vision checks) throughout the game (or a subset of them to save memory) which when the game is over, or enough time has passed, can be used to verify that neither player was cheating. If a player disconnects suddenly they can just be asked to send their log when they go online again, thus sudden disconnects is not a problem either.
To start with, I've limited it to determining if the distance between two players (two points) is bellow a certain therhold. It can however be extended to a vision field.
My current solution relies on a homographic encryption which can do addition (such as Paillier).
To start with I note the expression which I ultimately want to evaluate, which is the distance between two points being within a certain distance:
\begin{equation}
(x_a -x_b)^2 + (y_a - y_b)^2 - d
-
Player a sends $\mathcal{E}(x_a)$, $\mathcal{E}(y_a)$, $\mathcal{E}(x_a^2)$, $\mathcal{E}(y_a^2)$ and $\mathcal{E}$.
-
Player b sends:
- $r \times (\mathcal{E}(x_a^2) \mathcal{E}(y_a^2))\mathcal{E}(rx_b^2) \mathcal{E}(ry_b^2)\mathcal{E}(-rd) C_1 \times \mathcal{E}(-x_a) C_2 \times \mathcal{E}(-y_a)$
- $-2rx_b + C_1$
- $-2ry_b + C_2$
-
Player a then:
- Decrypts the encrypted part to get $[rx_a^2 +x_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2]$
- Multiplies $-2rx_b + C_1$ and $-2ry_b + C_2$ with $x_a$ and $y_a$ respectively.
- Adds this all together to get:
\begin{equation}
[rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2] + x_a[-2r x_b + C_1] + y_a[-2r y_b + C_2]
\end{equation}
which Equates to:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd
\end{equation}
- Player a checks if this value is smaller than 0, if so player a sends it's position to player b, if not it sends a "false" message.
I hope this answer was clear, or at least understandable. When I used the [ ] brackets it was only to notate what came as one number, so from the perspective of player a, everything inside of a bracket is just one number.
A thing to note here is that it's player a can still cheat by just refusing to send the position ( and Player b could for example send vision checks where he shouldn't), but this sort of cheating can be caught by keeping a log of all player positions (and vision checks) throughout the game (or a subset of them to save memory) which when the game is over, or enough time has passed, can be used to verify that neither player was cheating. If a player disconnects suddenly they can just be asked to send their log when they go online again, thus sudden disconnects is not a problem either.
Context
StackExchange Computer Science Q#99001, answer score: 3
Revisions (0)
No revisions yet.