Enum BooleanFunction

pub enum BooleanFunction {
    Small(SmallBooleanFunction),
    Big(BigBooleanFunction),
}

This type is used to store a boolean function with any number of variables.

It abstracts The SmallBooleanFunction and BigBooleanFunction types, by encapsulating the BooleanFunctionImpl trait.

Please refer to the BooleanFunctionImpl trait for more information.

Variants

Small(SmallBooleanFunction)

Struct representing a boolean function with a small truth table.

Big(BigBooleanFunction)

Struct representing a boolean function with a big truth table.

Implementations

impl BooleanFunction

pub fn from_hex_string_truth_table( hex_truth_table: &str, ) -> Result<Self, BooleanFunctionError>

Creates a new BooleanFunction from a hexadecimal string representing the truth table.

The hexadecimal string must have a length of $\frac{2^n}{4}$ where $n$ is the number of variables of the Boolean function (meaning this function only accepts Boolean function with 2 or more input variables).

Parameters

• hex_truth_table: The hexadecimal string representing the truth table of the Boolean function.

Returns

The Boolean function created from the hexadecimal string, or an error if the string cannot be parsed as a hexadecimal truth table of a Boolean function.

Example

use boolean_function::BooleanFunction;
let boolean_function = BooleanFunction::from_hex_string_truth_table("0969817CC5893BA6")
    .unwrap();

pub fn from_reverse_walsh_hadamard_transform( walsh_hadamard_values: &[i32], ) -> Result<Self, BooleanFunctionError>

Creates a new BooleanFunction from a list of integers representing the Walsh-Hadamard transform, by applying a reverse Walsh-Hadamard transform.

The Walsh-Hadamard values list for an $n$-variable Boolean function must have a length of $2^n$. The function returns a SmallBooleanFunction if the given Walsh-Hadamard values list has a length of 64 or less, and a BigBooleanFunction otherwise. It won’t check that the values are consistent, if not the function will return the closest Boolean function possible.

Parameters

• walsh_hadamard_values: The list of integers representing the Walsh-Hadamard transform of the Boolean function.

Returns

The Boolean function created from the Walsh-Hadamard values list, or an error if the list length is less than 4, or not a power of 2.

pub fn from_reverse_walsh_fourier_transform( walsh_fourier_values: &[i32], ) -> Result<Self, BooleanFunctionError>

Creates a new BooleanFunction from a list of integers representing the Walsh-Fourier transform, by applying a reverse Walsh-Fourier transform.

The Walsh-Fourier values list for an $n$-variable Boolean function must have a length of $2^n$. The function returns a SmallBooleanFunction if the given Walsh-Fourier values list has a length of 64 or less, and a BigBooleanFunction otherwise. It won’t check that the values are consistent, if not the function will return the closest Boolean function possible.

Parameters

• walsh_fourier_values: The list of integers representing the Walsh-Fourier transform of the Boolean function.

Returns

The Boolean function created from the Walsh-Fourier values list, or an error if the list length is less than 4, or not a power of 2.

pub fn from_u64_truth_table( truth_table: u64, num_variables: usize, ) -> Result<Self, BooleanFunctionError>

Creates a new BooleanFunction from an u64 representing the truth table (meaning the Boolean function has 6 or less input variables).

The wrapped Boolean function is a SmallBooleanFunction.

Parameters

• truth_table: The u64 truth table of the Boolean function, where the lower bit represents the output of the Boolean function for the input 0.
• num_variables: The number of input variables of the Boolean function.

Returns

The Boolean function created from the u64 truth table.

Returns an error if:

• The given input variables count is greater than 6.
• The given truth table is too big for the given input variables count and the unsafe_disable_safety_checks feature is not enabled.

pub fn from_biguint_truth_table( truth_table: &BigUint, num_variables: usize, ) -> Result<Self, BooleanFunctionError>

Creates a new BooleanFunction from a BigUint representing the truth table.

The wrapped Boolean function is a BigBooleanFunction if the variables count is greater than 6, and a SmallBooleanFunction otherwise.

Parameters

• truth_table: The BigUint truth table of the Boolean function, where the lower bit represents the output of the Boolean function for the input 0.
• num_variables: The number of input variables of the Boolean function.

Returns

The Boolean function created from the BigUint truth table.

Returns an error if:

• The given input variables count is greater than 31, and the unsafe_disable_safety_checks feature is not enabled.
• The given truth table is too big for the given input variables count and the unsafe_disable_safety_checks feature is not enabled.

