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

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

• @kelalaka: What code should I write in Sage to obtain a possible expression? Commented Sep 30, 2023 at 7:06
• (Updated) The modular addition make the inverse hard to express. Do you want the optimum one or one of the possible expression? In the later case, just use Sage Sbox package to get the inverse and try to express the $𝑥_𝑖$ by hand? The cnf might help some Commented Sep 30, 2023 at 8:22
• Are you sure $\boxplus$ is addition modulo $2^m$? That's not the same as addition in $\mathbb F_{2^m}$ (for $m\ge2)$. And that would imply $\rho$ has no right diffusion, since neither $\oplus$ nor $\boxplus$ has right diffusion.
– fgrieu
Commented Sep 30, 2023 at 16:12
• @fgrieu: according to Section 2.1 of the paper, $\oplus$ denotes the bitwise XOR, and $\boxplus$ denotes the addition modulo $2^t$ (for an element $a \in \mathbb{F}_{2^t}$.) Commented Oct 3, 2023 at 2:44

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$$
• Maj is the carry out of the Full-Adder. Are there any work to reduce this with the final x-or? Maj still quite complex, and this is like hiding the complexcity under a rug. Commented Oct 1, 2023 at 16:02
• wolframalpha.com/… Commented Oct 2, 2023 at 6:32
• Wolfram can draw the circuit, however, it seem like there is not so much for an individual simplification. May be in hardware, one can consider all inputs together to reduce the cost of time and area. Commented Oct 2, 2023 at 6:33
• Why is the binary matrix in this answer different from the matrix representation for the linear part of the update function (Theorem 4 in the paper)? Commented Oct 3, 2023 at 3:04
• @lyricallywicked: Because they are taking $\mathbf x=[x_3\ x_2\ x_1\ x_0]^T$ whereas I have done the reverse. It's the mathematical equivalent of endianness. Commented Oct 3, 2023 at 6:15