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:
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!