pub fn from_anf_polynomial_str( anf_polynomial: &str, num_variables: usize, ) -> Result<Self, BooleanFunctionError>

Computes Boolean Function from string ANF representation

The ANF string representation must be in exact form “x0*x2*x3 + x2*x3 + x1 + 1”.

X’s index starts at 0, meaning the maximum index is variable count - 1.

Parameters:

• anf_polynomial: The string representation of the ANF form
• num_variables: Variable count of the polynomial

Returns

The BooleanFunction corresponding to the ANF string representation, or an error if the input string doesn’t respect the format and unsafe_disable_safety_checks feature is not activated.

Example

use boolean_function::{BooleanFunction, BooleanFunctionImpl};

let rule_30 = BooleanFunction::from_anf_polynomial_str("x0*x1 + x0 + x1 + x2", 3).unwrap();
assert_eq!(rule_30.printable_hex_truth_table(), "1e");

pub fn from_anf_polynomial(anf_polynomial: &AnfPolynomial) -> Self

Computes Boolean Function from ANF polynomial

Parameters:

• anf_polynomial: The polynomial in Algebraic Normal Form

Returns

The BooleanFunction corresponding to the ANF polynomial

Trait Implementations

impl BitXor for BooleanFunction

XOR operator for Boolean functions truth tables.

Panics

If the Boolean functions have different number of variables, and the unsafe_disable_safety_checks feature is not enabled.

type Output = BooleanFunction

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Self) -> Self::Output

Performs the ^ operation.

impl BitXorAssign for BooleanFunction

In-place XOR operator for Boolean functions truth tables.

Panics

If the Boolean functions have different number of variables, and the unsafe_disable_safety_checks feature is not enabled.

fn bitxor_assign(&mut self, rhs: Self)

Performs the ^= operation.

impl BooleanFunctionImpl for BooleanFunction

fn variables_count(&self) -> usize

Variable count of the Boolean function.

fn get_boolean_function_type(&self) -> BooleanFunctionType

Internal type of the Boolean function abstraction:

• BooleanFunctionType::Big for BigBooleanFunction

• BooleanFunctionType::Small for SmallBooleanFunction

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.

fn is_balanced(&self) -> bool

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

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

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

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.

fn walsh_hadamard_transform(&self, __enum_dispatch_arg_0: 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.

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.

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.

fn walsh_fourier_transform(&self, __enum_dispatch_arg_0: 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.

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.

fn auto_correlation_transform(&self, __enum_dispatch_arg_0: 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.

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.

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.

fn derivative( &self, __enum_dispatch_arg_0: 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.

fn is_linear(&self) -> bool

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

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.

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");

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.

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.

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.

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.

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}}\}$.

fn annihilator( &self, __enum_dispatch_arg_0: 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: The maximum degree of the annihilator to search for.

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.

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.

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}^*$.

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.

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

fn is_linear_structure(&self, __enum_dispatch_arg_0: 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.

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.

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.

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.

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.

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.

fn get_1_local_neighbor(&self, __enum_dispatch_arg_0: 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.

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));

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");

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.

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.

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);

impl Clone for BooleanFunction

fn clone(&self) -> BooleanFunction

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BooleanFunction

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<BigBooleanFunction> for BooleanFunction

fn from(v: BigBooleanFunction) -> BooleanFunction

Converts to this type from the input type.

impl From<SmallBooleanFunction> for BooleanFunction

fn from(v: SmallBooleanFunction) -> BooleanFunction

Converts to this type from the input type.

impl Not for BooleanFunction

NOT operator for Boolean functions.

This is equivalent to the BooleanFunctionImpl::reverse operation: it reverses each output of the Boolean function.

type Output = BooleanFunction

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl PartialEq for BooleanFunction

fn eq(&self, other: &BooleanFunction) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl TryInto<BigBooleanFunction> for BooleanFunction

type Error = &'static str

The type returned in the event of a conversion error.

fn try_into( self, ) -> Result<BigBooleanFunction, <Self as TryInto<BigBooleanFunction>>::Error>

Performs the conversion.

impl TryInto<SmallBooleanFunction> for BooleanFunction

type Error = &'static str

The type returned in the event of a conversion error.

fn try_into( self, ) -> Result<SmallBooleanFunction, <Self as TryInto<SmallBooleanFunction>>::Error>

Performs the conversion.

impl Eq for BooleanFunction

impl StructuralPartialEq for BooleanFunction