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

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

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

When we consider the trace representation of of a function, then the algebraic degree is given by ${\displaystyle \max _{j\in \Gamma _{n}|A_{j}\neq 0}w_{2}(j)}$, 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)

${\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\}=\{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
${\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 π₯βπΈ}.

# 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 ${\displaystyle W_{g}(u)=(-1)^{u\cdot L^{-1}(a)}W_{f}(L^{-1}(u))}$.

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

${\displaystyle {\mathcal {NL}}(f)=\min _{g\in {\mathcal {A}}}d_{H}(f,g)}$
• For every π we have ${\displaystyle {\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 ${\displaystyle {\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 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

π+πΒ°πβ€π-1.