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, 2020 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, 2020 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, 2020 at 16:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.