# Difference between revisions of "Boolean Functions"

(→Algebraic normal form) |
m (→The Nonlinearity) |
||

(16 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

=Introduction= | =Introduction= | ||

− | Let < | + | Let 𝔽<sub>2</sub><sup>𝑛</sup> be the vector space of dimension 𝑛 over the finite field with two elements. |

− | The vector space can also be endowed with the structure of the field, the finite field with < | + | The vector space can also be endowed with the structure of the field, the finite field with 2<sup>𝑛</sup> elements, 𝔽<sub>2<sup>𝑛</sup></sub>. |

− | A function <math>f : \mathbb{F}_2^n\rightarrow\mathbb{F}</math> is called a <i>Boolean function</i> in dimenstion | + | A function <math>f : \mathbb{F}_2^n\rightarrow\mathbb{F}</math> is called a <i>Boolean function</i> in dimenstion 𝑛 (or <i>𝑛-variable Boolean function</i>). |

Given <math>x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n</math>, the support of <i>x</i> is the set <math>supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}</math>. | Given <math>x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n</math>, the support of <i>x</i> is the set <math>supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}</math>. | ||

− | The Hamming weight of | + | The Hamming weight of 𝑥 is the size of its support (<math>w_H(x)=|supp_x|</math>). |

− | Similarly the Hamming weight of a Boolean function | + | Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>. |

− | The Hamming distance of two functions < | + | The Hamming distance of two functions 𝑓,𝑔 (𝖽<sub>𝐻</sub>(𝑓,𝑔)) is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>. |

=Representation of a Boolean function= | =Representation of a Boolean function= | ||

Line 14: | Line 14: | ||

There exist different ways to represent a Boolean function. | There exist different ways to represent a Boolean function. | ||

A simple, but often not efficient, one is by its truth-table. | A simple, but often not efficient, one is by its truth-table. | ||

− | For example consider the following truth-table for a 3-variable Boolean function | + | For example consider the following truth-table for a 3-variable Boolean function 𝑓. |

<center> <table style="width:14%"> | <center> <table style="width:14%"> | ||

<tr> | <tr> | ||

− | <th colspan="3"> | + | <th colspan="3">𝑥</th> |

− | <th> | + | <th>𝑓(𝑥)</th> |

</tr> | </tr> | ||

<tr> | <tr> | ||

Line 47: | Line 47: | ||

==Algebraic normal form== | ==Algebraic normal form== | ||

− | An | + | An 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽<sub>2</sub> of the form |

<center><math> f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). </math></center> | <center><math> f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). </math></center> | ||

− | Such representation is unique and it is the <em> algebraic normal form</em> of | + | Such representation is unique and it is the <em> algebraic normal form</em> of 𝑓 (shortly ANF). |

− | The degree of the ANF is called the <em> algebraic degree</em> of the function, | + | The degree of the ANF is called the <em> algebraic degree</em> of the function, 𝑑°𝑓=max { |𝐼| : 𝑎<sub>𝐼</sub>≠0 }. |

+ | |||

+ | Based on the algebraic degree we called 𝑓 | ||

+ | * <em>affine</em> if 𝑑°𝑓=1, <em>linear</em> if 𝑑°𝑓=1 and 𝑓(𝟎)=0; | ||

+ | * <em>quadratic</em> if 𝑑°𝑓=2. | ||

+ | Affine functions are of the form 𝑓(𝑥)= 𝑢⋅𝑥+𝑒, for 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> and 𝑒∈𝔽<sub>2</sub> | ||

==Trace representation== | ==Trace representation== | ||

− | + | We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1). | |

+ | The map admits a uinque representation as a univariate polynomial of the form | ||

+ | <center><math> f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n}, | ||

+ | </math></center> | ||

+ | with Γ<sub>𝑛</sub> set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2<sup>𝑛</sup>-1), 𝘰(𝘫) size of the cyclotomic coset containing 𝘫, 𝘈<sub>𝘫</sub> ∈ 𝔽<sub>2<sup>𝘰(𝘫)</sup></sub>, Tr<sub>𝔽<sub>2<sup>𝘰(𝘫)</sup>/𝔽<sub>2</sub></sub></sub> trace function from 𝔽<sub>2<sup>𝘰(𝘫)</sup> to 𝔽<sub>2</sub>. | ||

+ | |||

+ | Such representation is also called the univariate representation . | ||

+ | |||

+ | 𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math> where 𝘗 is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>≠0. | ||

+ | |||

+ | When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n | A_j\ne0}w_2(j)</math>, where 𝓌<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗. | ||

+ | |||

+ | =On the weight of a Boolean function= | ||

+ | For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied. | ||

+ | * If 𝑑°𝑓=1 then 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>. | ||

+ | * If 𝑑°𝑓=2 then 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup> or 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>±2<sup>𝑛-1-ℎ</sup>, with 0≤ℎ≤𝑛/2. | ||

