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.
