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 $f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F}$ is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given $x=(x_{1},\ldots ,x_{n})\in \mathbb {F} _{2}^{n}$ , the support of x is the set $supp_{x}=\{i\in \{1,\ldots ,n\}:x_{i}=1\}$ . The Hamming weight of 𝑥 is the size of its support ($w_{H}(x)=|supp_{x}|$ ). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set $\{x\in \mathbb {F} _{2}^{n}:f(x)\neq 0\}$ . The Hamming distance of two functions 𝑓,𝑔 (𝖽𝐻(𝑓,𝑔)) is the size of the set $\{x\in \mathbb {F} _{2}^{n}:f(x)\neq g(x)\}\ (w_{H}(f\oplus g))$ .

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

$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}).$ 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;

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

$f(x)=\sum _{j\in \Gamma _{n}}{\mbox{Tr}}_{\mathbb {F} _{2^{o(j)}}/\mathbb {F} _{2}}(A_{j}x^{j}),\quad x\in \mathbb {F} _{2^{n}},$ 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 ${\mbox{Tr}}_{\mathbb {F} _{2^{n}}/\mathbb {F} _{2}}(P(x))$ where 𝘗 is a polynomial over the finite field F2𝑛 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 $\max _{j\in \Gamma _{n}|A_{j}\neq 0}w_{2}(j)$ , where 𝓌2(𝑗) is the Hamming weight of the binary expansion of 𝑗.

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)

$W_{f}(u)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{f(x)+x\cdot u},$ The set $\{u\in \mathbb {F} _{2}^{n}:W_{f}(u)\neq 0\}=\{u\in \mathbb {F} _{2}^{n}:W_{f}(u)=1\}$ 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
$\sum _{u\in \mathbb {F} _{2}^{n}}W_{f}(u)(-1)^{u\cdot x}=2^{n}(-1)^{f(x)};$ • Parseval's relation:
$\sum _{u\in \mathbb {F} _{2}^{n}}W_{f}^{2}(u)=2^{2n};$ • Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements 𝑎,𝑏 in 𝔽2𝑛
$\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},$ for 𝐸 the orthogonal subspace of 𝐸,{𝑢∈𝔽2𝑛 : 𝑢·𝑥=0, for all 𝑥∈𝐸}.

Equivalence of Boolean functions

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 EA-equivalence is called EA-invariant.

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,

${\mathcal {NL}}(f)=\min _{g\in {\mathcal {A}}}d_{H}(f,g)$ • For every 𝑓 we have ${\mathcal {NL}}(f)=2^{n-1}-{\frac {1}{2}}\max _{u\in \mathbb {F} _{2}^{n}}|W_{f}(u)|$ .
• From Parseval relation we obtain the covering radius bound ${\mathcal {NL}}(f)\leq 2^{n-1}-2^{n/2-1}$ .
• A function achieving the covering radius bound with equality is called bent (𝑛 is an even integer).
• 𝑓 is bent if and only if 𝑊𝑓(𝑢)=±2𝑛/2, for every 𝑢∈𝔽2𝑛.