Boolean Functions

Introduction

Let <math>\mathbb{F}_2^n</math> 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 <math>2^n \mbox{ elements, }\mathbb{F}_{2^n}</math>. A function <math>f : \mathbb{F}_2^n\rightarrow\mathbb{F}</math> is called a Boolean function in dimenstion n (or n-variable Boolean function).

Given <math>x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n</math>, the support of x is the set <math>supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}</math>. The Hamming weight of x is the size of its support (<math>w_H(x)=|supp_x|</math>). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>. The Hamming distance of two functions f,g is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.

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 <math>\mathbb{F}</math> of the form

<math> 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). </math>

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, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>.

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

<math> f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n}, </math>

with Γ_n set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2ⁿ-1), o(j) size of the cyclotomic coset containing j, A_j ∈ 𝔽_2^o(j), Tr_{𝔽2^o(j)/𝔽2} trace function from 𝔽_{2^o(j) to 𝔽2.}

Such representation is also called the univariate representation .

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