Ivi062: Created page with "An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equa..."

2019-10-25T14:37:04Z

Created page with "An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equa..."

New page

An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equals 2𝑛-1-2𝑛/2-1.

Equivalently, 𝑓 is bent if
* 𝑊𝑓(𝑢) takes only the values ±2𝑛/2,
* 𝑊𝑓(𝑢)≡2𝑛/2 (mod 2𝑛/2+1),
* its distance to any affine function equals 2𝑛-1±2𝑛/2-1,
* for any nonzero element 𝑎 the Boolean function 𝐷𝑎𝑓(𝑥)=𝑓(𝑥+𝑎)⊕𝑓(𝑥) is balanced,
* for any 𝑥∈𝔽2𝑛, <math>\sum_{a,b\in\mathbb{F}_2^n}(-1)^{D_aD_bf(x)}=2^n</math>,
* the 2𝑛×2𝑛 matrix 𝐻=[(-1)𝑓(𝑥+𝑦)]𝑥,𝑦∈𝔽2𝑛 is a Hadamard matrix (i.e. 𝐻×𝐻𝑡=2𝑛𝐼, where 𝐼 is the identity matrix),
* the support of 𝑓 is a difference set of the elementary Abelian 2-group 𝔽2𝑛.

Bent functions are also called perfect nonlinear functions.

The dual of a bent 𝑓 function is also a bent function, where the dual is defined as
<center><math>W_f(u)=2^{n/2}(-1)^{\tilde{f}(u)},</math></center>
and its own dual is 𝑓 itself.

=Bent functions and algebraic degree=
* For 𝑛 even and at least 4 the algebraic degree of any bent function is at most 𝑛/2.
* The algebraic degree of a bent function and of its dual satisfy the following relation:
<center><math>n/2-d^\circ f\ge\frac{n/2-d^\circ\tilde{f}}{d^\circ\tilde{f}-1}</math></center>
* Obviously, no affine function can be bent.
* When 𝑓 is quadratic, then it is affine equivalent to the function
<center><math>x_1x_2\oplus x_3x_4\oplus\ldots\oplus x_{n-1}x_n\oplus\epsilon, (\epsilon\in\mathbb{F}_2).</math></center>
* The characterisation of cubic bent functions has been done for small dimensions (𝑛≤8).

=Constructions=
==The Maiorana-McFarland Construction==
For 𝑛=2𝑚, 𝔽2𝑛={(𝑥,𝑦) : 𝑥,𝑦∈𝔽2𝑚}, 𝑓 is of the form
<center><math>f(x,y)=x\cdot\pi(y)\oplus g(y),</math></center>
where 𝜋 is a permutation of 𝔽2𝑚 and 𝑔 is any 𝑚-variable Boolean function.
Any such function is bent (the bijectivity of 𝜋 is a necessary and sufficient condition).
The dual function is <math>\tilde{f}(x,y)=y\cdot\pi^{-1}(x)\oplus g(\pi^{-1}(x))</math>.

Such construction contains, up to affine equivalence, all quadratic bent functions and all bent functions in at most 6 variables.

Bent Boolean Functions - Revision history

Ivi062: Created page with "An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equa..."