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

  • $\begingroup$ 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... $\endgroup$
    – poncho
    Jul 20, 2023 at 18:07


Your Answer

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

Browse other questions tagged or ask your own question.