5
$\begingroup$

Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?

I have seen that Sage has one implementation (official documentation):

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("12fe342a")
sage: B.algebraic_normal_form()
x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x3*x4 + x0*x1*x3 + x0*x1*x4 + x0*x2*x3*x4 + x0*x2*x4 + x0*x3*x4 + x0*x3 + x0 + x1*x2*x4 + x1*x3 + x1*x4 + x2*x3*x4 + x2*x3 + x2*x4

But, nowhere I could find the algorithm.

It would be helpful if someone kindly explains with a suitable example.

UPDATE The answer can be found here. It is copied below.

$\endgroup$
2
$\begingroup$

The sage source code implies that algebraic normal form is the same as the Fourier expansion of the function (over the group $\mathbb{Z}_2^n$, where $n$ is the number of input bits). You can compute the Fourier transform using the well-known FFT algorithm(s).

$\endgroup$
1
$\begingroup$

Source (Credit goes to user pico of crypto.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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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