# Difference between revisions of "Plateaued Functions"

(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...") |
|||

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 14:57, 7 February 2019

## Contents

# Background and Definition

A Boolean function is said to be *plateaued* if its Walsh transform takes at most three distinct values, viz. 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 are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that 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 of the form

for , where and are any positive integers, , is arbitrary and is any Boolean function.

The Walsh transform of takes the value

at . If is injective, resp. takes each value in its image set two times, then is plateaued of amplitude , resp. .

- ↑ Camion P, Carlet C, Charpin P, Sendrier N. On Correlation-immune functions. InAdvances in Cryptology—CRYPTO’91 1992 (pp. 86-100). Springer Berlin/Heidelberg.