Boolean Functions

Introduction

Let $\mathbb {F} _{2}^{n}$ be the vector space of dimension n 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^{n}{\mbox{ elements, }}\mathbb {F} _{2^{n}}$. A function $f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F}$ is called a Boolean function in dimenstion n (or n-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 x is the size of its support ($w_{H}(x)=|supp_{x}|$). Similarly the Hamming weight of a Boolean function f 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 f,g 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 f.

x			f(x)
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 n-variable Boolean function can be represented by a multivariate polynomial over $\mathbb {F}$ 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 f (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, $d^{0}f=\max\{|I|:a_{I}\neq 0\}$.

Trace representation

We identify the vector space with the finite field and we consider f an n-variable Boolean function of even weight (hence of algebraic degree at most n-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)}}\setminus \mathbb {F} _{2}}(A_{j}x^{j}),\quad x\in \mathbb {F} _{2^{n}},{\mbox{with }}\Gamma _{n}{\mbox{ set of integers obtained by choosing one element in each cyclotomic coset of 2 }}(\mod 2^{n}-1),o(j){\mbox{ size of the cyclotomic coset containing }}j,A_{j}\in \mathbb {F} _{2^{o(j)}},{\mbox{Tr}}_{\mathbb {F} _{2^{o(j)}}\setminus \mathbb {F} _{2}}{\mbox{ trace function from }}\mathbb {F} _{2^{o(j)}}{\mbox{ to }}\mathbb {F} _{2}.$ Such representation is also called the univariate representation .

f can also be simply presented in the form ${\mbox{Tr}}_{\mathbb {F} _{2^{n}}\setminus \mathbb {F} _{2}}(P(x)){\mbox{ where }}P{\mbox{ is a polynomial over the finite field }}\mathbb {F} _{2^{n}}$ but such representation is not unique, unless o(j)=n for every j such that A_j≠0.