Boolean Functions

From Boolean
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 [math]\displaystyle{ f : \mathbb{F}_2^n\rightarrow\mathbb{F} }[/math] is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given [math]\displaystyle{ x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n }[/math], the support of x is the set [math]\displaystyle{ supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \} }[/math]. The Hamming weight of π‘₯ is the size of its support ([math]\displaystyle{ w_H(x)=|supp_x| }[/math]). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\ne0 \} }[/math]. The Hamming distance of two functions 𝑓,𝑔 is the size of the set [math]\displaystyle{ \{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 𝑓.

π‘₯ 𝑓(π‘₯)
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

[math]\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). }[/math]

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 π‘’βˆˆπ”½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

[math]\displaystyle{ 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 Γ𝑛 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 [math]\displaystyle{ \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x)) }[/math] 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 [math]\displaystyle{ \max_{j\in\Gamma_n | A_j\ne0}w_2(j) }[/math], where π“Œ2(𝑗) is the Hamming weight of the binary expansion of 𝑗.

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)

[math]\displaystyle{ W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u}, }[/math]

The set [math]\displaystyle{ \{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \} }[/math] 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
    [math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)}; }[/math]
  • Parseval's relation:
    [math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n}; }[/math]
  • Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements π‘Ž,𝑏 in 𝔽2𝑛
    [math]\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}, }[/math]
    for πΈβŸ‚ the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½2𝑛 : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.

Equivalence of Boolean functions

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 EA-equivalence is called EA-invariant.