# Difference between revisions of "Boolean Functions"

m (ββTrace representation) |
m |
||

Line 8: | Line 8: | ||

The Hamming weight of π₯ is the size of its support (<math>w_H(x)=|supp_x|</math>). | The Hamming weight of π₯ is the size of its support (<math>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>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>. | Similarly the Hamming weight of a Boolean function π 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 π,π is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>. | + | The Hamming distance of two functions π,π (π½<sub>π»</sub>(π,π)) 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= | =Representation of a Boolean function= | ||

Line 75: | Line 75: | ||

With an innner product in π½<sub>2</sub><sup>π</sup> π₯Β·π¦, the value of π<sub>π</sub> at π’βπ½<sub>2</sub><sup>π</sup> is the following sum (over the integers) | With an innner product in π½<sub>2</sub><sup>π</sup> π₯Β·π¦, the value of π<sub>π</sub> at π’βπ½<sub>2</sub><sup>π</sup> is the following sum (over the integers) | ||

<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center> | <center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center> | ||

β | The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}</math> is the <i>Walsh support</i> of π. | + | The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}=\{ u\in\mathbb{F}_2^n : W_f(u)=1 \}</math> is the <i>Walsh support</i> of π. |

==Properties of the Walsh transform== | ==Properties of the Walsh transform== | ||

Line 86: | Line 86: | ||

Two π-variable Boolean functions π,π are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism πΏ, an affine Boolean function π and a vecor π such that <center>π(π₯) = π(πΏ(π₯)+π)+π(π₯).</center> | Two π-variable Boolean functions π,π are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism πΏ, an affine Boolean function π and a vecor π such that <center>π(π₯) = π(πΏ(π₯)+π)+π(π₯).</center> | ||

A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>. | A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>. | ||

+ | |||

+ | =The Nonlinearity= | ||

+ | The <em>nonlinearity</em> of a function π is defined as its minimal distance to affine functions, i.e. called π the set of all affine π-variable functions, | ||

+ | <center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center> | ||

+ | |||

+ | * For every π we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}|W_f(u)|</math>. | ||

+ | * From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>. | ||

+ | * A function achieving the covering radius bound with equality is called <em>bent</em> (π is an even integer). | ||

+ | * π is bent if and only if π<sub>π</sub>(π’)=Β±2<sup>π/2</sup>, for every π’βπ½<sub>2</sub><sup>π</sup>. |

## Revision as of 10:43, 2 October 2019

## Contents

# 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 F_{2π} 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*.

# The Nonlinearity

The *nonlinearity* of a function π is defined as its minimal distance to affine functions, i.e. called π the set of all affine π-variable functions,

- For every π we have .
- From Parseval relation we obtain the
*covering radius bound*. - A function achieving the covering radius bound with equality is called
*bent*(π is an even integer). - π is bent if and only if π
_{π}(π’)=Β±2^{π/2}, for every π’βπ½_{2}^{π}.