Plateaued Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
mNo edit summary
Β 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
= Background and Definition =
= Background and Definition =


A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is said to be ''plateaued'' if its Walsh transform takes at most three distinct values, viz. <math>0</math> and <math>\pm \mu</math> for some positive ineger <math>\mu</math> called the ''amplitude'' of <math>f</math>.
A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is said to be ''plateaued'' if its Walsh transform takes at most three distinct values, viz. 0 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 <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 𝐹 is an (𝑛,π‘š)-function, we say that 𝐹 is ''plateaued'' if all its component functions 𝑒⋅𝐹 for 𝑒≠0 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 <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on π‘₯, 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 π‘₯.


== Equivalence relations ==
== Equivalence relations ==
Line 27: Line 29:
<div><math>f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y)</math></div>
<div><math>f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y)</math></div>


for <math>x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s</math>, where <math>r</math> and <math>s</math> are any positive integers, <math>n = r + s</math>, <math>\phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r</math> is arbitrary and <math>h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2</math> is any Boolean function.
for <math>x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s</math>, where π‘Ÿ and 𝑠 are any positive integers, 𝑛 = π‘Ÿ + 𝑠, <math>\phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r</math> is arbitrary and <math>h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2</math> is any Boolean function.


The Walsh transform of <math>f_{\phi,h}</math> takes the value
The Walsh transform of <math>f_{\phi,h}</math> takes the value
Line 33: Line 35:
<div><math>W_{f_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)}</math></div>
<div><math>W_{f_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)}</math></div>


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 (π‘Ž,𝑏). If πœ‘ is injective, resp. takes each value in its image set two times, then <math>f_{\phi,h}</math> is plateaued of amplitude 2<sup>π‘Ÿ</sup>, resp. 2<sup>π‘Ÿ+1</sup>.


= 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 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>Β  =
Line 39: Line 41:
== Characterization by the Derivatives ==
== 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.
Using the fact that a Boolean function 𝑓 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:
Let 𝐹 be an (𝑛,π‘š)-function. Then:


* F is plateuaed if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set
* 𝐹 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>
<div><math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math></div>
Line 49: Line 51:
does not depend on <math>x</math>;
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>.
* 𝐹 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:
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>;
* for every 𝐹, 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.
* if two plateaued functions 𝐹,𝐺 have the same distribution, then all of their component functions <math>u \cdot F, u\cdot G</math> have the same amplitude.


=== Power Functions ===
=== Power Functions ===
Line 65: Line 67:
Then:
Then:


