What is the inverse of this generalised automaton (based on bitwise XOR and modular addition)?

Question

Section 4.1 of the paper “Nonlinear Diffusion Layers” [Y. Liu, V. Rijmen, G. Leander] defines the nonlinear function $\rho$ over $\mathbb{F}_{2^m}$ as follows: $$\rho : \mathbb{F}_{2^m}^4 \to \mathbb{F}_{2^m}^4 : (x_3, x_2, x_1, x_0) \mapsto (y_3, y_2, y_1, y_0),$$ where $$y_i = x_i \oplus (x_{i + 1} \boxplus x_{i + 2}), 0 \leq i \leq 3, m \geq 2.$$ Here $\oplus$ is bitwise XOR, $\boxplus$ is addition modulo $2^m.$ Then Remark 2 says,

Note that $\rho$ is of a similar nature as the Sbox ($\chi$ function) adopted in the SHA-3 permutation keccak-f, which is a generalised automaton. Although $\rho$ is invertible, the inverse of $\rho$ seems to be of no simple expression.

My question is: what is the expression for the inverse of $\rho$?

Answer 1

As the paper says, there is not a simple expression. The $\boxplus$ operator is surprisingly complex as a Boolean algebraic expression. It does however act analogously to a $T$-function and so there is a moderately simple algorithmic expression for the computation of the inverse.

Things are probably helped by introducing $m$-bit "carry" variables $c_{i,j}$ which represent the carry bits when adding $x_i$ to $x_j$ modulo $2^m$. If we write $w^{(b)}$ for the $b$th bit of the $m$-bit value $w$ we have $c_{i,j}^{(0)}=0$ and $$c_{i,j}^{(b+1)}=\mathrm{maj}(c_{i,j}^{(b)},x_i^{(b)},x_j^{(b)})$$ where $\mathrm{maj}$ is the majority vote function. We then have $$y_i^{(b)}=x_i^{(b)}\oplus x_{i+1}^{(b)}\oplus x_{i+2}^{(b)}\oplus c_{i+1,i+2}^{(b)}$$ which is a purely $\mathbb F_2$ linear function in our variables. N.B. subscripts wrap mod 4 in the paper and we'll assume that they do here as well.

The $b$th bits of our $x_i$ can now be calculated from the $b$th bits of our $y_i$ and $c_{i,i+1}$ because $$\begin{pmatrix}1&1&1&0\\ 0&1&1&1\\ 1&0&1&1\\1&1&0&1\end{pmatrix}\begin{pmatrix}x^{(b)}_0\\x^{(b)}_1\\x^{(b)}_2\\x^{(b)}_3\end{pmatrix}=\begin{pmatrix}y^{(b)}_0\oplus c^{(b)}_{1,2}\\y^{(b)}_1\oplus c^{(b)}_{2,3}\\ y^{(b)}_2\oplus c^{(b)}_{3,0}\\y^{(b)}_3\oplus c^{(b)}_{0,1}\end{pmatrix}$$ $$\begin{pmatrix}1&1&1&0\\ 0&1&1&1\\ 1&0&1&1\\1&1&0&1\end{pmatrix}\begin{pmatrix}y^{(b)}_0\oplus c^{(b)}_{1,2}\\y^{(b)}_1\oplus c^{(b)}_{2,3}\\y^{(b)}_2\oplus c^{(b)}_{3,0}\\y^{(b)}_3\oplus c^{(b)}_{0,1}\end{pmatrix}=\begin{pmatrix}x^{(b)}_0\\x^{(b)}_1\\x^{(b)}_2\\x^{(b)}_3\end{pmatrix}.$$

Thus in pseudo-code,

1. $\textbf{let } c\leftarrow [0,0,0,0]^T$
2. $\textbf{for } b \textbf{ in } 0,\dots, m-1$
3. $\quad\textbf{for } i \textbf{ in } 0,\ldots, 3$
4. $\quad\quad \textbf{let } v[i]\leftarrow c[i]\oplus y^{(b)}[i]$
5. $\quad\textbf{end } i$
6. $\quad\textbf{for } j \quad\textbf{ in } 0,\ldots, 3$
7. $\quad\quad\textbf{let } x^{(b)}[j]\leftarrow v[i]\oplus v[(i+1)\mod 4]\oplus v[(i+2)\bmod 4]$
8. $\quad\textbf{end } j$
9. $\quad\textbf{for }k \textbf{ in } 0,\ldots, 3$
10. $\quad\quad\textbf{ let } c[k]=\mathrm{maj}(c[k],x^{(b)}_{(k+1)\mod 4},x^{(b)}_{(k+2)\bmod 4})$
11. $\quad\textbf{end } k$
12. $\textbf{end }b$