1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @kelalaka: What code should I write in Sage to obtain a possible expression? $\endgroup$ Sep 30, 2023 at 7:06
  • 1
    $\begingroup$ (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 $\endgroup$
    – kelalaka
    Sep 30, 2023 at 8:22
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Sep 30, 2023 at 16:12
  • 1
    $\begingroup$ @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}$.) $\endgroup$ Oct 3, 2023 at 2:44

1 Answer 1

2
$\begingroup$

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$
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Oct 1, 2023 at 16:02
  • $\begingroup$ wolframalpha.com/… $\endgroup$
    – kelalaka
    Oct 2, 2023 at 6:32
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Oct 2, 2023 at 6:33
  • $\begingroup$ 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)? $\endgroup$ Oct 3, 2023 at 3:04
  • $\begingroup$ @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. $\endgroup$
    – Daniel S
    Oct 3, 2023 at 6:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.