# Difference between revisions of "Boolean Functions"

m |
m (ββThe Nonlinearity) |
||

(6 intermediate revisions by the same user not shown) | |||

Line 77: | Line 77: | ||

* If πΒ°πβ€π and π nonzero then π<sub>π»</sub>(π)β₯2<sup>π-π</sup>. | * If πΒ°πβ€π and π nonzero then π<sub>π»</sub>(π)β₯2<sup>π-π</sup>. | ||

* π<sub>π»</sub>(π) is odd if and only if πΒ°π=π. | * π<sub>π»</sub>(π) is odd if and only if πΒ°π=π. | ||

β | |||

=The Walsh transform= | =The Walsh transform= | ||

Line 91: | Line 90: | ||

* Poisson summation formula: for any vector subspace πΈ of π½<sub>2</sub><sup>π</sup> and for any elements π,π in π½<sub>2</sub><sup>π</sup> <center><math> \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></center> for πΈ<sup>β</sup> the orthogonal subspace of πΈ,{π’βπ½<sub>2</sub><sup>π</sup> : π’Β·π₯=0, for all π₯βπΈ}. | * Poisson summation formula: for any vector subspace πΈ of π½<sub>2</sub><sup>π</sup> and for any elements π,π in π½<sub>2</sub><sup>π</sup> <center><math> \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></center> for πΈ<sup>β</sup> the orthogonal subspace of πΈ,{π’βπ½<sub>2</sub><sup>π</sup> : π’Β·π₯=0, for all π₯βπΈ}. | ||

β | = | + | =Equivalences of Boolean functions= |

+ | Two π-variable Boolean functions π,π are called <i>affine equivalent</i> if there exists a linear automorphism πΏ 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> | 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 <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>. | ||

β | =The Nonlinearity= | + | =Properties important for cryptographic applications= |

+ | |||

+ | ==Balanced functions== | ||

+ | An π-variable Boolean function π is called <em>balanced</em> if π<sub>π»</sub>(π)=2<sup>π-1</sup>, so its output is uniformly distributed. | ||

+ | Such functions cannot have maximal degree. | ||

+ | Most cryptographic applications use balanced Boolean functions. | ||

+ | |||

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

Line 101: | Line 112: | ||

* 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>. | * 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>. | * 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 | + | * A function achieving the covering radius bound with equality is called [[Bent Boolean Functions| bent]] (π is an even integer and the function is not balanced). |

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

+ | * π is bent if and only if for any nonzero element π the Boolean function π·<sub>π</sub>π(π₯)=π(π₯+π)+π(π₯) is balanced. | ||

+ | |||

+ | ==Correlation-immunity order== | ||

+ | A Boolean function π is <em>π-th order correlation-immune</em> if the probability distribution of the output is unaltered when any π input variables are fixed. | ||

+ | Balanced π-th order correlation-immune functions are called <em>π-resilient</em>. | ||

+ | |||

+ | Given π a π-variable function with correlation-immunity of order π then <center>π+πΒ°πβ€π.</center> | ||

+ | If π is also balanced, then <center>π+πΒ°πβ€π-1.</center> |

## Latest revision as of 15:39, 25 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 .

# Properties important for cryptographic applications

## Balanced functions

An π-variable Boolean function π is called *balanced* if π_{π»}(π)=2^{π-1}, so its output is uniformly distributed.
Such functions cannot have maximal degree.
Most cryptographic applications use balanced Boolean functions.

## 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 and the function is not balanced).
- π is bent if and only if π
_{π}(π’)=Β±2^{π/2}, for every π’βπ½_{2}^{π}. - π is bent if and only if for any nonzero element π the Boolean function π·
_{π}π(π₯)=π(π₯+π)+π(π₯) is balanced.

## Correlation-immunity order

A Boolean function π is *π-th order correlation-immune* if the probability distribution of the output is unaltered when any π input variables are fixed.
Balanced π-th order correlation-immune functions are called *π-resilient*.

Given π a π-variable function with correlation-immunity of order π then

If π is also balanced, then