boolean_function

Trait BooleanFunctionImpl

Source 
pub trait BooleanFunctionImpl: Debug {

Show 39 methods    // Required methods
    fn variables_count(&self) -> usize;
    fn get_boolean_function_type(&self) -> BooleanFunctionType;
    fn is_balanced(&self) -> bool;
    fn compute_cellular_automata_rule(&self, input_bits: u32) -> bool;
    fn derivative(
        &self,
        direction: u32,
    ) -> Result<BooleanFunction, BooleanFunctionError>;
    fn is_linear(&self) -> bool;
    fn reverse(&self) -> BooleanFunction;
    fn algebraic_normal_form(&self) -> AnfPolynomial;
    fn annihilator(
        &self,
        max_degree: Option<usize>,
    ) -> Option<(BooleanFunction, usize, usize)>;
    fn get_1_local_neighbor(&self, position: u32) -> BooleanFunction;
    fn iter(&self) -> BooleanFunctionIterator ⓘ;
    fn printable_hex_truth_table(&self) -> String;
    fn biguint_truth_table(&self) -> BigUint;
    fn close_balanced_functions_iterator(
        &self,
    ) -> Result<CloseBalancedFunctionIterator, BooleanFunctionError>;

    // Provided methods
    fn get_max_input_value(&self) -> u32 { ... }
    fn walsh_hadamard_transform(&self, w: u32) -> i32 { ... }
    fn walsh_hadamard_values(&self) -> Vec<i32> { ... }
    fn absolute_walsh_hadamard_spectrum(&self) -> HashMap<u32, usize> { ... }
    fn walsh_fourier_transform(&self, w: u32) -> i32 { ... }
    fn walsh_fourier_values(&self) -> Vec<i32> { ... }
    fn auto_correlation_transform(&self, w: u32) -> i32 { ... }
    fn absolute_autocorrelation(&self) -> HashMap<u32, usize> { ... }
    fn absolute_indicator(&self) -> u32 { ... }
    fn algebraic_degree(&self) -> usize { ... }
    fn is_symmetric(&self) -> bool { ... }
    fn nonlinearity(&self) -> u32 { ... }
    fn is_bent(&self) -> bool { ... }
    fn is_near_bent(&self) -> bool { ... }
    fn algebraic_immunity(&self) -> usize { ... }
    fn is_plateaued(&self) -> bool { ... }
    fn sum_of_square_indicator(&self) -> usize { ... }
    fn has_linear_structure(&self) -> bool { ... }
    fn is_linear_structure(&self, value: u32) -> bool { ... }
    fn linear_structures(&self) -> Vec<u32> { ... }
    fn correlation_immunity(&self) -> usize { ... }
    fn resiliency_order(&self) -> Option<usize> { ... }
    fn support(&self) -> HashSet<u32> { ... }
    fn propagation_criterion(&self) -> usize { ... }
    fn try_u64_truth_table(&self) -> Option<u64> { ... }

}
Expand description

Trait for Boolean function implementations. This trait is implemented by SmallBooleanFunction and BigBooleanFunction.

You could use this trait via the BooleanFunction type, which encapsulates the BooleanFunctionImpl trait.

Required Methods§

Source

fn variables_count(&self) -> usize

Variable count of the Boolean function.

Source

fn get_boolean_function_type(&self) -> BooleanFunctionType

Internal type of the Boolean function abstraction:

Source

fn is_balanced(&self) -> bool

Returns true if the Boolean function is balanced, ie it has an equal number of 0 and 1 outputs.

Source

fn compute_cellular_automata_rule(&self, input_bits: u32) -> bool

Computes the value of the Boolean function for a given input, as a 32-bit unsigned integer.

This is equivalent of calling directly your Boolean function object as a function.

§Parameters
  • input_bits: The input value for which to compute the Boolean function value, the least significant bit being the first variable.
§Returns

The value of the Boolean function for the given input bits.

§Panics

If the input value is greater than the maximum input value, and the unsafe_disable_safety_checks feature is not enabled.

