3
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ They are oponents, so revealig your position is disadvantageous. $\endgroup$ – Beacon of Wierd Oct 25 '18 at 0:34
  • $\begingroup$ Can you explain your existing solution by homomorphic cryptography? I would encourage you to write it down as an answer, either as a record of existing knowledge or, possibly, as the best solution to stand the test of time. It will certainly help and motivate more people to answer your question. For example, it might be possible to improve upon your solution. $\endgroup$ – Apass.Jack Oct 26 '18 at 13:03
  • $\begingroup$ crypto.stackexchange.com might be a better place to ask this question, although I believe this question is certainly not off-topic here. Please note that cross-posting is usually frowned upon. You can just let the question stay here for a while. Then, if no good answers come up, head towards the other site. $\endgroup$ – Apass.Jack Oct 26 '18 at 13:11
  • $\begingroup$ @Apass.Jack Hi, I don't know if you got a notification when I updated the answer, but I've found a solution now and posted it here if you are interested :) $\endgroup$ – Beacon of Wierd Apr 9 at 23:19
  • 1
    $\begingroup$ I suggest reading about secure multiparty computation, which is an entire field covering problems of this sort. You are looking for a SML protocol for computing a particular function (the distance function). There are generic results showing how to build such a protocol for any function of your choice, which you could apply directly. There might also be ways to get algorithms specific to your situation that are faster than the generic ones. If you asked on Crypto.SE you'd probably get good answers. $\endgroup$ – D.W. Apr 10 at 0:40
3
$\begingroup$

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 < 0 \end{equation} However, since the distance you want to check will in many cases be very similar for both players, your opponent can make good guesses as to what $d$ is, which means your opponent has access to a boundary on your position (one equation, two unknowns in a 2D environment). Thus we need to add a slight modification to avoid this, and ultimately evaluate the following equation: \begin{equation} r(x_a -x_b)^2 + r(y_a - y_b)^2 - rd < 0 \end{equation} The multiplication of $r$ here does not change the truth value of the expression, but it does add one unknown, thus the only constraint we can get is that the unknown point is on a plane, which does not add any new information.

In order to use the additive homographic property of our encryption we need to fully expand this equation: \begin{equation} rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd < 0 \end{equation} Let us assume that we are player b. We have access to $x_b$ and $y_b$ and we are going to be choosing $r$ and $d$. From the equation above it's then obvious that player b needs information about $x_a$, $y_a$, $x_a^2$ and $y_a^2$, thus player a will now encrypt those values and send them to player b, together with the public key to for the encryption.

Here comes my breakthrough, player b is only able to do addition with the encrypted values we received from player a, thus the terms $rx_a^2$,$ry_a^2$,$-2rx_a x_b$,$-2rx_a x_b$ are impossible for player b to compute. However, if we restrict r to be integers player b can compute $rx_a^2$ and $ry_a^2$ by simply adding $x_a^2$ and $y_a^2$ to themselves $r$ times. In practice this would be multiplying the encrypted values $r$ times (assuming we use Paillier encryption).

This only leaves $-2rx_a x_b$ and $-2rx_a x_b$, which we can solve by letting player a do the actual multiplication. If player b sends: \begin{equation} -2rx_b \end{equation} \begin{equation} -2ry_b \end{equation} Player a can preform the multiplication. However, we run into the same problem in the beginning, now player a can put a constraint on the position, since we are sending two equations and three unknowns, thus we need to modify what we send to keep our information hidden. Thus player b instead sends: \begin{equation} -2rx_b + C_1 \end{equation} \begin{equation} -2ry_b + C_2 \end{equation} Where $C_1$ and $C_2$ are integers. Since they are integers, and we know they are going to be multiplied by $x_a$ and $y_a$ we can do the same trick as before and account for this in our addition of the encrypted values.

Thus the last thing to work out is what to encrypt and send back, which is rather easy. We simply have to account for the added $C_1$ and $C_2$ and subtract them. Thus player b sends: \begin{equation} \mathcal{E} (rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2) \end{equation} Where $\mathcal{E}$ stands for "encrypted". There's a note to be made here about speeding up the computation of $\mathcal{E} (rx_a^2)$ which using a naive approach would require us to do $2r + C_1 + C_2$ encryption computations, however this can be sped up considerably by simply adding the newly encrypted sum to itself, thus making the process exponential and reducing the computations down to somewhere above $ log_2 (r) + log_2(max(C_1,C_2))$, but this is only important for the implementation. Later I will represent this type of multiplication with $\times$.

Let's now look at all the transactions which take place:

  • Player b sends a request to Player a (this step can be skipped if the transactions are continuous)

  • 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.

$\endgroup$
  • $\begingroup$ Clever! It looks like this might be secure if you trust both parties to encrypt their values correctly. However, if party a is malicious, then they can learn partial information about $b$'s information: e.g., party a can choose $x_a=y_a=0$ and learn partial information about $x_b^2+y_b^2-d$ some of the time (they observe $rx_b^2+ry_b^2-rd$; if this is odd, they can conclude that $x_b^2+y_b^2-d$ is odd too). Thus this protocol might be secure in the so-called semi-honest (passive) threat model but it doesn't seem like it will be secure in the malicious (active) threat model. $\endgroup$ – D.W. Apr 10 at 0:50
  • $\begingroup$ @D.W. Yes, there are several "dishonesty" loop holes, however those can be checked after the fact, since both players can keep a log of all transactions and require the opponent to send the private encryption keys by the end of a session, thus ensuring that no no malicious behaviour has been conducted. $\endgroup$ – Beacon of Wierd Apr 10 at 7:03
  • $\begingroup$ @D.W. Correct me if I am wrong, finding out if $x_b^2 + y_b^2 - d$ is odd or not only works if x_b and y_b are integers, right? Which would be extremely rare and can even be made to never happen. $\endgroup$ – Beacon of Wierd Apr 10 at 7:31
  • $\begingroup$ Paillier's scheme requires everything to be integers, so if they're not integers, you can't use this scheme. $\endgroup$ – D.W. Apr 10 at 17:49
  • $\begingroup$ @D.W. Oh, I see. I guess I'll have to keep $r$ even then :) Do you know of any additive homographic encryption which can handle decimal numbers? $\endgroup$ – Beacon of Wierd Apr 10 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.