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 in cs.stackexchange

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.

• can the same be extended to 8-bit sbox? like AES sbox? – crypt Sep 29 '20 at 16:34
• @abraza Yes, it'll work for any sbox – hola Sep 30 '20 at 1:18
• I would also note that applying $M_2$ recursively leads to complexity $k2^k$. That is, xor the right half to the left half, then recurse to each half. – Fractalice Sep 30 '20 at 17:39
• @Fractalic Where is this sequence $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,\ldots$ from? That is, how do I generate it for any $k$? – E.Nole Dec 17 '20 at 23:58
• @E.Nole It is derived from the binary expansion of the index. $x_i$ is included if $i$-th bit in the index is set. – Fractalice Dec 18 '20 at 8:10

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.

• I think the tag is well written – kodlu Oct 1 '20 at 3:03

It is possible to use the SageMath, too. With the help of

SBox package

component_function(b): Return a Boolean function corresponding to the component function $$b\cdot S(x)$$

and from Boolean funcions package

algebraic_normal_form(): Return the sage.rings.polynomial.pbori.BooleanPolynomial corresponding to the algebraic normal form.

S = SBox(6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11);

f0 = S.component_function(1)
f1 = S.component_function(2)
f2 = S.component_function(4)
f3 = S.component_function(8)

print ( "y0 = ", f0.algebraic_normal_form())
print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())


Providing the output

\begin{align} y_0 &= x_{0} x_{1} + x_{0} x_{2} x_{3} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{2} x_{3} + x_{1} x_{2} + x_{1}\\ y_1 &= x_{0} x_{2} + x_{0} x_{3} + x_{0} + x_{1} x_{2} + x_{1} x_{3} + x_{2} + 1\\ y_2 &= x_{0} x_{1} x_{3} + x_{0} x_{1} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{2} x_{3} + x_{2} x_{3} + x_{2} + 1\\ y_3 &= x_{0} x_{1} x_{3} + x_{0} x_{1} + x_{0} x_{2} x_{3} + x_{0} x_{3} + x_{3} \end{align}

The Sbox package of Sage has lots of other tools, too. Some are;

• autocorrelation table
• boomerang connectivity table (BCT)
• Conjunctive Normal Form (CNF)
• fixed points
• has a linear structure
• Linearity
• Non-Linearity
• inverse
• almost perfect nonlinear (APN) function.
• Balanced
• Bent
• Involution
• Permutation
• Max Degree
• Min Degree
• polynomials satisfying the S-box.

There is a simple way based on repeated linear interpolation, known as the Shannon-expansion.

With this you can extract the ANF expression from any black-box map function (for example, an S-Box) using on the order of $$2^n$$ evaluations for an $$n$$-bit Boolean function. It's slow but remarkably simple. I will demonstrate using $$2$$-bit function.

$$f(x_0,x_1)$$

can be expanded in the first bit

$$\small{f(x_0,x_1) = f(0,x_1)(1-x_0) \; + \; f(1,x_1){x_0}}$$

and then again in the second bit

$$\small{f(x_0,x_1) = f(0,0)(1-x_0)(1-x_1) \; + \; f(0,1)(1-x_0)x_1 \; + \; f(1,0){x_0}(1-x_1) \; + \; f(1,1){x_0}{x_1}}$$

Repeating this with larger functions, the pattern becomes clear. The $$k$$th term in this expression simply multiplies $$\small{f(x)}$$ with either a $$x_i$$ or $$\small(1-x_i)$$, depending on the setting of the bit in the input to the map function.

So for a larger Boolean function, the first term would be

$$\small{f(0,0,0,0,\ldots,0)(1-x_0)(1-x_1)(1-x_2)(1-x_3)\ldots(1-x_n)}$$

and the final term would be

$$\small{f(1,1,1,1,\ldots,1)x_0 x_1 x_2 x_3\ldots x_n}$$

The ANF can then be derived from this expression by multiplying out the parenthesis. This is laborious by hand, but a small amount of code in a computer program.

Here is the idea implemented in C++

#include <iostream>
#include <vector>

/* black-box map function to extract ANF */
int map(int x) {
int sbox[] = {6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11};
return sbox[x % 16];
}

int num_input_bits = 4; /* number of map input bits to consider */
int num_output_bits = 4; /* number of map output bits to consider */

/* (1-x_0)(1-x1)x_2 = x_2*(1 + x_0 + x_1 + x_0*x_1) */

int main() {
/* step 1) calculate ANF of the map function */
int num_input_states = 1 << num_input_bits;
for (int i = 0; i < num_output_bits; ++i) {
std::vector<int> anf(num_input_states); /* accumulate ANF here */
for (int j = 0; j < num_input_states; ++j) {
int bit = (map(j) >> i) & 1; /* extract map output bit */
if (bit == 1) {
for (int k = 0; k < num_input_states; ++k) { /* "broadcast" result to ANF terms */
if ((j & k) == j) { /* does this bit contribute to this ANF term? */
anf[k] = (anf[k] + 1) % 2;
}
}
}
}
/* step 2) print the ANF expression */
std::cout << "y_" << i << " = ";
int term_count = 0;
for (int j = 0; j < anf.size(); ++j) {
if (anf[j]) {
std::cout << (term_count++ != 0 ? " + " : "");
size_t factor_count = 0;
for (int k = 0; k < num_input_bits; ++k) {
if ((j >> k) & 1) {
std::cout << (factor_count++ != 0 ? "*" : "");
std::cout << "x_" << k;
}
}
if (factor_count == 0) {
std::cout << "1"; /* empty product */
}
}
}
if (term_count == 0) {
std::cout << "0"; /* empty sum */
}
std::cout << std::endl;
}
return 0;
}


Which outputs the ANF representation of your S-Box:

y_0 = x_1 + x_0*x_1 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_0*x_2*x_3 + x_1*x_2*x_3
y_1 = 1 + x_0 + x_2 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_1*x_3
y_2 = 1 + x_0*x_1 + x_2 + x_0*x_2 + x_0*x_3 + x_0*x_1*x_3 + x_2*x_3 + x_1*x_2*x_3
y_3 = x_0*x_1 + x_3 + x_0*x_3 + x_0*x_1*x_3 + x_0*x_2*x_3

• That is great. It explains why the Mobious transform works. – hola Oct 2 '20 at 2:47
• I think this answer will be much great if you bring the Shannon-expansion and Mobius transform relation. – kelalaka Oct 2 '20 at 8:38
• The last two equations of $f$ confusingly changed notation: $f(1,\ldots,1)$ somehow now means the coefficient of $x_0x_1\ldots,x_{n-1}$ instead of the value fo $f$ on the input $(1,1,\ldots,1)$. Maybe simply remove the = sign. – Fractalice Oct 5 '20 at 12:03
• Thanks & Fixed @Fractalic – conchild Oct 5 '20 at 17:49