# Difference between revisions of "Plateaued Functions"

Line 34: | Line 34: | ||

at <math>(a,b)</math>. If <math>\phi</math> is injective, resp. takes each value in its image set two times, then <math>f_{\phi,h}</math> is plateaued of amplitude <math>2^r</math>, resp. <math>2^{r+1}</math>. | at <math>(a,b)</math>. If <math>\phi</math> is injective, resp. takes each value in its image set two times, then <math>f_{\phi,h}</math> is plateaued of amplitude <math>2^r</math>, resp. <math>2^{r+1}</math>. | ||

+ | |||

+ | = Characterization of Plateaued Functions <ref name="carletPlateuaed">Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.</ref> = | ||

+ | |||

+ | == Characterization by the Derivatives == | ||

+ | |||

+ | Using the fact that a Boolean function <math>f</math> is plateaued if and only if the expression <math>\sum_{a,b \in \mathbb{F}_2^n} (-1)^{DaDbf(x)}</math> does not depend on <math>x \in \mathbb{F}_2^n</math>, one can derive the following characterization. | ||

+ | |||

+ | Let <math>F</math> be an <math>(n,m)</math>-function. Then: | ||

+ | |||

+ | * F is plateuaed if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set | ||

+ | |||

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

+ | |||

+ | does not depend on <math>x</math>; | ||

+ | |||

+ | * F is plateaued with single amplitude if and only if the size of the set depends neither on <math>x</math>, nor on <math>v \in \mathbb{F}_2^m</math> for <math>v \ne 0</math>. | ||

+ | |||

+ | Moreover: | ||

+ | |||

+ | * for every <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals that of <math>D_aF(b) + D_aF(x)</math> when <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>; | ||

+ | |||

+ | * if two plateaued functions <math>F,G</math> have the same distribution, then all of their component functions <math>u \cdot F, u\cdot G</math> have the same amplitude. | ||

+ | |||

+ | === Power Functions === | ||

+ | |||

+ | Let <math>F(x) = x^d</math>. Then, for every $v,x,\lambda \in \mathbb{F}_{2^n}</math> with <math>\lambda \ne 0</math>, we have | ||

+ | |||

+ | <div><math> | \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(x) = v \} | = | \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(x/\lambda) = v/\lambda^d \}|.</math></div> | ||

+ | |||

+ | Then: | ||

+ | |||

+ | * <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_{2^n}</math>, we have | ||

+ | |||

+ | <div><math>| \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(1) = v \} | = | \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(0) = v \}|;</math></div> | ||

+ | |||

+ | * <math>F</math> is plateaued with single amplitude if and only if the size above does not, in addition, depend on <math>v \ne 0</math>. | ||

+ | |||

+ | === Functions with Unbalanced Components === | ||

+ | |||

+ | Let <math>F</math> be an <math>(n,m)</math>-function. Then <math>F</math> is plateuaed with all components unbalanced if and only if, for every <math>v,x \in \mathbb{F}_{2}^n</math>, we have | ||

+ | |||

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

+ | |||

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

## Revision as of 19:53, 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*.

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