Plateaued Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
(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 [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. [math]\displaystyle{ 0 }[/math] and [math]\displaystyle{ \pm \mu }[/math] for some positive ineger [math]\displaystyle{ \mu }[/math] called the amplitude of [math]\displaystyle{ f }[/math].

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if [math]\displaystyle{ F }[/math] is an [math]\displaystyle{ (n,m) }[/math]-function, we say that [math]\displaystyle{ F }[/math] is plateaued if all its component functions [math]\displaystyle{ u \cdot F }[/math] for [math]\displaystyle{ u \ne 0 }[/math] are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that [math]\displaystyle{ 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

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 [math]\displaystyle{ r }[/math] and [math]\displaystyle{ s }[/math] are any positive integers, [math]\displaystyle{ n = r + s }[/math], [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 [math]\displaystyle{ (a,b) }[/math]. If [math]\displaystyle{ \phi }[/math] is injective, resp. takes each value in its image set two times, then [math]\displaystyle{ f_{\phi,h} }[/math] is plateaued of amplitude [math]\displaystyle{ 2^r }[/math], resp. [math]\displaystyle{ 2^{r+1} }[/math].

  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.