Plateaued Functions: Difference between revisions
(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...") |
No edit summary |
||
| 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>. | |||
Revision as of 12:57, 7 February 2019
Background and Definition
A Boolean function 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 : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2} is said to be plateaued if its Walsh transform takes at most three distinct values, viz. 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 0} and 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 \pm \mu} for some positive ineger 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 \mu} called the amplitude of 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} .
This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if 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 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, we say that 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 if all its component functions 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 u \cdot F} 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 u \ne 0} are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that 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.
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 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_{\phi,h}} of the form
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 x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s} , where 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 r} and 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 s} are any positive integers, 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 = r + s} , 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 \phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r} is arbitrary and 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 h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2} is any Boolean function.
The Walsh transform of 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_{\phi,h}} takes the value
at 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)} . If 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 \phi} is injective, resp. takes each value in its image set two times, 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_{\phi,h}} is plateaued of amplitude 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 2^r} , resp. 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 2^{r+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.
