A problem related to two bitwise sums of rotations of two different bitstrings

Question

Let $r(b, t)$ denote the bitstring $b$ rotated to the left by $t$ bits: for example, $r(00110101, 5) = 10100110.$

Consider the following game. Player A picks two (different) $n$-bit strings $(T_1, T_2)$ and four arbitrary numbers $(a, b, c, d)$ less than $n$. Then Player A computes $$B_1 = r(T_1, a) \oplus r(T_2, b)$$ and $$B_2 = r(T_1, c) \oplus r(T_2, d),$$ then reveals $B_1$ and $B_2$ to Player B (we can assume that $B_1 \neq B_2$).

Given $B_1$ and $B_2$, how hard is it (in the average case) for the Player B to find two (different) $n$-bit strings $X_1$ and $X_2$ and four arbitrary numbers $(t, u, v, w)$ such that $$r(X_1, t) \oplus r(X_2, u) = B_1$$ and $$r(X_1, v) \oplus r(X_2, w) = B_2?$$

Answer 1

There's a very easy way to find a solution with $t=u=v=0$ and $w=1$ say. First note that the parity of the Hamming weights of $B_1$ and $B_2$ are the same and hence the Hamming weight of $B_1\oplus B_2$ is even.

We can consider bit strings under rotation as representatives of $\mathbb F_2[z]/(z^n\oplus 1)\mathbb F_2[z]$ and left rotation as multiplication by $z$. In this setting, binary strings with even Hamming weight correspond to polynomials that are multiples of $z\oplus 1$ and we can easily recover the cofactor by polynomial division. In this framework, with $t=u=v=0$ and $w=1$ by abuse of notation we can write $$X_1(z)\oplus X_2(z)=B_1(z)$$ $$X_1(z)\oplus zX_2(z)=B_2(z)$$ and hence $$(z+\oplus 1)X_2(z)=B_1(z)\oplus B_2(z).$$

Thus by taking the polynomial represented by $B_1\oplus B_2$ and dividing by $z+1$ we get a polynomial that can correspond to our $X_2$ string then by either XORing this with $B_1$ or its shift with $B_2$ we can recover $X_1$.

For example, suppose that we have $B_1$= 00110101 and $B_2$= 10011001. We can form $B_1\oplus B_2$= 10101100 corresponding to the polynomial $z^7\oplus z^5\oplus z^3\oplus z^2$ which we can divide by $z\oplus 1$ to get $z^6\oplus z^5\oplus z^2$ and use this to choose the string $X_2$ = 01100100. We then see that $B_1\oplus X_2$= 01010001 which will be our $X_1$. We note that $X_1\oplus r(X_1,1)$= 01010001$\oplus$11001000= 10011001=$B_2$ as required.