§Example
use boolean_function::BooleanFunction;
use boolean_function::BooleanFunctionImpl;

let boolean_function = BooleanFunction::from_hex_string_truth_table("abce1234").unwrap();
assert_eq!(boolean_function.compute_cellular_automata_rule(8), false);
assert_eq!(boolean_function(8), false); // directly as a function
Source

fn derivative( &self, direction: u32, ) -> Result<BooleanFunction, BooleanFunctionError>

Computes the derivative of the Boolean function for a given direction.

The derivative of a Boolean function $f$ in the direction $u$ is defined as:

$$\nabla_u f(x) = f(x) \oplus f(x \oplus u)$$

Where $\oplus$ is the XOR operation.

§Parameters
  • direction: The direction $u$ for which to compute the derivative.
§Returns

The derivative of the Boolean function in the given direction, or an error if the direction is greater than the maximum input value and the unsafe_disable_safety_checks feature is not enabled.

Source

fn is_linear(&self) -> bool

Returns true if the Boolean function is linear, ie its algebraic degree is 0 or 1.

Source

fn reverse(&self) -> BooleanFunction

Reverse the Boolean function, ie swap 0 and 1 outputs.

This is equivalent to the NOT operation, like !boolean_function.

§Returns

The reversed Boolean function.

Source

fn algebraic_normal_form(&self) -> AnfPolynomial

Returns the Algebraic Normal Form of the Boolean function, in the form of an AnfPolynomial.

We use the Bakoev’s algorithm to compute the ANF polynomial http://www.math.bas.bg/moiuser/OCRT2017/a3.pdf.

§Returns

The Algebraic Normal Form of the Boolean function.

§Example
// Wolfram's rule 30
use boolean_function::BooleanFunctionImpl;
use boolean_function::BooleanFunction;
let boolean_function = BooleanFunction::from_u64_truth_table(30, 3).unwrap();
let anf_polynomial = boolean_function.algebraic_normal_form();
// `*` denotes the AND operation, and `+` denotes the XOR operation
assert_eq!(anf_polynomial.to_string(), "x0*x1 + x0 + x1 + x2");
Source

fn annihilator( &self, max_degree: Option<usize>, ) -> Option<(BooleanFunction, usize, usize)>

Returns, if it exists, an annihilator function, its degree and the dimension of annihilator vector space.

The annihilator of a Boolean function $f$ is a non-null Boolean function $g$ such that:

$$f(x).g(x) = 0 \ \ \forall x \in \mathbb{F}_2^n$$

Special case: annihilator of zero function is constant one function, by convention.

§Parameters
  • max_degree: An optional maximum degree of the annihilator to search for. If set to None, the value is set to the variable count.
§Returns
  • None if no annihilator is found (this is the case for constant one function).
  • Some((annihilator, degree, dimension)) if an annihilator is found:
    • annihilator: The annihilator function.
    • degree: The degree of the returned annihilator function.
    • dimension: The dimension of the annihilator vector space.
Source

fn get_1_local_neighbor(&self, position: u32) -> BooleanFunction

Returns a 1-local neighbor of the Boolean function, at a specific position

A 1-local neighbor of a Boolean function $f$ at position $i$ is a Boolean function $f_i$ such that:

$$f_i(x) = \begin{cases} f(x) &\text{if } x \neq i \\ f(x) \oplus 1 &\text{if } x = i \end{cases}$$

$f_i$ is said to be connected to $f$.

§Parameters
  • position: The position $i$ at which to compute the 1-local neighbor.
§Returns

The 1-local neighbor of the Boolean function at the given position.

§Panics

If the position is greater than the maximum input value, and the unsafe_disable_safety_checks feature is not enabled.

Source

fn iter(&self) -> BooleanFunctionIterator ⓘ

Returns an iterator over the values of the Boolean function.

§Returns

An iterator over the values of the Boolean function.

