Boolean Functions

Introduction

Let 𝔽₂^𝑛 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 𝔽₂ 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;
• quadratic if 𝑑°𝑓=2.

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

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 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 $\max _{j\in \Gamma _{n}|A_{j}\neq 0}w_{2}(j)$, where 𝓌₂(𝑗) 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 𝔽₂^𝑛 𝑥·𝑦, the value of 𝑊_𝑓 at 𝑢∈𝔽₂^𝑛 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 𝔽₂^𝑛 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 𝔽₂^𝑛 and for any elements 𝑎,𝑏 in 𝔽₂^𝑛 $\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 𝐸,{𝑢∈𝔽₂^𝑛 : 𝑢·𝑥=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 $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,

${\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 and the function is not balanced).
• 𝑓 is bent if and only if 𝑊_𝑓(𝑢)=±2^𝑛/2, for every 𝑢∈𝔽₂^𝑛.

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.