* <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_{2^n}</math>, we have
* 𝐹 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>
<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>.
* 𝐹 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 ===
=== 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
Let 𝐹 be an (𝑛,π‘š)-function. Then 𝐹 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>
<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>.
Moreover, 𝐹 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 𝑛-variable Boolean function 𝑓 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 (𝑛,π‘š)-function 𝐹 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, 𝐹 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, 𝐹 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>
Β 
== Characterization by the Means of the Power Moments of the Walsh Transform ==
Β 
=== First Characterization ===
Β 
A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is plateuaed if and only if, for every <math>0 \ne \alpha \in \mathbb{F}_2^n</math>, we have
Β 
<div><math>\sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0.</math></div>
Β 
An (𝑛,π‘š)-function 𝐹 is plateuaed if and only if for every <math>u \in \mathbb{F}_2^m</math> and <math>0 \ne \alpha \in \mathbb{F}_2^n</math>, we have
Β 
<div><math>\sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0.</math></div>
Β 
Furthermore, 𝐹 is plateaued with single amplitude if and only if, in addition, the sum <math>\sum_{w \in \mathbb{F}_2^n} W_F^4(w,u)</math> does not depend on <math>u</math> for <math>u \ne 0</math>.
Β 
=== Second Characterization ===
Β 
A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is plateuaed if and only if, for every <math>b \in \mathbb{F}_2</math>, we have
Β 
<div><math> \sum_{a \in \mathbb{F}_2} W_f^4(a) = 2^n(-1)^{f(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_f^3(a). </math></div>
Β 
An (𝑛,π‘š)-function 𝐹 is plateuaed if and only if, for every <math>b \in \mathbb{F}_2^n</math> and every <math>u \in \mathbb{F}_m</math>, we have
Β 
<div><math> \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) = 2^n(-1)^{u \cdot F(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_F^3(a,u).</math></div>
Β 
Moreover, 𝐹 is plateaued with single amplitude if and only if the two sums above do not depend on 𝑒 for <math>u \ne 0</math>.
Β 
=== Third Characterization ===
Β 
Any Boolean function 𝑓 in <math>n</math> variables satisfies
Β 
<div><math> \left( \sum_{a \in \mathbb{F}_2^n} W_f^4(a) \right)^2 \le 2^{2n} \left( \sum_{a \in \mathbb{F}_2^n} W_f^6(a) \right), </math></div>
Β 
with equality if and only if 𝑓 is plateuaed.
Β 
Any (𝑛,π‘š)-function 𝐹 satisfies
Β 
<div><math> \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \right)^2 \le 2^{2n} \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) \right), </math></div>
Β 
with equality if and only if 𝐹 is plateuaed.
Β 
In addition, every (𝑛,π‘š)-function satisfies
Β 
<div><math>\sum_{u \in \mathbb{F}_2^m} \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \le 2^n \sum_{u \in \mathbb{F}_2^m} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) }, </math></div>
Β 
with equality if and only if 𝐹 is plateuaed.
Β 
= Characterization of APN among Plateaued Functions =
Β 
== Characterization by the Derivatives ==
Β 
One very useful property of quadratic functions which extends to plateaued functions is that it suffices to consider the number of solutions to the differential equation <math>D_aF(x) = D_aF(0)</math> in order to decided the APN-ness of a given function 𝐹. More precisely, a plateuaed (𝑛,𝑛) function 𝐹 is APN if and only if the equation
<div><math>F(x) + F(x+a) = F(0) + F(a)</math></div>
has at most two solutions for any <math>0 \ne a \in \mathbb{F}_2^n</math>.
Β 
== Characterization by the Walsh Transform ==
Β 
Suppose 𝐹 is a plateaued (𝑛,𝑛) function with <math>F(0) = 0</math>. Then 𝐹 is APN if and only if
Β 
<div><math>| \{ (x,b) \in \mathbb{F}_{2^n}^2 : F(x) + F(x+b) + F(b) = 0 \} | = 3 \cdot 2^n - 2,</math></div>
Β 
or, equivalently,
Β 
<div><math> \sum_{a \in \mathbb{F}_{2^n}, u \in \mathbb{F}_{2^n}^*} W_F^3(a,u) = 2^{2n+1}(2^n-1).</math></div>
Β 
Β 
Any (𝑛,𝑛)-function satisfies the inequality
Β 
<div><math> 3 \cdot 2^{3^n} - 2^{2n + 1} \le \sum_{u \in \mathbb{F}_2^n} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u)},</math></div>
Β 
with equality if and only if 𝐹 is APN plateaued.
Β 
If we denote by <math>2^{\lambda_u}</math> the amplitude of the component function <math>u \cdot F</math> of a given plateuaed function <math>F</math>, then 𝐹 is APN if and only if
Β 
<div><math>\sum_{0 \ne u \in \mathbb{F}_2^n} 2^{2 \lambda_u} \le 2^{n+1}(2^n-1).</math></div>
Β 
== Functions with Unbalanced Components ==
Β 
Let 𝐹 be an (𝑛,𝑛)-plateaued function with all components unbalanced. Then
Β 
<div><math>| \{ (a,b) \in (\mathbb{F}_2^n)^2 : a \ne b, F(a) = F(b)\}| \ge 2 \cdot (2^n-1),</math></div>
Β 
with equality if and only if 𝐹 is APN.

Latest revision as of 16:05, 5 November 2019

Background and Definition

A Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math] is said to be plateaued if its Walsh transform takes at most three distinct values, viz. 0 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 𝑒≠0 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 [math]\displaystyle{ \{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \} }[/math] does not depend on π‘₯, or, equivalently, the size of the set [math]\displaystyle{ \{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \} }[/math] 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 [math]\displaystyle{ f_{\phi,h} }[/math] of the form

[math]\displaystyle{ f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y) }[/math]

