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:
Bases: sage.structure.sage_object.SageObject
This module implements Boolean functions represented as a truth table.
We can construct a Boolean Function from either:
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
Return the absolut indicator of the function. Ths is the maximal absolut value of the autocorrelation.
EXAMPLES:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: B.absolut_indicator()
32
Return the absolute autocorrelation of the function.
EXAMPLES:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: sorted([ _ for _ in B.absolute_autocorrelation().iteritems() ])
[(0, 33), (8, 58), (16, 28), (24, 6), (32, 2), (128, 1)]
Return the absolute Walsh spectrum fo the function.
EXAMPLES:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
sage: sorted([_ for _ in B.absolute_walsh_spectrum().iteritems() ])
[(0, 64), (16, 64)]
sage: B = BooleanFunction("0113077C165E76A8")
sage: B.absolute_walsh_spectrum()
{8: 64}
Returns the algebraic immunity of the Boolean function. This is the smallest
integer such that there exists a non trivial annihilator for
or
.
INPUT:
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
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]
Return (if it exists) an annihilator of the boolean function of
degree at most , that is a Boolean polynomial
such that
INPUT:
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) ])
set([0])
Return the autocorrelation fo the function, defined by
EXAMPLES:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("03")
sage: B.autocorrelation()
(8, 8, 0, 0, 0, 0, 0, 0)
Return the maximum value such that the function is
correlation immune of order
.
A Boolean function is said to be correlation immune of order
, 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
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
Return True if the function is bent.
EXAMPLE:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("0113077C165E76A8")
sage: B.is_bent()
True
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
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.
EXAMPLE:
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
The number of variables of this function.
EXAMPLE:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: BooleanFunction(4).nvariables()
4
Return the maximum value such that the function is
resilient of order
.
A Boolean function is said to be resilient of order if it
is balanced and correlation immune of order
.
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
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
The truth table of the Boolean function.
INPUT: a string representing the desired format, can be either
EXAMPLE:
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: B.truth_table(format='oct')
Traceback (most recent call last):
...
ValueError: unknown output format
Compute the Walsh Hadamard transform of the function
.
EXAMPLE:
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)
Bases: object
Iterator through the values of a Boolean function.
EXAMPLE:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction(3)
sage: type(B.__iter__())
<type 'sage.crypto.boolean_function.BooleanFunctionIterator'>
x.next() -> the next value, or raise StopIteration
Returns a random Boolean function with variables.
EXAMPLE:
sage: from sage.crypto.boolean_function import random_boolean_function
sage: B = random_boolean_function(9)
sage: B.nvariables()
9
sage: B.nonlinearity()
217 # 32-bit
222 # 64-bit
Specific function to unpickle Boolean functions.
EXAMPLE:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction([0,1,1,0])
sage: loads(dumps(B)) == B # indirect doctest
True