Bent Boolean functions

The bent_function module defines the BentFunction class, which represents a bent Boolean function and some of its properties.

AUTHORS:

Paul Leopardi (2016-09-25): initial version

EXAMPLES:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: bf = BooleanFunction([0,1,0,0])
sage: bf.algebraic_normal_form()
x0*x1 + x0
sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction(bf)
sage: type(bentf)
<class 'boolean_cayley_graphs.bent_function.BentFunction'>
sage: bentf.algebraic_normal_form()
x0*x1 + x0

REFERENCES:

class boolean_cayley_graphs.bent_function.BentFunction[source]

Bases: boolean_cayley_graphs.boolean_function_improved.BooleanFunctionImproved

A bent Boolean function, with methods corresponding to some of its properties.

The class inherits from BooleanFunctionImproved and is initialized in the same way as BooleanFunction. Since BooleanFunctionImproved inherits from Saveable, so does BentFunction.

EXAMPLES:

sage: import os
sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1])
sage: bentf.algebraic_normal_form()
x0*x1
sage: d = tmp_dir()
sage: bentf.save_mangled('example', dir=d)
sage: ex = BentFunction.load_mangled('example', dir=d)
sage: type(ex)
<class 'boolean_cayley_graphs.bent_function.BentFunction'>
sage: ex is bentf
False
sage: ex == bentf
True
sage: BentFunction.remove_mangled('example', dir=d)
sage: os.rmdir(d)

TESTS:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: bf = BentFunction([0,1,0,0])
sage: print(bf)
Boolean function with 2 variables

sage: from sage.crypto.boolean_function import BooleanFunction
sage: bf = BentFunction([0,1,0,0])
sage: latex(bf)
\text{\texttt{Boolean{ }function{ }with{ }2{ }variables}}

is_partial_spread_minus(certify=False)[source]

Determine if a bent function is in the partial spread (-) class.

Partial spread (-) is Dillon’s \(\mathcal{PS}^{(-)}\) class [Dil1974].

INPUT:

self – the current object.
certify – boolean (default: False):

OUTPUT:

If certify is False, then return True if the bent function represented by self is in \(\mathcal{PS}^{(-)}\), otherwise return False. If certify is True then return two values, where the first is True or False as above, and if the first value is True, the second value is a list of intersections between maximal cliques, otherwie the second value is an empty list.

EXAMPLES:

sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0])
sage: bentf.is_bent()
True
sage: bentf.is_partial_spread_minus()
True
sage: bentf.is_partial_spread_minus(certify=True)
(True, [{7, 11, 12}, {3, 13, 14}])

linear_code_graph()[source]

Return the graph of the linear code corresponding to the bent function.

INPUT:

self – the current object.

OUTPUT:

The graph of the linear code corresponding to self. This is a strongly regular graph [Car2010], [Del1972], [Din2015].

EXAMPLES:

sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0])
sage: lcg = bentf.linear_code_graph()
sage: type(lcg)
<class 'sage.graphs.graph.Graph'>
sage: lcg.is_strongly_regular(parameters=True)
(16, 6, 2, 2)

REFERENCES:

sdp_design_matrix()[source]

Return the incidence matrix of the SDP design of the bent function.

This method returns the incidence matrix of the design of type \(R(\mathtt{self})\), as described by Dillon and Schatz [DS1987]. This is a design with the symmetric difference property [Kan1975].

INPUT:

self – the current object.

OUTPUT:

The incidence matrix of the SDP design corresponding to self.

EXAMPLES:

sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0])
sage: sdp = bentf.sdp_design_matrix()
sage: print(sdp)
[0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0]
[0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1]
[0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1]
[1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1]
[0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1]
[0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0]
[1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0]
[0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1]
[0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0]
[0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0]
[1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0]
[1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1]
[1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0]
[1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0]
[0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0]
sage: from sage.combinat.designs.incidence_structures import IncidenceStructure
sage: sdp_design = IncidenceStructure(sdp)
sage: sdp_design.is_t_design(return_parameters=True)
(True, (2, 16, 6, 2))

REFERENCES:

walsh_hadamard_dual()[source]

Return the Walsh Hadamard dual of the bent function.

This method returns a BentFunction based on the Walsh Hadamard transform of self. Since self is a bent function, the returned BentFunction` is well-defined and is bent, being the *dual* bent function [Hou1999]_ or *Fourier transform* of ``self [Rot1976].

INPUT:

self – the current object.

OUTPUT:

An object of class BentFunction, being the dual of self.

EXAMPLES:

sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0])
sage: dual_bentf = bentf.walsh_hadamard_dual()
sage: type(dual_bentf)
<class 'boolean_cayley_graphs.bent_function.BentFunction'>
sage: dual_bentf.is_bent()
True
sage: dual_bentf.algebraic_normal_form()
x0*x1 + x2*x3

Note

Versions of Sage before 8.2 had an incorrect sign in BooleanFunction.walsh_hadamard_transform(self). See [Sage trac ticket #23931](https://trac.sagemath.org/ticket/23931) Previous versions of this method had 1 + x // scale to compensate for an incorrect sign in BooleanFunction.walsh_hadamard_transform(self). [Since this has now been fixed in Sage 8.2](https://trac.sagemath.org/ticket/23931) this is now changed to 1 - x // scale.

weight_class()[source]

Return the weight class of the bent function.

INPUT:

self – the current object.

OUTPUT:

The value 0 or 1, being the weight class of self.

EXAMPLES:

sage: from boolean_cayley_graphs.bent_function import BentFunction
sage: bentf = BentFunction([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0])
sage: bentf.weight_class()
0