for [math]\displaystyle{ x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s }[/math], where π‘Ÿ and 𝑠 are any positive integers, 𝑛 = π‘Ÿ + 𝑠, [math]\displaystyle{ \phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r }[/math] is arbitrary and [math]\displaystyle{ h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2 }[/math] is any Boolean function.

The Walsh transform of [math]\displaystyle{ f_{\phi,h} }[/math] takes the value

[math]\displaystyle{ W_{f_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)} }[/math]

at (π‘Ž,𝑏). If πœ‘ is injective, resp. takes each value in its image set two times, then [math]\displaystyle{ f_{\phi,h} }[/math] is plateaued of amplitude 2π‘Ÿ, resp. 2π‘Ÿ+1.

Characterization of Plateaued Functions [2]

Characterization by the Derivatives

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

Let 𝐹 be an (𝑛,π‘š)-function. Then:

  • 𝐹 is plateuaed if and only if, for every [math]\displaystyle{ v \in \mathbb{F}_2^m }[/math], the size of the set
[math]\displaystyle{ \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} }[/math]

does not depend on [math]\displaystyle{ x }[/math];

  • 𝐹 is plateaued with single amplitude if and only if the size of the set depends neither on [math]\displaystyle{ x }[/math], nor on [math]\displaystyle{ v \in \mathbb{F}_2^m }[/math] for [math]\displaystyle{ v \ne 0 }[/math].

Moreover:

  • for every 𝐹, the value distribution of [math]\displaystyle{ D_aD_bF(x) }[/math] equals that of [math]\displaystyle{ D_aF(b) + D_aF(x) }[/math] when [math]\displaystyle{ (a,b) }[/math] ranges over [math]\displaystyle{ (\mathbb{F}_2^n)^2 }[/math];
  • if two plateaued functions 𝐹,𝐺 have the same distribution, then all of their component functions [math]\displaystyle{ u \cdot F, u\cdot G }[/math] have the same amplitude.

Power Functions

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

[math]\displaystyle{ | \{ (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]

Then:

  • 𝐹 is plateaued if and only if, for every [math]\displaystyle{ v \in \mathbb{F}_{2^n} }[/math], we have
[math]\displaystyle{ | \{ (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]
  • 𝐹 is plateaued with single amplitude if and only if the size above does not, in addition, depend on [math]\displaystyle{ v \ne 0 }[/math].

Functions with Unbalanced Components

Let 𝐹 be an (𝑛,π‘š)-function. Then 𝐹 is plateuaed with all components unbalanced if and only if, for every [math]\displaystyle{ v,x \in \mathbb{F}_{2}^n }[/math], we have

[math]\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 \}|. }[/math]

Moreover, 𝐹 is plateaued with single amplitude if and only if this value does not, in addition, depend on [math]\displaystyle{ v }[/math] for [math]\displaystyle{ 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]\displaystyle{ {\rm Im}(D_aF) }[/math] of any derivative of a strongly-plateaued function [math]\displaystyle{ F }[/math] is an affine space.

Characterization by the Auto-Correlation Functions

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

An 𝑛-variable Boolean function 𝑓 is plateaued if and only if, for every [math]\displaystyle{ x \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ 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]

An (𝑛,π‘š)-function 𝐹 is plateaued if and only if, for every [math]\displaystyle{ x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m }[/math], we have

[math]\displaystyle{ 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]

Furthermore, 𝐹 is plateaued with single amplitude if and only if, for every [math]\displaystyle{ x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m }[/math], we have

[math]\displaystyle{ \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]

Alternatively, 𝐹 is plateuaed if and only if, for every [math]\displaystyle{ x,v \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ 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]

Characterization by the Means of the Power Moments of the Walsh Transform

First Characterization

A Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math] is plateuaed if and only if, for every [math]\displaystyle{ 0 \ne \alpha \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0. }[/math]

An (𝑛,π‘š)-function 𝐹 is plateuaed if and only if for every [math]\displaystyle{ u \in \mathbb{F}_2^m }[/math] and [math]\displaystyle{ 0 \ne \alpha \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0. }[/math]

Furthermore, 𝐹 is plateaued with single amplitude if and only if, in addition, the sum [math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_F^4(w,u) }[/math] does not depend on [math]\displaystyle{ u }[/math] for [math]\displaystyle{ u \ne 0 }[/math].

Second Characterization

A Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math] is plateuaed if and only if, for every [math]\displaystyle{ b \in \mathbb{F}_2 }[/math], we have

