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

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

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.