In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their coordinates to each other?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
While this may be of interest as an academic exercise, they can't securely compute it without revealing their coordinates (or at the very least leaking a lot of information about their coordinates).
Consider that partyB gives a secure service to partyA whereby partyA can calculate the arctan without exposing its coordinate. Let's say this result is $v$. Then clearly $y_2 = y_1 + (x_2 - x_1)\tan v$, which is already leaking a very large amount of information about $(x_2,y_2)$. Indeed, if partyA can make an additional query to that service, passing in some other coordinate, then partyA has sufficient data to calculate the coordinate precisely.
-
$\begingroup$ When we have the problem 'securely compute $F(a, b)$ without leakage, we assume that the information that the two sides get from the value $F(a, b)$ is not counted as part of the unwanted leakage. You could claim that this isn't a useful problem (because, as you point out, two queries will reveal everything), but we don't know enough about the ultimate problem to state that $\endgroup$– ponchoCommented Aug 13, 2018 at 19:06
-
$\begingroup$ That's a valid point, but I still feel it's relevant to point out to whomever is asking the question the insecurity of the problem as a standalone piece. $\endgroup$– MotiNKCommented Aug 14, 2018 at 8:54
-
$\begingroup$ In an FHE setting, they could both encrypt and compute on encrypted ciphertexts that can only be decrypted by a 3rd party $\endgroup$ Commented Aug 14, 2018 at 12:27
-
$\begingroup$ @FlorianBourse, or the parties can have a special key generation algorithm which outputs a global public key $(pk)$ which the parties use to encrypt stuff and to a distributed decryption using shared secret keys $(sk_A, sk_B)$ whenever they want to decrypt the ciphertext. $\endgroup$– DragosCommented Aug 14, 2018 at 15:18
$\begingroup$
$\endgroup$
Have a look in the SCALE-MAMBA documentation at 11.10.3 section where it explains how one implements $\mathsf{ArcTan}([x])$ where x is a shared fixed point value.
Regarding your case specifically, first the parties have to share their inputs. Party A selects randomly $r_{Bx_1}, r_{By_1}$ and sends them to the other player. Party A will keep the $r_{Ax_1},r_{Ay_1}$ such that
- $r_{Ax_1} + r_{Bx_1} = x_1$ and
- $r_{Ay_1} + r_{By_1} = y_1$.
Now party B does the same with it's own coordinates and shares its coordinates $(x_2, y_2)$ to Party A. Thus the inputs are now secret shared among the parties: $[x_1], [y_1], [x_2], [y_2]$. I guess the input processing phase with SHE can be done by having one party, say Party A, encrypt their inputs: $\mathsf{Enc}(x_1), \mathsf{Enc}(y_1)$ and send them to Party B. Then same technique applies to both MPC and SHE worlds.
Next step consists in the parties computing the shared division $[x] = [y_1 - y_2]\textit{ }/\textit{ }[x_1 - x_2]$ using either fixed or floating point arithmetic in MPC. Then you can plug in the Arctan algorithm from the SCALE-MAMBA doc to compute $[\mathsf{Arctan}(x)]$ from $[x]$.
To give you an intuition on what is happening under the hoods of $\mathsf{Arctan}(x)$ you need to see that the equation can be re-written as: $\mathsf{Arctan}(x) = \frac{\pi}{2} - \mathsf{Arctan}(\frac{1}{x})$.
Since the inputs are now mapped into $\frac{1}{x} \in [-1,1]$ we can evaluate some funky polynomials $P(\frac{1}{x}), Q(\frac{1}{x})$ to approximate the value of $\mathsf{Arctan}(x)$ which is called Padé approximant. The concrete coefficients of $P,Q$ are resurrected from an old book by Hart78 in the SCALE-MAMBA documentation.
