Boolean Functions

Introduction

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n \mbox{ elements, }\mathbb{F}_{2^n}} . A function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : \mathbb{F}_2^n\rightarrow\mathbb{F}} is called a Boolean function in dimenstion n (or n-variable Boolean function).

Given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n} , the support of x is the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}} . The Hamming weight of x is the size of its support (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_H(x)=|supp_x|} ). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x\in\mathbb{F}_2^n : f(x)\ne0 \}} . The Hamming distance of two functions f,g is the size of the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}} of the form

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 f (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d^0f=\max \{ |I| : a_I\ne0 \}} .

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}\setminus\mathbb{F}_2}(A_jx^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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.