# A problem related to three outputs of the majority function for nine rotations of three bitstrings

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

Let $$m(b_1,b_2,b_3)$$ denote the majority function: for example, $$m(10010111,00101110,10100000)=10100110.$$

Consider the following game. Player A picks three arbitrary $$n$$-bit strings $$(S_1,S_2,S_3)$$ and nine arbitrary integers $$(k_1,k_2,\ldots,k_9)$$ less than $$n.$$ Then Player A computes

$$\begin{array}{l} X_1 = m(r(S_1,k_1), r(S_2,k_2), r(S_3,k_3)),\\ X_2 = m(r(S_1,k_4), r(S_2,k_5), r(S_3,k_6)),\\ X_3 = m(r(S_1,k_7), r(S_2,k_8), r(S_3,k_9)), \end{array}$$

then reveals $$X_1$$, $$X_2$$ and $$X_3$$ to Player B (we can assume that $$X_1 \neq X_2, X_1 \neq X_3, X_2 \neq X_3.$$)

Given $$X_1$$, $$X_2$$ and $$X_3$$, how hard is it (in the average case) for the Player B to find three arbitrary $$n$$-bit strings $$(Y_1,Y_2,Y_3)$$ and nine arbitrary integers $$(v_1,v_2,\ldots,v_9)$$ such that $$\begin{array}{l} X_1 = m(r(Y_1,v_1), r(Y_2,v_2), r(Y_3,v_3)),\\ X_2 = m(r(Y_1,v_4), r(Y_2,v_5), r(Y_3,v_6)),\\ X_3 = m(r(Y_1,v_7), r(Y_2,v_8), r(Y_3,v_9))? \end{array}$$

• Doesn't look that difficult; one approach would be to assign $v_1=v_2=v_3=0$, nonzero random values for the others, and then do backtracking at a bit level (e.g. look at the four possible bit settings of bit 0 of $X_0$, and follow the implications. My guess is that most branches relatively quickly run into contradictions, and if so, you either find a solution or not (and if not, try other random settings for $v_4$ et al). I haven't actually tried it, though... Jul 20, 2023 at 18:07