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

lyrically wicked

6/28/24, 7:31 AM

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

1 + 0

xor

complexity

Score:2

Crypto

Daniel S

6/28/24, 9:25 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.