§Example
// Wolfram's rule 30
use boolean_function::BooleanFunctionImpl;
use boolean_function::BooleanFunction;
let boolean_function = BooleanFunction::from_u64_truth_table(30, 3).unwrap();
let mut iterator = boolean_function.iter();
assert_eq!(iterator.next(), Some(false));
assert_eq!(iterator.next(), Some(true));
Source

fn printable_hex_truth_table(&self) -> String

Returns the truth table of the Boolean function as a hexadecimal string.

§Returns

The truth table of the Boolean function as a hexadecimal string.

§Example
// Wolfram's rule 30
use boolean_function::BooleanFunctionImpl;
use boolean_function::BooleanFunction;
let boolean_function = BooleanFunction::from_u64_truth_table(30, 3).unwrap();
assert_eq!(boolean_function.printable_hex_truth_table(), "1e");
Source

fn biguint_truth_table(&self) -> BigUint

Returns the truth table of the Boolean function as a BigUint.

§Returns

The truth table of the Boolean function as a BigUint.

Source

fn close_balanced_functions_iterator( &self, ) -> Result<CloseBalancedFunctionIterator, BooleanFunctionError>

Returns an iterator over the closest possible balanced Boolean functions.

“closest” means the minimum possible Hamming distance over the truth table.

This is particularly useful if you want to extract a set of balanced functions from a bent function. So that you can generate highly nonlinear balanced functions.

§Returns

An iterator over close balanced Boolean functions, or an error if the function is already balanced.

§Note

It is assumed that the function truth table is correctly sanitized, so be careful if you generated it with unsafe_disable_safety_checks feature activated.

§Example
use boolean_function::BooleanFunction;
 use crate::boolean_function::BooleanFunctionImpl;

let bent_function = BooleanFunction::from_hex_string_truth_table(
            "80329780469d0b85cd2ad63e1a6ba42adbd83c9a0c55e4e8c99f227b0ffc1418"
        ).unwrap();
let close_balanced_iterator = bent_function.close_balanced_functions_iterator();
assert!(close_balanced_iterator.is_ok());
let mut close_balanced_iterator = close_balanced_iterator.unwrap();
let highly_nonlinear_balanced_function = close_balanced_iterator.next().unwrap();
assert!(highly_nonlinear_balanced_function.is_balanced());
assert_eq!(highly_nonlinear_balanced_function.nonlinearity(), 112);

Provided Methods§

Source

fn get_max_input_value(&self) -> u32

Maximum input value for the Boolean function, as unsigned 32-bit integer.

This is equal to $2^n - 1$, where $n$ is the number of variables.

Source

fn walsh_hadamard_transform(&self, w: u32) -> i32

Computes the Walsh-Hadamard transform of the Boolean function for a given point.

The Walsh-Hadamard transform of a Boolean function $f$, for a given point $\omega$, is defined as:

$$W_f(\omega) = \sum_{x=0}^{2^n-1} (-1)^{f(x) \oplus \omega \cdot x}$$

Where $\oplus$ is the XOR operation, $\cdot$ is the AND operand product, and $2^n - 1$ is the maximum input value.

§Parameters
  • w: The point $\omega$ for which to compute the Walsh-Hadamard transform.
§Returns

The value of the Walsh-Hadamard transform for the given point.

§Panics

If the point is greater than the maximum input value, and the unsafe_disable_safety_checks feature is not enabled.

Source

fn walsh_hadamard_values(&self) -> Vec<i32>

Computes the Walsh-Hadamard values for all points.

§Returns

A vector containing the Walsh-Hadamard values for all points.

Source

fn absolute_walsh_hadamard_spectrum(&self) -> HashMap<u32, usize>

Computes the absolute Walsh-Hadamard spectrum of the Boolean function.

The absolute Walsh-Hadamard spectrum is the number of occurrences of each absolute value of the Walsh-Hadamard transform.

§Returns

A hashmap containing the absolute Walsh-Hadamard values as keys, and the number of occurrences as values.

Source

fn walsh_fourier_transform(&self, w: u32) -> i32

Computes the Walsh-Fourier transform of the Boolean function for a given point.

The Walsh-Fourier transform of a Boolean function $f$, for a given point $\omega$, is defined as:

