Boolean functions - Cryptography (2024)

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

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

EXAMPLES:

sage: # needs sage.rings.finite_ringssage: R.<x> = GF(2^8,'a')[]sage: from sage.crypto.boolean_function import BooleanFunctionsage: B = BooleanFunction(x^254); B # the Boolean function Tr(x^254)Boolean function with 8 variablessage: B.nonlinearity()112sage: B.algebraic_immunity() # needs sage.rings.polynomial.pbori4

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: 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 theresult. Therefore it must be of length a power of 2, and itselements 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 isthe Boolean function with truth table (Tr(P(x)) for x inGF(2^k))

EXAMPLES:

from the number of variables:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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)]); B # needs sage.symbolicBoolean function with 1 variablesage: [b for b in B] # needs sage.symbolic[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) # needs sage.rings.polynomial.pborisage: P = x*y # needs sage.rings.polynomial.pborisage: BooleanFunction(P) # needs sage.rings.polynomial.pboriBoolean function with 3 variables

from a polynomial over a binary field:

sage: R.<x> = GF(2^8,'a')[] # needs sage.rings.finite_ringssage: B = BooleanFunction(x^7); B # needs sage.rings.finite_ringsBoolean function with 8 variables

two failure cases:

sage: BooleanFunction(sqrt(2)) # needs sage.symbolicTraceback (most recent call last):...TypeError: unable to init the Boolean functionsage: 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 github issue #28001 for details.

absolute_autocorrelation()#

Return the absolute autocorrelation of the function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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 ofthe autocorrelation.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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://github.com/sagemath/sage/issues/28001 for details.32

absolute_walsh_spectrum()#

Return the absolute Walsh spectrum fo the function.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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 degreeof its algebraic normal form. Note that the degree of the constantzero function is defined to be equal to \(-1\).

EXAMPLES:

sage: # needs sage.rings.polynomial.pborisage: from sage.crypto.boolean_function import BooleanFunctionsage: B.<x0, x1, x2, x3> = BooleanPolynomialRing()sage: f = BooleanFunction(x1*x2 + x1*x2*x3 + x1)sage: f.algebraic_degree()3sage: 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 anontrivial annihilator for self or ~self.

INPUT:

annihilator – boolean (default: False); if True,returns also an annihilator of minimal degree

EXAMPLES:

sage: # needs sage.rings.polynomial.pborisage: from sage.crypto.boolean_function import BooleanFunctionsage: 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] += 1sage: B.algebraic_immunity()2sage: # needs sage.rings.finite_rings sage.rings.polynomial.pborisage: 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.BooleanPolynomialcorresponding to the algebraic normal form.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: B = BooleanFunction([0,1,1,0,1,0,1,1])sage: P = B.algebraic_normal_form(); P # needs sage.rings.polynomial.pborix0*x1*x2 + x0 + x1*x2 + x1 + x2sage: [P(*ZZ(i).digits(base=2, padto=3)) for i in range(8)] # needs sage.rings.polynomial.pbori[0, 1, 1, 0, 1, 0, 1, 1]

annihilator(d, dim=False)#

Return (if it exists) an annihilator of the boolean function ofdegree 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 alsothe dimension of the annihilator vector space.

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: f = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")sage: f.annihilator(1) is None # needs sage.rings.polynomial.pboriTruesage: g = BooleanFunction(f.annihilator(3)) # needs sage.rings.polynomial.pborisage: set(fi*g(i) for i,fi in enumerate(f)) # needs sage.rings.polynomial.pbori{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 BooleanFunctionsage: 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 iscorrelation immune of order \(m\).

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

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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}\) elementsof 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: # needs sage.rings.polynomial.pborisage: from sage.crypto.boolean_function import BooleanFunctionsage: f = BooleanFunction([0,1,0,1,0,1,0,1])sage: f.derivative(1).algebraic_normal_form()1sage: u = [1,0,0]sage: f.derivative(u).algebraic_normal_form()1sage: v = vector(GF(2), u) # needs sage.modulessage: f.derivative(v).algebraic_normal_form() # needs sage.modules1sage: 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 ifthere 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(),has_linear_structure().

EXAMPLES:

sage: # needs sage.modulessage: from sage.crypto.boolean_function import BooleanFunctionsage: 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()2sage: 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 ofoutput ones need to change to obtain a linear function.

EXAMPLES:

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

nvariables()#

The number of variables of this function.

EXAMPLES:

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

resiliency_order()#

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

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

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

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunctionsage: 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 BooleanFunctionsage: 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: # needs sage.rings.polynomial.pborisage: from sage.crypto.boolean_function import BooleanFunctionsage: 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') # needs sage.rings.polynomial.pbori'00ab'sage: # needs sage.rings.polynomial.pborisage: H = '0abbacadabbacad0'sage: len(H)16sage: T = BooleanFunction(H).truth_table(format='hex')sage: T == HTruesage: H = H * 4sage: T = BooleanFunction(H).truth_table(format='hex')sage: T == HTruesage: H = H * 4sage: T = BooleanFunction(H).truth_table(format='hex')sage: T == HTruesage: len(T)256sage: 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 BooleanFunctionsage: R.<x> = GF(2^3,'a')[] # needs sage.rings.finite_ringssage: B = BooleanFunction(x^3) # needs sage.rings.finite_ringssage: B.walsh_hadamard_transform() # needs sage.rings.finite_rings(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 BooleanFunctionsage: B = BooleanFunction(3)sage: type(B.__iter__())<class '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_functionsage: B = random_boolean_function(9)sage: B.nvariables()9sage: 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 BooleanFunctionsage: B = BooleanFunction([0,1,1,0])sage: loads(dumps(B)) == B # indirect doctestTrue

Boolean functions - Cryptography (2024)

References