+ | * If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌<sub>𝐻</sub>(𝑓)≥2<sup>𝑛-𝑟</sup>. | ||

+ | * 𝓌<sub>𝐻</sub>(𝑓) is odd if and only if 𝑑°𝑓=𝑛. | ||

+ | |||

+ | =The Walsh transform= | ||

+ | The <i>Walsh transform</i> 𝑊<sub>𝑓</sub> is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)<sup>𝑓(𝑥)</sup>. | ||

+ | With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> 𝑥·𝑦, the value of 𝑊<sub>𝑓</sub> at 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers) | ||

+ | <center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center> | ||

+ | The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}=\{ u\in\mathbb{F}_2^n : W_f(u)=1 \}</math> is the <i>Walsh support</i> of 𝑓. | ||

+ | |||

+ | ==Properties of the Walsh transform== | ||

+ | For every 𝑛-variable Boolean function 𝑓 we have the following relations. | ||

+ | * Inverse Walsh transform: for any element 𝑥 of 𝔽<sub>2</sub><sup>𝑛</sup> we have <center><math> \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)};</math></center> | ||

+ | * Parseval's relation: <center><math>\sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n};</math></center> | ||

+ | * Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements 𝑎,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = |E^\perp|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center> for 𝐸<sup>⟂</sup> the orthogonal subspace of 𝐸,{𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> : 𝑢·𝑥=0, for all 𝑥∈𝐸}. | ||

+ | |||

+ | =Equivalences of Boolean functions= | ||

+ | Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>affine equivalent</i> if there exists a linear automorphism 𝐿 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎).</center> | ||

+ | |||

+ | Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center> | ||

+ | A parameter that is preserved by an equivalence relation is called <i>invariant</i>. | ||

+ | |||

+ | * The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence. | ||

+ | * If 𝑓,𝑔 are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>. | ||

+ | |||

+ | =Properties important for cryptographic applications= | ||

+ | |||

+ | ==Balanced functions== | ||

+ | An 𝑛-variable Boolean function 𝑓 is called <em>balanced</em> if 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>, so its output is uniformly distributed. | ||

+ | Such functions cannot have maximal degree. | ||

+ | Most cryptographic applications use balanced Boolean functions. | ||

+ | |||

+ | ==The Nonlinearity== | ||

+ | The <em>nonlinearity</em> of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called 𝒜 the set of all affine 𝑛-variable functions, | ||

+ | <center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center> | ||

+ | |||

+ | * For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}|W_f(u)|</math>. | ||

+ | * From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>. | ||

+ | * A function achieving the covering radius bound with equality is called [[Bent Boolean Functions| bent]] (𝑛 is an even integer and the function is not balanced). | ||

+ | * 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>. | ||

+ | * 𝑓 is bent if and only if for any nonzero element 𝑎 the Boolean function 𝐷<sub>𝑎</sub>𝑓(𝑥)=𝑓(𝑥+𝑎)+𝑓(𝑥) is balanced. | ||

+ | |||

+ | ==Correlation-immunity order== | ||

+ | A Boolean function 𝑓 is <em>𝑚-th order correlation-immune</em> if the probability distribution of the output is unaltered when any 𝑚 input variables are fixed. | ||

+ | Balanced 𝑚-th order correlation-immune functions are called <em>𝑚-resilient</em>. | ||

+ | |||

+ | Given 𝑓 a 𝑛-variable function with correlation-immunity of order 𝑚 then <center>𝑚+𝑑°𝑓≤𝑛.</center> | ||

+ | If 𝑓 is also balanced, then <center>𝑚+𝑑°𝑓≤𝑛-1.</center> |

## Latest revision as of 15:39, 25 October 2019

## Contents

# Introduction

Let 𝔽_{2}^{𝑛} be the vector space of dimension 𝑛 over the finite field with two elements.
The vector space can also be endowed with the structure of the field, the finite field with 2^{𝑛} elements, 𝔽_{2𝑛}.
A function is called a *Boolean function* in dimenstion 𝑛 (or *𝑛-variable Boolean function*).

Given , the support of *x* is the set .
The Hamming weight of 𝑥 is the size of its support ().
Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set .
The Hamming distance of two functions 𝑓,𝑔 (𝖽_{𝐻}(𝑓,𝑔)) is the size of the set .

# Representation of a Boolean function

There exist different ways to represent a Boolean function. A simple, but often not efficient, one is by its truth-table. For example consider the following truth-table for a 3-variable Boolean function 𝑓.

𝑥 | 𝑓(𝑥) | ||
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 |

0 | 1 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

1 | 1 | 0 | 0 |

1 | 1 | 1 | 1 |

## Algebraic normal form

An 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽_{2} of the form

Such representation is unique and it is the * algebraic normal form* of 𝑓 (shortly ANF).

