Plateaued Functions - Revision history

Ivi062 at 16:05, 5 November 2019

2019-11-05T16:05:58Z

Ivi062 at 15:53, 5 November 2019

2019-11-05T15:53:31Z

← Older revision		Revision as of 15:53, 5 November 2019
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. ~~<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>~~.		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 ==

Nikolay at 21:36, 8 February 2019

2019-02-08T21:36:56Z

@@ Line 155: / Line 155: @@
 = Characterization of APN among Plateaued Functions =
-== Deciding APN-ness of 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 <math>F</math>. More precisely, a plateuaed <math>(n,n)</math> function <math>F</math> is APN if and only if the equation
@@ Line 170: / Line 170: @@
 <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>

Nikolay at 21:28, 8 February 2019

2019-02-08T21:28:55Z

← Older revision		Revision as of 21:28, 8 February 2019
Line 152:		Line 152:

	with equality if and only if <math>F</math> is plateuaed.		with equality if and only if <math>F</math> is plateuaed.

			= Characterization of APN among Plateaued Functions =

			== Deciding APN-ness of Plateaued Functions ==

			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 <math>F</math>. More precisely, a plateuaed <math>(n,n)</math> function <math>F</math> 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 <math>F</math> is a plateaued <math>(n,n)</math> function with <math>F(0) = 0</math>. Then <math>F</math> 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>

Nikolay at 15:28, 8 February 2019

2019-02-08T15:28:48Z

← Older revision		Revision as of 15:28, 8 February 2019
Line 106:		Line 106:

	<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>		<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 <math>(n,m)</math>-function <math>F</math> 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, <math>F</math> 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 <math>(n,m)</math>-function <math>F</math> 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, <math>F</math> is plateaued with single amplitude if and only if the two sums above do not depend on <math>u</math> for <math>u \ne 0</math>.

			=== Third Characterization ===

			Any Boolean function <math>f</math> 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 <math>f</math> is plateuaed.

			Any <math>(n,m)</math>-function <math>F</math> 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 <math>F</math> is plateuaed.

			In addition, every <math>(n,m)</math>-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 <math>F</math> is plateuaed.

Nikolay at 19:11, 7 February 2019

2019-02-07T19:11:11Z

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

Nikolay at 18:53, 7 February 2019

2019-02-07T18:53:11Z

← Older revision		Revision as of 18:53, 7 February 2019
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>.

Nikolay at 12:57, 7 February 2019

2019-02-07T12:57:13Z

← Older revision		Revision as of 12:57, 7 February 2019
Line 21:		Line 21:
	== Primary constructons ==		== Primary constructons ==

	=== Maiorana-MacFarland Functions ===		=== Generalization of the Maiorana-MacFarland Functions <ref name="camion1992">Camion P, Carlet C, Charpin P, Sendrier N. On Correlation-immune functions. InAdvances in Cryptology—CRYPTO’91 1992 (pp. 86-100). Springer Berlin/Heidelberg.</ref> ===

			The Maiorana-MacFarland class of bent functions can be generalized into the class of functions <math>f_{\phi,h}</math> of the form

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

			The Walsh transform of <math>f_{\phi,h}</math> takes the value

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

Nikolay: Created page with "= 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 t..."

2019-02-07T12:47:01Z

Created page with "= 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 t..."

New page

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

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

== 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 ==

=== Maiorana-MacFarland Functions ===