how to solve equation with XOR, modulo addition and multiplication

Question

I have an equation with two variables

$y=(Ax' + x) \oplus (Bx'+x)$,

where $x$ and $x'$ are two $n$-bit ($n\in \mathbf{N^+}$) unknown variables, $A$, $B$ and $y$ are known to me ($Ax'$ is the normal multiplication, $+$ is carried with respect to $\bmod 2^n$, and $\oplus$ is bit-wise XOR).

In more detail, the model I consider here can be treated as a black box. $x'$ and $x$ are two number initialized and fixed by other people, I can only access the inputs, $A$ and $B$, of this black box, and collect the corresponding outputs $y$. Then I want to determine $x$ and $x'$ by some pairs of query $(A, B)$ and the corresponding outputs $y$.

This problem is closely related to the one: How to solve this equation for $x$ with XOR involved?, which tries to get the unknown $x'$ of the equation $y=(Ax'+C)\oplus (Bx'+D)$. The answer of this problem is: $x'$ can be determined if $A\oplus B=(11\cdots111)_2$ (here $()_2$ denotes binary representation).

Then I try to go through the similar steps as given by @Martin Kochanski, but I find the extra variable $x$ do introduce some other problems and make the previous solution not valid anymore.

Then I think may be I need multiple copies of $A$, $B$ and $y$. Then I tried with the case $n=8$ and exhaustively searched all the combinations of $(A, B, y)$ that lead to unique solution of $(x, x')$, and such case do exists. For example, I found that input queries $(2^0,2^1)$,$(2^1,2^2)$,$(2^2,2^3)$,$(2^3,2^4)$,$(2^4,2^5)$, $(2^5,2^6)$ and $(2^6,2^7)$ and all the corresponding outputs $y$ actually determines the value of $x'$ and $x$.

So is there any analytical method to solve this (system of) equation(s)? Or exist a sufficient condition to reveal $x'$ and $x$.

Answer 1

There is no possible solution in the general case, unless you introduce more constraints.

If you let $A=B$ for example, then $y=(Ax' + x) \oplus (Ax'+x) = 0$ so you'll never be able to solve for two n-bit values $x, x'$ from knowing only one n-bit $A$ number - otherwise, you'd have just invented the infinite data compression scheme.

Answer 2

I assume that you're given a system of equations of the form

$$y^i = (x+A^i x') \oplus (x + B^i x')$$

where the $A^i,B^i,y^i$ are known, and the goal is to find $x,x'$.

A general procedure is to recover the bits of $x,x'$ one bit at a time, starting from the least significant position and working your way up, using a pruned search.

In particular, notice that we can reduce everything modulo $k$ and obtain the equation

$$y^i = (x+A^i x') \oplus (x + B^i x') \bmod 2^k.$$

Thus, the least significant $k$ bits of $y^i$ depend only on the least significant $k$ bits of $x,x'$. Let $S_k$ denote the of all possible values for $(x \bmod 2^k, x' \bmod 2^k)$. Given $S_{k-1}$, we can enumerate all possible entries for $S_k$ and check each to see if it is consistent with all of the known equations, throwing away any inconsistent values and adding the consistent values to $S_k$. The procedure is to start with $S_1$ and iteratively calculate $S_2,S_3,\dots,S_n$. To check consistency of candidate values for $x,x' \bmod 2^k$, we just plug them into the equations, evaluate modulo $2^k$, and check whether the equation holds mod $2^k$ or not.

How efficient will this be? It depends on the number of equations you have and the numbers $A^i,B^i$. For reasonably chosen, non-degenerate values $A^i,B^i$, if you have enough equations, I expect this procedure will be efficient (much more efficient than trying all $2^{2n}$ possibilities for $x,x'$): the size of $S_k$ will be roughly constant or grow linearly with $k$, not exponentially with $k$. The more equations you have, the better -- the more equations you have, the more likely that the size of the $S_k$'s stays bounded and this remains efficient. In a pinch, two equations might suffice.