# Difference between revisions of "Boolean Functions"

m (→Equivalence of Boolean functions) |
m (→Equivalences of Boolean functions) |
||

Line 95: | Line 95: | ||

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 | + | A parameter that is preserved by an equivalence relation is called <i>invariant</i>. |

+ | |||

+ | * The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence. | ||

+ | * If 𝑓,𝑔 are affine equivalent, then | ||

=The Nonlinearity= | =The Nonlinearity= |

## Revision as of 16:28, 11 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 𝑗.

# On the weight of a Boolean function

For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied.

- If 𝑑°𝑓=1 then 𝓌
_{𝐻}(𝑓)=2^{𝑛-1}. - If 𝑑°𝑓=2 then 𝓌
_{𝐻}(𝑓)=2^{𝑛-1}or 𝓌_{𝐻}(𝑓)=2^{𝑛-1}±2^{𝑛-1-ℎ}, with 0≤ℎ≤𝑛/2. - If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌
_{𝐻}(𝑓)≥2^{𝑛-𝑟}. - 𝓌
_{𝐻}(𝑓) is odd if and only if 𝑑°𝑓=𝑛.

# 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 𝑥∈𝐸}.

# Equivalences of Boolean functions

Two 𝑛-variable Boolean functions 𝑓,𝑔 are called *affine equivalent* if there exists a linear automorphism 𝐿 and a vecor 𝑎 such that

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 an equivalence relation is called *invariant*.

- The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
- If 𝑓,𝑔 are affine equivalent, then

# 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}^{𝑛}.