Revision as of 18:53, 7 February 2019

Background and Definition

A Boolean function $f:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2}$ is said to be plateaued if its Walsh transform takes at most three distinct values, viz. $0$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \pm \mu } for some positive ineger Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mu } called the amplitude of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f} .

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if $F$ is an $(n,m)$ -function, we say that $F$ is plateaued if all its component functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\cdot F} for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\neq 0} are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that $F$ 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 $f_{\phi ,h}$ of the form

f_{\phi ,h}(x,y)=x\cdot \phi (y)+h(y)

for $x\in \mathbb {F} _{2}^{r},y\in \mathbb {F} _{2}^{s}$ , where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r} and $s$ are any positive integers, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=r+s} , $\phi :\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}^{r}$ is arbitrary and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle h:\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}} is any Boolean function.

The Walsh transform of $f_{\phi ,h}$ takes the value

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle W_{f_{\phi ,h}}(a,b)=2^{r}\sum _{y\in \phi ^{-1}(a)}(-1)^{b\cdot y+h(y)}}

at $(a,b)$ . If $\phi$ is injective, resp. takes each value in its image set two times, then $f_{\phi ,h}$ is plateaued of amplitude Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{r}} , resp. Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{r+1}} .

Characterization of Plateaued Functions ^[2]

Characterization by the Derivatives

Using the fact that a Boolean function Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f} is plateaued if and only if the expression $\sum _{a,b\in \mathbb {F} _{2}^{n}}(-1)^{DaDbf(x)}$ does not depend on $x\in \mathbb {F} _{2}^{n}$ , one can derive the following characterization.

Let $F$ be an $(n,m)$ -function. Then:

F is plateuaed if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\in \mathbb {F} _{2}^{m}} , the size of the set

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}}

does not depend on $x$ ;

F is plateaued with single amplitude if and only if the size of the set depends neither on $x$ , nor on Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\in \mathbb {F} _{2}^{m}} for $v\neq 0$ .

Moreover:

for every $F$ , the value distribution of $D_{a}D_{b}F(x)$ equals that of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D_{a}F(b)+D_{a}F(x)} when $(a,b)$ ranges over $(\mathbb {F} _{2}^{n})^{2}$ ;

if two plateaued functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F,G} have the same distribution, then all of their component functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\cdot F,u\cdot G} have the same amplitude.

Power Functions

Let $F(x)=x^{d}$ . Then, for every $v,x,\lambda \in \mathbb{F}_{2^n}</math> with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \lambda \neq 0} , we have

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

Then:

$F$ is plateaued if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\in \mathbb {F} _{2^{n}}} , we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(1)=v\}|=|\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(0)=v\}|;}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is plateaued with single amplitude if and only if the size above does not, in addition, depend on $v\neq 0$ .

Functions with Unbalanced Components

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} be an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function. Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is plateuaed with all components unbalanced if and only if, for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v,x \in \mathbb{F}_{2}^n} , we have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle | \{ (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 \}|.}

Moreover, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is plateaued with single amplitude if and only if this value does not, in addition, depend on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v \ne 0} .

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

[camion1992-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.

[carletPlateuaed-2] Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.

[1]

[2]

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

Anonymous

Search

Plateaued Functions: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:53, 7 February 2019

Contents

Background and Definition

Equivalence relations

Relations to other classes of functions

Constructions of Boolean plateaued functions

Primary constructons

Generalization of the Maiorana-MacFarland Functions ^[1]

Characterization of Plateaued Functions ^[2]

Characterization by the Derivatives

Power Functions

Functions with Unbalanced Components

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

Plateaued Functions: Difference between revisions

Revision as of 18:53, 7 February 2019

Background and Definition

Equivalence relations

Relations to other classes of functions

Constructions of Boolean plateaued functions

Primary constructons

Generalization of the Maiorana-MacFarland Functions [1]

Characterization of Plateaued Functions [2]

Characterization by the Derivatives

Power Functions

Functions with Unbalanced Components

Navigation

Wiki tools

Page tools

Categories

Generalization of the Maiorana-MacFarland Functions ^[1]

Characterization of Plateaued Functions ^[2]