Difference between revisions of "Boolean Functions"

From Boolean Functions
Jump to: navigation, search
m (Algebraic normal form)
m (Trace representation)
Line 68: Line 68:
  
 
𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math>  where 𝘗 is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>&ne;0.
 
𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math>  where 𝘗 is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>&ne;0.
 +
 +
When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n | A_j\ne0}w_2(j)</math>, where 𝓌<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗.
  
 
=The Walsh transform=
 
=The Walsh transform=

Revision as of 09:16, 2 October 2019

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 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.

When we consider the trace representation of of a function, then the algebraic degree is given by , 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)

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.