This question follows-up from this question/comment.

Suppose, you are given $X \odot Y$, where $X~(\neq 0) \in \operatorname{GF}(2^{128})$ is random, $Y~(\neq 0) \in \operatorname{GF}(2^{128})$ is random, and $\odot$ is a multiplication over $\operatorname{GF}(2^{128}$) with some modulus. As explained in this answer, the product $X \odot Y$ preserves privacy about its factors.

Therefore, assume you are given some extra information (see below). Will it be possible to recover (at least some non-trivial information) $X$, $Y$ under each of the scenarios:

  1. $X \oplus Y$ is given. Since $\oplus$ can be stated as the addition operation over any $\operatorname{GF}(\cdot)$, we can also say the sum of $X$ and $Y$ over $\operatorname{GF}(2^{128})$ is given.
  2. Arithmetic sum $X + Y$ is given.
  3. Modular addition, $X+Y \pmod{2^{128}}$ is given. Or, may be with any other divider (except $2$ as this coincides with $\oplus$), say $2^{8}$ or $2^{16}$, instead of $2^{128}$.

I considered each of the above scenarios to be exclusive. Please feel free to combine the scenarios or propose a new scenario if that is useful.

  • 2
    $\begingroup$ For 1: if $X$ or $Y$ is zero, $X\oplus Y$ recovers the other variable. Otherwise, substitute one equation into the other and solve a quadratic equation over the field (it's a bit different from the reals but there are methods, which I don't remember). $\endgroup$
    – Fractalice
    Oct 7 '20 at 16:26
  • 1
    $\begingroup$ For 2 or 3 I guess something can be done by introducing variable for the carries and solving quadratic equations over $GF(2)$, which is generally hard but here the system has very simple structure. $\endgroup$
    – Fractalice
    Oct 7 '20 at 16:30
  • 2
    $\begingroup$ I would also add that, mathematically speaking, this is not well-defined as there are no "good" maps between $GF(2^{128})$ and $\mathbb{Z}$ or $\mathbb{Z}_{2^{128}}$. (good meaning behaving well with respect to any usual operations, i.e. being homomorphisms). $\endgroup$
    – Fractalice
    Oct 7 '20 at 16:31

Your Answer

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

Browse other questions tagged or ask your own question.