Plateaued Functions

From Boolean
Revision as of 12:47, 7 February 2019 by Nikolay (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

Maiorana-MacFarland Functions