Difference between revisions of "Plateaued Functions"

From Boolean Functions
Jump to: navigation, search
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

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

  1. Camion P, Carlet C, Charpin P, Sendrier N. On Correlation-immune functions. InAdvances in Cryptology—CRYPTO’91 1992 (pp. 86-100). Springer Berlin/Heidelberg.
  2. Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.