Boolean functions

Those functions are used for example in LFSR based ciphers like the filter generator or the combination generator.

This module allows to study properties linked to spectral analysis, and also algebraic immunity.

EXAMPLES:

sage: R.<x>=GF(2^8,'a')[]
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction( x^254 ) # the Boolean function Tr(x^254)
sage: B
Boolean function with 8 variables
sage: B.nonlinearity()
112
sage: B.algebraic_immunity()
4

AUTHOR:

• Rusydi H. Makarim (2016-10-13): add functions related to linear structures

• Rusydi H. Makarim (2016-07-09): add is_plateaued()

• Yann Laigle-Chapuy (2010-02-26): add basic arithmetic

• Yann Laigle-Chapuy (2009-08-28): first implementation

class sage.crypto.boolean_function.BooleanFunction

Bases: sage.structure.sage_object.SageObject

This module implements Boolean functions represented as a truth table.

We can construct a Boolean Function from either:

• an integer - the result is the zero function with x variables;

• a list - it is expected to be the truth table of the result. Therefore it must be of length a power of 2, and its elements are interpreted as Booleans;

• a string - representing the truth table in hexadecimal;

• a Boolean polynomial - the result is the corresponding Boolean function;

• a polynomial P over an extension of GF(2) - the result is the Boolean function with truth table ( Tr(P(x)) for x in GF(2^k) )

EXAMPLES:

from the number of variables:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: BooleanFunction(5)
Boolean function with 5 variables

from a truth table:

sage: BooleanFunction([1,0,0,1])
Boolean function with 2 variables

note that elements can be of different types:

sage: B = BooleanFunction([False, sqrt(2)])
sage: B
Boolean function with 1 variable
sage: [b for b in B]
[False, True]

from a string:

sage: BooleanFunction("111e")
Boolean function with 4 variables

from a sage.rings.polynomial.pbori.BooleanPolynomial:

sage: R.<x,y,z> = BooleanPolynomialRing(3)
sage: P = x*y
sage: BooleanFunction( P )
Boolean function with 3 variables

from a polynomial over a binary field:

sage: R.<x> = GF(2^8,'a')[]
sage: B = BooleanFunction( x^7 )
sage: B
Boolean function with 8 variables

two failure cases:

sage: BooleanFunction(sqrt(2))
Traceback (most recent call last):
...
TypeError: unable to init the Boolean function

sage: BooleanFunction([1, 0, 1])
Traceback (most recent call last):
...
ValueError: the length of the truth table must be a power of 2

absolut_indicator(*args, **kwds)

Deprecated: Use absolute_indicator() instead. See trac ticket #28001 for details.

absolute_autocorrelation()

Return the absolute autocorrelation of the function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: sorted(B.absolute_autocorrelation().items())
[(0, 33), (8, 58), (16, 28), (24, 6), (32, 2), (128, 1)]

absolute_indicator()

Return the absolute indicator of the function.

The absolute indicator is defined as the maximal absolute value of the autocorrelation.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: B.absolute_indicator()
32

The old method’s name contained a typo, it is deprecated:

sage: B.absolut_indicator()
doctest:warning
...
DeprecationWarning: absolut_indicator is deprecated. Please use absolute_indicator instead.
See https://trac.sagemath.org/28001 for details.
32

absolute_walsh_spectrum()

Return the absolute Walsh spectrum fo the function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: sorted(B.absolute_walsh_spectrum().items())
[(0, 64), (16, 64)]

sage: B = BooleanFunction("0113077C165E76A8")
sage: B.absolute_walsh_spectrum()
{8: 64}

algebraic_degree()

Return the algebraic degree of this Boolean function.

The algebraic degree of a Boolean function is defined as the degree of its algebraic normal form. Note that the degree of the constant zero function is defined to be equal to -1.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B.<x0, x1, x2, x3> = BooleanPolynomialRing()
sage: f = BooleanFunction(x1*x2 + x1*x2*x3 + x1)
sage: f.algebraic_degree()
3
sage: g = BooleanFunction([0, 0])
sage: g.algebraic_degree()
-1

algebraic_immunity(annihilator=False)

Return the algebraic immunity of the Boolean function.

This is the smallest integer \(i\) such that there exists a non trivial annihilator for \(self\) or \(~self\).

INPUT:

• annihilator – a Boolean (default: False), if True, returns also an annihilator of minimal degree.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: R.<x0,x1,x2,x3,x4,x5> = BooleanPolynomialRing(6)
sage: B = BooleanFunction(x0*x1 + x1*x2 + x2*x3 + x3*x4 + x4*x5)
sage: B.algebraic_immunity(annihilator=True)
(2, x0*x1 + x1*x2 + x2*x3 + x3*x4 + x4*x5 + 1)
sage: B[0] +=1
sage: B.algebraic_immunity()
2

