Differential uniformity

From Boolean
Revision as of 09:52, 5 September 2019 by Ivi062 (talk | contribs) (Created page with "Given a vectorial Boolean function <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^m}</math>, it is called differentially <math>\delta</math>-uniform if the equation <math>F...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Given a vectorial Boolean function [math]\displaystyle{ F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^m} }[/math], it is called differentially [math]\displaystyle{ \delta }[/math]-uniform if the equation [math]\displaystyle{ F(x+a)-F(x)=b }[/math] admits at most [math]\displaystyle{ \delta }[/math] solutions for every non-zero [math]\displaystyle{ a\in\mathbb{F}_{2^n} }[/math] and [math]\displaystyle{ b\in\mathbb{F}_{2^m} }[/math].

This definition can be generalized to the case of functions [math]\displaystyle{ F:\mathbb{F}_{p^n}\rightarrow\mathbb{F}_{p^m} }[/math]. Functions with the smallest value for [math]\displaystyle{ \delta }[/math] contribute an optimal resistance to the differential attack.

The smallest possible value is [math]\displaystyle{ \delta=p^{n-m} }[/math], such functions are called perfect nonlinear (PN) and they exist only for [math]\displaystyle{ p }[/math] odd and [math]\displaystyle{ m\le n/2 }[/math]. (see also planar functions)

For [math]\displaystyle{ p=2 }[/math] and [math]\displaystyle{ m=n }[/math] the smallest value is [math]\displaystyle{ \delta=2 }[/math] and such optimal funtions are called almost perfect nonlinear (APN).

Differential uniformity is invariant under affine, EA- and CCZ-equivalence.