# Difference between revisions of "Plateaued Functions"

Line 4: | Line 4: | ||

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if <math>F</math> is an <math>(n,m)</math>-function, we say that <math>F</math> is ''plateaued'' if all its component functions <math>u \cdot F</math> for <math>u \ne 0</math> are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that <math>F</math> is ''plateaued with single amplitude''. | This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if <math>F</math> is an <math>(n,m)</math>-function, we say that <math>F</math> is ''plateaued'' if all its component functions <math>u \cdot F</math> for <math>u \ne 0</math> are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that <math>F</math> is ''plateaued with single amplitude''. | ||

+ | |||

+ | The characterization by means of the derivatives below suggests the following definition: a v.B.f. <math>F</math> is said to be ''strongly-plateuaed'' if, for every <math>a</math> and every <math>v</math>, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on <math>x</math>, or, equivalently, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}</math> does not depend on <math>x</math>. | ||

== Equivalence relations == | == Equivalence relations == | ||

Line 78: | Line 80: | ||

Moreover, <math>F</math> is plateaued with single amplitude if and only if this value does not, in addition, depend on <math>v</math> for <math>v \ne 0</math>. | Moreover, <math>F</math> is plateaued with single amplitude if and only if this value does not, in addition, depend on <math>v</math> for <math>v \ne 0</math>. | ||

+ | |||

+ | === Strongly-Plateaued Functions === | ||

+ | |||

+ | A Boolean function is strongly-plateaued if and only if its partially-bent. A v.B.f. is strongly-plateaued if and only if all of its component functions are partially-bent. In particular, bent and quadratic Boolean and vectorial functions are strongly-plateaued. | ||

+ | |||

+ | The image set <math>{\rm Im}(D_aF)</math> of any derivative of a strongly-plateaued function <math>F</math> is an affine space. | ||

+ | |||

+ | == Characterization by the Auto-Correlation Functions == | ||

+ | |||

+ | Recall that the autocorrelation function of a Boolean function <math>f</math> is defined as <math>{\Delta_f}(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + f(x+a)}</math>. | ||

+ | |||

+ | An <math>n</math>-variable Boolean function <math>f</math> is plateaued if and only if, for every <math>x \in \mathbb{F}_2^n</math>, we have | ||

+ | |||

+ | <div><math>2^n \sum_{a \in \mathbb{F}_2^n} \Delta_f(a) \Delta_f(a+x) = \left( \sum_{a \in \mathbb{F}_2^n} \Delta_f^2(a) \right) \Delta_f(x).</math></div> | ||

+ | |||

+ | An <math>(n,m)</math>-function <math>F</math> is plateaued if and only if, for every <math>x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m</math>, we have | ||

+ | |||

+ | <div><math> 2^n \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}(a) \Delta_{u \cdot F}(a+x) = \left( \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}^2(a) \right) \Delta_{u \cdot F}(x).</math></div> | ||

+ | |||

+ | Furthermore, <math>F</math> is plateaued with single amplitude if and only if, for every <math>x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m</math>, we have | ||

+ | |||

+ | <div><math> \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}(a) \Delta_{u \cdot F}(a+x) = \mu^2 \Delta_{u \cdot F}(x).</math></div> | ||

+ | |||

+ | Alternatively, <math>F</math> is plateuaed if and only if, for every <math>x,v \in \mathbb{F}_2^n</math>, we have | ||

+ | |||

+ | <div><math> 2^n | \{ (a,b,c) \in (\mathbb{F}_2^n)^3 : F(a) + F(b) + F(c) + F(a+b+c+x) = v \}| = | \{ (a,b,c,d) \in (\mathbb{F}_2^n)^4 : F(a) + F(b) + F(c) + F(a+b+c) + F(d) + F(d+x) = v \}|.</math></div> |

## Revision as of 20:11, 7 February 2019

## Contents

# Background and Definition

A Boolean function is said to be *plateaued* if its Walsh transform takes at most three distinct values, viz. and for some positive ineger called the *amplitude* of .

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if is an -function, we say that is *plateaued* if all its component functions for are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that is *plateaued with single amplitude*.

The characterization by means of the derivatives below suggests the following definition: a v.B.f. is said to be *strongly-plateuaed* if, for every and every , the size of the set does not depend on , or, equivalently, the size of the set does not depend on .

## Equivalence relations

The class of functions that are plateaued with single amplitude is CCZ-invariant.

The class of plateaued functions is only EA-invariant.

## Relations to other classes of functions

All bent and semi-bent Boolean functions are plateaued.

Any vectorial AB function is plateaued with single amplitude.

# Constructions of Boolean plateaued functions

## Primary constructons

### Generalization of the Maiorana-MacFarland Functions ^{[1]}

The Maiorana-MacFarland class of bent functions can be generalized into the class of functions of the form

for , where and are any positive integers, , is arbitrary and is any Boolean function.

The Walsh transform of takes the value

at . If is injective, resp. takes each value in its image set two times, then is plateaued of amplitude , resp. .

# Characterization of Plateaued Functions ^{[2]}

## Characterization by the Derivatives

Using the fact that a Boolean function is plateaued if and only if the expression does not depend on , one can derive the following characterization.

Let be an -function. Then:

- F is plateuaed if and only if, for every , the size of the set

does not depend on ;

- F is plateaued with single amplitude if and only if the size of the set depends neither on , nor on for .

Moreover:

- for every , the value distribution of equals that of when ranges over ;

- if two plateaued functions have the same distribution, then all of their component functions have the same amplitude.

### Power Functions

Let . Then, for every $v,x,\lambda \in \mathbb{F}_{2^n}</math> with , we have

Then:

- is plateaued if and only if, for every , we have

- is plateaued with single amplitude if and only if the size above does not, in addition, depend on .

### Functions with Unbalanced Components

Let be an -function. Then is plateuaed with all components unbalanced if and only if, for every , we have

Moreover, is plateaued with single amplitude if and only if this value does not, in addition, depend on for .

### Strongly-Plateaued Functions

A Boolean function is strongly-plateaued if and only if its partially-bent. A v.B.f. is strongly-plateaued if and only if all of its component functions are partially-bent. In particular, bent and quadratic Boolean and vectorial functions are strongly-plateaued.

The image set of any derivative of a strongly-plateaued function is an affine space.

## Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean function is defined as .

An -variable Boolean function is plateaued if and only if, for every , we have

An -function is plateaued if and only if, for every , we have

Furthermore, is plateaued with single amplitude if and only if, for every , we have

Alternatively, is plateuaed if and only if, for every , we have