It is sometimes important to be able to quickly convert a binary function, described in as a truth table, to its Algebraic Normal Form (or simply, ANF). The truth table basically lists the points where a function is 1 and when it is 0. For instance, if the function has two variables, and its truth table is `0110`

or, in hexadecimal form, `0x5`

then the ANF of this function is simply `x0 + x1`

, where `x0`

is the first variable of the function, and `x1`

is the second.

When it comes to more complex functions, an automatic method for this conversion is helpful. The Sage software can do exactly that:

1 2 3 4 5 |
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("0123456789ABCDEF") sage: B.algebraic_normal_form() x0*x1*x2 + x0*x1*x3 + x0*x1*x4 + x0*x1*x5 + x0*x2 + x0*x3 + x1*x2 + x1*x4 + x2 + 1 |

Here, we used Sage to convert the function given by the truth table (in hex) `0x0123456789ABCDEF`

to its ANF equivalent.

I have long searched for a method for this, but at the end it was Luk Bettale who showed me the way. Many thanks to him for this!