3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – poncho Aug 13 '18 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$ – MotiN Aug 14 '18 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$ – Florian Bourse Aug 14 '18 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$ – Dragos Aug 14 '18 at 15:18
1
$\begingroup$

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.

$\endgroup$

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.