2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For sure you are correct on observing this point. But I am not asking for the general case. Take the least-significant-bit of $x'$ for example. Under $\bmod 2$, the lsb of the equation reduces to $y_0=(A_0x'_0 \oplus x_0) \oplus (B_0x'_0 \oplus x_0)$, then if A is odd and B is even, we have $x'_0 = y_0$. Also I mentioned that "may be I need multiple copies of $A$, $B$ and $y$" to get $x'$ and $x$. $\endgroup$ – leo_cityu Oct 25 '16 at 6:18
  • $\begingroup$ @leo_cityu Please edit all the necessary information into the question itself, not comments. I mentioned that "may be I need multiple copies of A, B and y" to get x′ and x That would make it not one equation, but rather a system of multiple equations, subject to additional constraints that you haven't spelled out thus far. See How do I ask a good question?. $\endgroup$ – dxiv Oct 25 '16 at 6:26

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.