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

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

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

## 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

${\displaystyle 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 ${\displaystyle {\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.

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

${\displaystyle W_{f}(u)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{f(x)+x\cdot u},}$

The set ${\displaystyle \{u\in \mathbb {F} _{2}^{n}:W_{f}(u)\neq 0\}}$ 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
${\displaystyle \sum _{u\in \mathbb {F} _{2}^{n}}W_{f}(u)(-1)^{u\cdot x}=2^{n}(-1)^{f(x)};}$
• Parseval's relation:
${\displaystyle \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𝑛
${\displaystyle \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.