$$F_f(\omega) = \sum_{x=0}^{2^n-1} f(x) \cdot (-1)^{\omega \cdot x}$$

Where $\cdot$ is the AND operand product, and $2^n - 1$ is the maximum input value.

§Parameters
  • w: The point $\omega$ for which to compute the Walsh-Fourier transform.
§Returns

The value of the Walsh-Fourier transform for the given point.

§Panics

If the point is greater than the maximum input value, and the unsafe_disable_safety_checks feature is not enabled.

Source

fn walsh_fourier_values(&self) -> Vec<i32>

Computes the Walsh-Fourier values for all points.

§Returns

A vector containing the Walsh-Fourier values for all points.

Source

fn auto_correlation_transform(&self, w: u32) -> i32

Computes the autocorrelation transform of the Boolean function for a given point. The autocorrelation transform of a Boolean function $f$, for a given point $\omega$, is defined as:

$$\Delta_f(\omega) = \sum_{x=0}^{2^n-1} (-1)^{f(x) \oplus f(x \oplus \omega)}$$

Where $\oplus$ is the XOR operation, and $2^n - 1$ is the maximum input value.

§Parameters
  • w: The point $\omega$ for which to compute the autocorrelation transform.
§Returns

The value of the autocorrelation transform for the given point.

§Panics

If the point is greater than the maximum input value, and the unsafe_disable_safety_checks feature is not enabled.

Source

fn absolute_autocorrelation(&self) -> HashMap<u32, usize>

Computes the absolute autocorrelation spectrum of the Boolean function.

The absolute autocorrelation spectrum is the number of occurrences of each absolute value of the autocorrelation transform.

§Returns

A hashmap containing the absolute autocorrelation values as keys, and the number of occurrences as values.

Source

fn absolute_indicator(&self) -> u32

Returns the absolute indicator of the Boolean function.

As defined here, the absolute indicator is the maximal absolute value of the auto-correlation transform for all points starting from 1 to the maximum input value $2^n - 1$, $n$ being the number of variables.

Source

fn algebraic_degree(&self) -> usize

Returns the algebraic degree of the Boolean function.

The algebraic degree of a Boolean function is the maximum degree of the AND monomials in its Algebraic Normal Form.

The degree of a monomial is the number of variables in the monomial.

§Returns

The algebraic degree of the Boolean function.

Source

fn is_symmetric(&self) -> bool

Returns true if the Boolean function is symmetric.

A Boolean function is symmetric if for all inputs $x$, the value of the function is the same as the value of the function for the bitwise reversed input.

It means that the output depends only on the Hamming weight of the input.

Source

fn nonlinearity(&self) -> u32

Returns the nonlinearity of the Boolean function.

Nonlinearity is a measure of how far the Boolean function is from being linear. It’s defined as the Hamming distance between the Boolean function and the closest linear function, or the minimum number of output bits that must be changed to make the function linear.

§Returns

The nonlinearity of the Boolean function, as an unsigned 32-bit integer.

Source

fn is_bent(&self) -> bool

Returns true if the Boolean function is bent, meaning maximally nonlinear, or perfectly nonlinear.

Only functions with an even number of variables can be bent.

The maximum possible nonlinearity for a Boolean function with $n$ variables is $\frac{2^n - 2^{\frac{n}{2}}}{2}$.

A bent function has all its derivative balanced.

The Rothaus theorem states that if an $n$-variable Boolean function $f$ is bent, then $deg(f) <= \frac{n}{2}$.

A bent function cannot be balanced.

Source

fn is_near_bent(&self) -> bool

Returns true if the Boolean function is near-bent.

A $n$-variable Boolean function is said to be near-bent if $n$ is odd, and its Walsh-Hamamard spectrum contains all and only the 3 values $\{0, \pm 2^{\frac{n+1}{2}}\}$.

Source

fn algebraic_immunity(&self) -> usize

Returns the algebraic immunity of the Boolean function.

The algebraic immunity of a Boolean function is defined as the minimum degree of an annihilator of the function.

