2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.