sage: R.<x> = GF(2^8,'a')[]
sage: B = BooleanFunction(x^31)
sage: B.algebraic_immunity()
4

algebraic_normal_form()

Return the sage.rings.polynomial.pbori.BooleanPolynomial corresponding to the algebraic normal form.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction([0,1,1,0,1,0,1,1])
sage: P = B.algebraic_normal_form()
sage: P
x0*x1*x2 + x0 + x1*x2 + x1 + x2
sage: [ P(*ZZ(i).digits(base=2,padto=3)) for i in range(8) ]
[0, 1, 1, 0, 1, 0, 1, 1]

annihilator(d, dim=False)

Return (if it exists) an annihilator of the boolean function of degree at most \(d\), that is a Boolean polynomial \(g\) such that

\[f(x)g(x) = 0 \forall x.\]

INPUT:

• d – an integer;

• dim – a Boolean (default: False), if True, return also the dimension of the annihilator vector space.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: f = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: f.annihilator(1) is None
True
sage: g = BooleanFunction( f.annihilator(3) )
sage: set([ fi*g(i) for i,fi in enumerate(f) ])
{0}

autocorrelation()

Return the autocorrelation of the function, defined by

\[\Delta_f(j) = \sum_{i\in\{0,1\}^n} (-1)^{f(i)\oplus f(i\oplus j)}.\]

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("03")
sage: B.autocorrelation()
(8, 8, 0, 0, 0, 0, 0, 0)

correlation_immunity()

Return the maximum value \(m\) such that the function is correlation immune of order \(m\).

A Boolean function is said to be correlation immune of order \(m\) , if the output of the function is statistically independent of the combination of any m of its inputs.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: B.correlation_immunity()
2

derivative(u)

Return the derivative in direction of u

INPUT:

• u – either an integer or a tuple/list of \(\GF{2}\) elements of length equal to the number of variables

The derivative of \(f\) in direction of \(u\) is defined as \(x \mapsto f(x) + f(x + u)\).

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: f = BooleanFunction([0,1,0,1,0,1,0,1])
sage: f.derivative(1).algebraic_normal_form()
1
sage: u = [1,0,0]
sage: f.derivative(u).algebraic_normal_form()
1
sage: v = vector(GF(2), u)
sage: f.derivative(u).algebraic_normal_form()
1
sage: f.derivative(8).algebraic_normal_form()
Traceback (most recent call last):
...
IndexError: index out of bound

has_linear_structure()

Return True if this function has a linear structure.

An \(n\)-variable Boolean function \(f\) has a linear structure if there exists a nonzero \(a \in \GF{2}^n\) such that \(f(x \oplus a) \oplus f(x)\) is a constant function.

See also

is_linear_structure(), linear_structures().

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
sage: f.has_linear_structure()
True
sage: f.autocorrelation()
(16, -16, 0, 0, 0, 0, 0, 0, -16, 16, 0, 0, 0, 0, 0, 0)
sage: g = BooleanFunction([0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1])
sage: g.has_linear_structure()
False
sage: g.autocorrelation()
(16, 4, 4, 4, 4, -4, -4, -4, -4, 4, -4, -4, -4, 4, -4, -4)

is_balanced()

Return True if the function takes the value True half of the time.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction(1)
sage: B.is_balanced()
False
sage: B[0] = True
sage: B.is_balanced()
True

is_bent()

Return True if the function is bent.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("0113077C165E76A8")
sage: B.is_bent()
True

is_linear_structure(val)

Return True if val is a linear structure of this Boolean function.

INPUT:

• val – either an integer or a tuple/list of \(\GF{2}\) elements of length equal to the number of variables

See also

has_linear_structure(), linear_structures().

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
sage: f.is_linear_structure(1)
True
sage: l = [1, 0, 0, 1]
sage: f.is_linear_structure(l)
True
sage: v = vector(GF(2), l)
sage: f.is_linear_structure(v)
True
sage: f.is_linear_structure(7)
False
sage: f.is_linear_structure(20) #parameter is out of range
Traceback (most recent call last):
...
IndexError: index out of range
sage: v = vector(GF(3), [1, 0, 1, 1])
sage: f.is_linear_structure(v)
Traceback (most recent call last):
...
TypeError: base ring of input vector must be GF(2)
sage: v = vector(GF(2), [1, 0, 1, 1, 1])
sage: f.is_linear_structure(v)
Traceback (most recent call last):
...
TypeError: input vector must be an element of a vector space with dimension 4
sage: f.is_linear_structure('X') #failure case
Traceback (most recent call last):
...
TypeError: cannot compute is_linear_structure() using parameter X