§Returns

The algebraic immunity of the Boolean function, or 0 if the function has no annihilator.

Source

fn is_plateaued(&self) -> bool

Returns true if the Boolean function is plateaued.

A Boolean function is plateaued if its Walsh-Hadamard spectrum has at most three values: 0, $\lambda$ and $-\lambda$, where $\lambda \in \mathbb{N}^*$.

Source

fn sum_of_square_indicator(&self) -> usize

Returns the sum of the square of the indicator of the Boolean function.

The sum of the square of the indicator for a $n$-variable Boolean function $f$ is defined as:

$$\sum_{w=0}^{2^n-1} \Delta_f(w)^2$$

Where $\Delta_f(w)$ is the autocorrelation transform of the function for a given point $w$.

§Returns

The sum of the square of the indicator of the Boolean function.

Source

fn has_linear_structure(&self) -> bool

Returns true if the Boolean function has a linear structure.

A $n$-variable boolean function has a linear structure if $\exists a \in \mathbb{F}_2^n$ such that $x \longmapsto f(x) \oplus f(x \oplus a)$ is a constant function.

https://www.sciencedirect.com/topics/mathematics/linear-structure

Source

fn is_linear_structure(&self, value: u32) -> bool

Checks if the parameter is a linear structure of the Boolean function.

A vector $a \in \mathbb{F}_2^n$ is a linear structure of a $n$-variable Boolean function $f$ if the function $x \longmapsto f(x) \oplus f(x \oplus a)$ is a constant function.

§Parameters
  • value: The value to check if it is a linear structure.
§Returns

true if the value is a linear structure of the Boolean function, false otherwise.

§Panics

The function panics if the value is greater than the function maximum input value and the unsafe_disable_safety_checks feature is not enabled.

Source

fn linear_structures(&self) -> Vec<u32>

List of all linear structures of the Boolean function.

A vector $a \in \mathbb{F}_2^n$ is a linear structure of a $n$-variable Boolean function $f$ if the function $x \longmapsto f(x) \oplus f(x \oplus a)$ is a constant function.

§Returns

A vector containing all linear structures of the Boolean function.

Source

fn correlation_immunity(&self) -> usize

Returns the correlation immunity order of the Boolean function (calculated using Xiao Massey theorem).

A Boolean function is said to be correlation immune of order $k$ if the output of the function is statistically independent of any subset of maximum $k$ input bits.

As shown by Siegenthaler, a $n$-variable Boolean function which is correlation immune of order $k$ has a degree $d \leq n - m$. https://iacr.org/archive/asiacrypt2002/25010483/25010483.pdf

§Returns

The correlation immunity order of the Boolean function.

Source

fn resiliency_order(&self) -> Option<usize>

Returns the resiliency order of the Boolean function.

A boolean function is said to be resilient of order $k$ if it is balanced and correlation immune of order $k$.

§Returns

The resiliency order of the Boolean function, or None if the function is not balanced.

Source

fn support(&self) -> HashSet<u32>

Returns the support of the Boolean function.

The support of a $n$-variable Boolean function is the set of all inputs $x \in \mathbb{F}_2^n$ such that $f(x) = 1$.

§Returns

The support of the Boolean function, as a set of unsigned 32-bit integers.

Source

fn propagation_criterion(&self) -> usize

Returns the maximum propagation criterion of the Boolean function.

A $n$-variable Boolean function $f$ satisfies propagation criterion at order $k$ if its output changes with a probability of $\frac{1}{2}$ when changing the value of any subset of $i$ variables, $\forall i \in \llbracket 1, k \rrbracket$

§Returns

The maximum propagation criterion of the Boolean function.

Source

fn try_u64_truth_table(&self) -> Option<u64>

Returns the truth table of the Boolean function as an unsigned 64-bit integer, if it fits (meaning the Boolean function has 6 or less input variables).

§Returns

The truth table of the Boolean function as an unsigned 64-bit integer, or None if the truth table is too big to fit in an u64.

Implementors§