Boolean Functions

From Boolean Functions
Revision as of 09:09, 2 October 2019 by Ivi062 (talk | contribs) (β†’β€ŽAlgebraic normal form)
Jump to: navigation, search


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 is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given , the support of x is the set . The Hamming weight of π‘₯ is the size of its support (). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set . The Hamming distance of two functions 𝑓,𝑔 is the size of the set .

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

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

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 where π˜— is a polynomial over the finite field F2𝑛 but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈𝘫≠0.

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)

The set 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
  • Parseval's relation:
  • Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements π‘Ž,𝑏 in 𝔽2𝑛
    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.