The degree of the ANF is called the * algebraic degree* of the function, 𝑑°𝑓=max { |𝐼| : 𝑎_{𝐼}≠0 }.

Based on the algebraic degree we called 𝑓

*affine*if 𝑑°𝑓=1,*linear*if 𝑑°𝑓=1 and 𝑓(𝟎)=0;*quadratic*if 𝑑°𝑓=2.

Affine functions are of the form 𝑓(𝑥)= 𝑢⋅𝑥+𝑒, for 𝑢∈𝔽_{2}^{𝑛} and 𝑒∈𝔽_{2}

## Trace representation

We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1). The map admits a uinque representation as a univariate polynomial of the form

with Γ_{𝑛} set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2^{𝑛}-1), 𝘰(𝘫) size of the cyclotomic coset containing 𝘫, 𝘈_{𝘫} ∈ 𝔽_{2𝘰(𝘫)}, Tr_{𝔽2𝘰(𝘫)/𝔽2} trace function from 𝔽_{2𝘰(𝘫) to 𝔽2.
}

Such representation is also called the univariate representation .

𝑓 can also be simply presented in the form where 𝘗 is a polynomial over the finite field F_{2𝑛} but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈_{𝘫}≠0.

When we consider the trace representation of of a function, then the algebraic degree is given by , where 𝓌_{2}(𝑗) is the Hamming weight of the binary expansion of 𝑗.

# On the weight of a Boolean function

For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied.

- If 𝑑°𝑓=1 then 𝓌
_{𝐻}(𝑓)=2^{𝑛-1}. - If 𝑑°𝑓=2 then 𝓌
_{𝐻}(𝑓)=2^{𝑛-1}or 𝓌_{𝐻}(𝑓)=2^{𝑛-1}±2^{𝑛-1-ℎ}, with 0≤ℎ≤𝑛/2. - If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌
_{𝐻}(𝑓)≥2^{𝑛-𝑟}. - 𝓌
_{𝐻}(𝑓) is odd if and only if 𝑑°𝑓=𝑛.

# The Walsh transform

The *Walsh transform* 𝑊_{𝑓} is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)^{𝑓(𝑥)}.
With an innner product in 𝔽_{2}^{𝑛} 𝑥·𝑦, the value of 𝑊_{𝑓} at 𝑢∈𝔽_{2}^{𝑛} is the following sum (over the integers)

The set is the *Walsh support* of 𝑓.

## Properties of the Walsh transform

For every 𝑛-variable Boolean function 𝑓 we have the following relations.

- Inverse Walsh transform: for any element 𝑥 of 𝔽
_{2}^{𝑛}we have - Parseval's relation:
- Poisson summation formula: for any vector subspace 𝐸 of 𝔽
_{2}^{𝑛}and for any elements 𝑎,𝑏 in 𝔽_{2}^{𝑛}for 𝐸 ^{⟂}the orthogonal subspace of 𝐸,{𝑢∈𝔽_{2}^{𝑛}: 𝑢·𝑥=0, for all 𝑥∈𝐸}.

# Equivalences of Boolean functions

Two 𝑛-variable Boolean functions 𝑓,𝑔 are called *affine equivalent* if there exists a linear automorphism 𝐿 and a vecor 𝑎 such that

Two 𝑛-variable Boolean functions 𝑓,𝑔 are called *extended-affine equivalent* (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that

A parameter that is preserved by an equivalence relation is called *invariant*.

- The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
- If 𝑓,𝑔 are affine equivalent, then .

# Properties important for cryptographic applications

## Balanced functions

An 𝑛-variable Boolean function 𝑓 is called *balanced* if 𝓌_{𝐻}(𝑓)=2^{𝑛-1}, so its output is uniformly distributed.
Such functions cannot have maximal degree.
Most cryptographic applications use balanced Boolean functions.

## The Nonlinearity

The *nonlinearity* of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called 𝒜 the set of all affine 𝑛-variable functions,

- For every 𝑓 we have .
- From Parseval relation we obtain the
*covering radius bound*. - A function achieving the covering radius bound with equality is called bent (𝑛 is an even integer and the function is not balanced).
- 𝑓 is bent if and only if 𝑊
_{𝑓}(𝑢)=±2^{𝑛/2}, for every 𝑢∈𝔽_{2}^{𝑛}. - 𝑓 is bent if and only if for any nonzero element 𝑎 the Boolean function 𝐷
_{𝑎}𝑓(𝑥)=𝑓(𝑥+𝑎)+𝑓(𝑥) is balanced.

## Correlation-immunity order

A Boolean function 𝑓 is *𝑚-th order correlation-immune* if the probability distribution of the output is unaltered when any 𝑚 input variables are fixed.
Balanced 𝑚-th order correlation-immune functions are called *𝑚-resilient*.

Given 𝑓 a 𝑛-variable function with correlation-immunity of order 𝑚 then

If 𝑓 is also balanced, then