# Generate ANF from SBox

Given an SBox, how can I generate its component equations (in ANF)?

For example, let's say I have this SBox:

6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11

Then, the equations are:

$$y_0 = x_1 \oplus x_0x_1 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_0x_2x_3 \oplus x_1x_2x_3$$

$$y_1 = 1 \oplus x_0 \oplus x_2 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_1x_3$$

$$y_2 = 1 \oplus x_0x_1 \oplus x_2 \oplus x_0x_2 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3$$

$$y_3 = x_0x_1 \oplus x_3 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_0x_2x_3$$

The same question is asked here

From TRUTH TABLE to ANF

First write [6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11] in that way: the columns of matrix are those numbers in $\mathbb{F_2^4}$. $$\begin{bmatrix} 0&0&1&0&0&1&0&0&0&1&1&1&0&1&1&1\\ 1&0&1&0&0&0&1&1&1&1&0&0&0&1&0&1\\ 1&1&1&0&0&1&0&0&1&0&1&0&1&1&0&0\\ 0&0&0&1&0&0&0&1&1&0&1&0&1&1&1&1 \end{bmatrix}$$ Then multiply it with Moebius transformation matrix :

$$M_1 = \begin{bmatrix} 1 \end{bmatrix}, M_2 = \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix}, \cdots, M_{2^k} = M_2 \otimes M_{2^{k-1}} = \begin{bmatrix} M_{2^{k-1}}&M_{2^{k-1}}\\ 0&M_{2^{k-1}} \end{bmatrix}.$$ So for $k=4$, the matrix is: $$\begin{bmatrix} 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 \\ 0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{bmatrix}$$ Then you have this matrix: $$\begin{bmatrix} 0&0&1&1&0&1&1&0&0&1&0&0&0&1&1&0\\ 1&1&0&0&1&1&1&0&0&1&1&0&0&0&0&0\\ 1&0&0&1&1&1&0&0&0&1&0&1&1&0&1&0\\ 0&0&0&1&0&0&0&0&1&1&0&1&0&1&0&0 \end{bmatrix}$$ Each row gives the coordinate function $S_1,S_2,S_3$and $S_4$ resp. The entries of each row are the coefficients of $1, x_0, x_1, x_0x_1, x_2, x_0x_2, x_1x_2, x_0x_1x_2, x_3, x_0x_3, x_1x_3, x_0x_1x_3, x_2x_3, x_0x_2x_3, x_1x_2x_3, x_0x_1x_2x_3$.

From ANF to TRUTH TABLE (TT)

Exactly the inverse of operations. Note that $M_{2^k}^{-1}=M_{2^k}$ for any $k$.

i.e. [TT] * $[M]$ = [ANF] and [TT] = [ANF] * $[M]$.

Note: The arithmetics are taken modulo 2.

This is useful to know in general.

Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $n-$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$

where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $\mathbb{F}_2^n$ in standard order, the function has an anf representation given by $$f(x)=\sum_{y \in \mathbb{F}_2^n} a_y \prod_{1\leq i\leq n~:~y_i=1} x_i$$ which means the variable $x_i$ is included in the monomial product corresponding to the coefficient $a_y$ if and only if $i$ is in the support of the vector $y.$

So if we had $y=(y_1,y_2,y_3,y_4)=(1,0,1,0),$ for $n=4,$ the coefficient $a_y$ multiplies the monomial $x_1 x_3$.

The transform computes the coefficients $a_y$ by the sum $$a_y=\sum_{x\preccurlyeq y} f(x) ~(mod~2),$$ where $x \preccurlyeq y$ means the support of $x$ is a subset of the support of $y.$

The complexity is $N \log N$ where $N=2^n,$ so this is a fast transform.

• Thanks, but it's still not clear. Can you elaborate on how to compute $a_y$ (may be, with an example)? – yyyy0000 Jun 4 '17 at 15:46