[math]\displaystyle{ \sum_{a \in \mathbb{F}_2} W_f^4(a) = 2^n(-1)^{f(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_f^3(a). }[/math]

An (𝑛,π‘š)-function 𝐹 is plateuaed if and only if, for every [math]\displaystyle{ b \in \mathbb{F}_2^n }[/math] and every [math]\displaystyle{ u \in \mathbb{F}_m }[/math], we have

[math]\displaystyle{ \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) = 2^n(-1)^{u \cdot F(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_F^3(a,u). }[/math]

Moreover, 𝐹 is plateaued with single amplitude if and only if the two sums above do not depend on 𝑒 for [math]\displaystyle{ u \ne 0 }[/math].

Third Characterization

Any Boolean function 𝑓 in [math]\displaystyle{ n }[/math] variables satisfies

[math]\displaystyle{ \left( \sum_{a \in \mathbb{F}_2^n} W_f^4(a) \right)^2 \le 2^{2n} \left( \sum_{a \in \mathbb{F}_2^n} W_f^6(a) \right), }[/math]

with equality if and only if 𝑓 is plateuaed.

Any (𝑛,π‘š)-function 𝐹 satisfies

[math]\displaystyle{ \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \right)^2 \le 2^{2n} \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) \right), }[/math]

with equality if and only if 𝐹 is plateuaed.

In addition, every (𝑛,π‘š)-function satisfies

[math]\displaystyle{ \sum_{u \in \mathbb{F}_2^m} \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \le 2^n \sum_{u \in \mathbb{F}_2^m} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) }, }[/math]

with equality if and only if 𝐹 is plateuaed.

Characterization of APN among Plateaued Functions

Characterization by the Derivatives

One very useful property of quadratic functions which extends to plateaued functions is that it suffices to consider the number of solutions to the differential equation [math]\displaystyle{ D_aF(x) = D_aF(0) }[/math] in order to decided the APN-ness of a given function 𝐹. More precisely, a plateuaed (𝑛,𝑛) function 𝐹 is APN if and only if the equation

[math]\displaystyle{ F(x) + F(x+a) = F(0) + F(a) }[/math]

has at most two solutions for any [math]\displaystyle{ 0 \ne a \in \mathbb{F}_2^n }[/math].

Characterization by the Walsh Transform

Suppose 𝐹 is a plateaued (𝑛,𝑛) function with [math]\displaystyle{ F(0) = 0 }[/math]. Then 𝐹 is APN if and only if

[math]\displaystyle{ | \{ (x,b) \in \mathbb{F}_{2^n}^2 : F(x) + F(x+b) + F(b) = 0 \} | = 3 \cdot 2^n - 2, }[/math]

or, equivalently,

[math]\displaystyle{ \sum_{a \in \mathbb{F}_{2^n}, u \in \mathbb{F}_{2^n}^*} W_F^3(a,u) = 2^{2n+1}(2^n-1). }[/math]


Any (𝑛,𝑛)-function satisfies the inequality

[math]\displaystyle{ 3 \cdot 2^{3^n} - 2^{2n + 1} \le \sum_{u \in \mathbb{F}_2^n} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u)}, }[/math]

with equality if and only if 𝐹 is APN plateaued.

If we denote by [math]\displaystyle{ 2^{\lambda_u} }[/math] the amplitude of the component function [math]\displaystyle{ u \cdot F }[/math] of a given plateuaed function [math]\displaystyle{ F }[/math], then 𝐹 is APN if and only if

[math]\displaystyle{ \sum_{0 \ne u \in \mathbb{F}_2^n} 2^{2 \lambda_u} \le 2^{n+1}(2^n-1). }[/math]

Functions with Unbalanced Components

Let 𝐹 be an (𝑛,𝑛)-plateaued function with all components unbalanced. Then

[math]\displaystyle{ | \{ (a,b) \in (\mathbb{F}_2^n)^2 : a \ne b, F(a) = F(b)\}| \ge 2 \cdot (2^n-1), }[/math]

with equality if and only if 𝐹 is APN.

  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.