is_plateaued()

Return True if this function is plateaued, i.e. its Walsh transform takes at most three values \(0\) and \(\pm \lambda\), where \(\lambda\) is some positive integer.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: R.<x0, x1, x2, x3> = BooleanPolynomialRing()
sage: f = BooleanFunction(x0*x1 + x2 + x3)
sage: f.walsh_hadamard_transform()
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, -8)
sage: f.is_plateaued()
True

is_symmetric()

Return True if the function is symmetric, i.e. invariant under permutation of its input bits. Another way to see it is that the output depends only on the Hamming weight of the input.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction(5)
sage: B[3] = 1
sage: B.is_symmetric()
False
sage: V_B = [0, 1, 1, 0, 1, 0]
sage: for i in srange(32): B[i] = V_B[i.popcount()]
sage: B.is_symmetric()
True

linear_structures()

Return all linear structures of this Boolean function as a vector subspace of \(\GF{2}^n\).

See also

is_linear_structure(), has_linear_structure().

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
sage: LS = f.linear_structures()
sage: LS.dimension()
2
sage: LS.basis_matrix()
[1 0 0 0]
[0 0 0 1]
sage: LS.list()
[(0, 0, 0, 0), (1, 0, 0, 0), (0, 0, 0, 1), (1, 0, 0, 1)]

nonlinearity()

Return the nonlinearity of the function. This is the distance to the linear functions, or the number of output ones need to change to obtain a linear function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction(5)
sage: B[1] = B[3] = 1
sage: B.nonlinearity()
2
sage: B = BooleanFunction("0113077C165E76A8")
sage: B.nonlinearity()
28

nvariables()

The number of variables of this function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: BooleanFunction(4).nvariables()
4

resiliency_order()

Return the maximum value \(m\) such that the function is resilient of order \(m\).

A Boolean function is said to be resilient of order \(m\) if it is balanced and correlation immune of order \(m\).

If the function is not balanced, we return -1.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("077CE5A2F8831A5DF8831A5D077CE5A26996699669699696669999665AA5A55A")
sage: B.resiliency_order()
3

sum_of_square_indicator()

Return the sum of square indicator of the function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: B.sum_of_square_indicator()
32768

truth_table(format='bin')

The truth table of the Boolean function.

INPUT: a string representing the desired format, can be either

• ‘bin’ (default) : we return a tuple of Boolean values

• ‘int’ : we return a tuple of 0 or 1 values

• ‘hex’ : we return a string representing the truth_table in hexadecimal

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: R.<x,y,z> = BooleanPolynomialRing(3)
sage: B = BooleanFunction( x*y*z + z + y + 1 )
sage: B.truth_table()
(True, True, False, False, False, False, True, False)
sage: B.truth_table(format='int')
(1, 1, 0, 0, 0, 0, 1, 0)
sage: B.truth_table(format='hex')
'43'

sage: BooleanFunction('00ab').truth_table(format='hex')
'00ab'

sage: H = '0abbacadabbacad0'
sage: len(H)
16
sage: T = BooleanFunction(H).truth_table(format='hex')
sage: T == H
True
sage: H = H * 4
sage: T = BooleanFunction(H).truth_table(format='hex')
sage: T == H
True
sage: H = H * 4
sage: T = BooleanFunction(H).truth_table(format='hex')
sage: T == H
True
sage: len(T)
256
sage: B.truth_table(format='oct')
Traceback (most recent call last):
...
ValueError: unknown output format

walsh_hadamard_transform()

Compute the Walsh Hadamard transform \(W\) of the function \(f\).

\[W(j) = \sum_{i\in\{0,1\}^n} (-1)^{f(i)\oplus i \cdot j}\]

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: R.<x> = GF(2^3,'a')[]
sage: B = BooleanFunction( x^3 )
sage: B.walsh_hadamard_transform()
(0, -4, 0, 4, 0, 4, 0, 4)

class sage.crypto.boolean_function.BooleanFunctionIterator

Bases: object

Iterator through the values of a Boolean function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction(3)
sage: type(B.__iter__())
<type 'sage.crypto.boolean_function.BooleanFunctionIterator'>

sage.crypto.boolean_function.random_boolean_function(n)

Return a random Boolean function with \(n\) variables.

EXAMPLES:

sage: from sage.crypto.boolean_function import random_boolean_function
sage: B = random_boolean_function(9)
sage: B.nvariables()
9
sage: while not (210 < B.nonlinearity() < 220):
....:     B = random_boolean_function(9)

sage.crypto.boolean_function.unpickle_BooleanFunction(bool_list)

Specific function to unpickle Boolean functions.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction([0,1,1,0])
sage: loads(dumps(B)) == B # indirect doctest
True