Almost Perfect Nonlinear (APN) Functions: Difference between revisions

From Boolean
← Older editNewer edit →

Nikolay (talk | contribs)

2 user groups
318 edits
No edit summary
No edit summary
Line 11: Line 11:
= Characterizations =
= Characterizations =


== Autocorrelation functions of the directional derivatives ==
== Autocorrelation functions of the directional derivatives <ref name="bercanchalai2006"> Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, ''On Almost Perfect Nonlinear Functions Over GF(2^n)'', IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70</ref> ==


Given a Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math>, the ''autocorrelation function'' of <math>f</math> is defined as
Given a Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math>, the ''autocorrelation function'' of <math>f</math> is defined as
Line 19: Line 19:
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div>
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}} \mathcal{F}(D_af_\lambda) = 2^{2n+1}</math></div>
for any <math>a \in \mathbb{F}_{2^n}^*</math>. Equality occurs if and only if <math>F</math> is APN.
for any <math>a \in \mathbb{F}_{2^n}^*</math>. Equality occurs if and only if <math>F</math> is APN.
This allows APN functions to be characterized in terms of the ''sum-of-square-indicator'' <math>\nu(f)</math> defined as
<div><math>\nu(f) = \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^2(D_aF) = 2^{-n} \sum_{a \in \mathbb{F}_{2^n}} \mathcal{F}^4(f + \varphi_a)</math></div>
for <math>\varphi_a(x) = {\rm Tr}(ax)</math>.
Then any <math>(n,n)</math> function <math>F</math> satisfies
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}</math></div>
and equality occurs if and only if <math>F</math> is APN.
Similar techniques can be used to characterize permutations and APN functions with plateaued components.

Revision as of 10:50, 15 January 2019

Background and definition

Almost perfect nonlinear (APN) functions are the class of (n,n) Vectorial Boolean Functions that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function F is efficient when fixing some difference δ and computing the output of F for all pairs of inputs (x1,x2) whose difference is δ produces output pairs with a difference distribution that is far away from uniform.

The formal definition of an APN function F:𝔽2n→𝔽2n is usually given through the values

ΔF(a,b)=|{x∈𝔽2n:F(x)+F(a+x)=b}|

which, for a≠0, express the number of input pairs with difference a that map to a given b. The existence of a pair (a,b)∈𝔽2n∗×𝔽2n with a high value of ΔF(a,b) makes the function F vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

ΔF=max⁡{ΔF(a,b):a∈𝔽2n∗,b∈𝔽2n}

which clearly satisfies ΔF≥2 for any function F. The functions meeting this lower bound are called almost perfect nonlinear (APN).

Characterizations

Autocorrelation functions of the directional derivatives [1]

Given a Boolean function f:𝔽2n→𝔽2, the autocorrelation function of f is defined as

ℱ(f)=∑x∈𝔽2n(−1)f(x)=2n−2wt(f).

Any (n,n)-function F satisfies

∑λ∈𝔽2nℱ(Dafλ)=22n+1

for any a∈𝔽2n∗. Equality occurs if and only if F is APN.

This allows APN functions to be characterized in terms of the sum-of-square-indicator ν(f) defined as

ν(f)=∑a∈𝔽2nℱ2(DaF)=2−n∑a∈𝔽2nℱ4(f+φa)

for φa(x)=Tr(ax).

Then any (n,n) function F satisfies

∑λ∈𝔽2n∗ν(fλ)≥(2n−1)22n+1

and equality occurs if and only if F is APN.

Similar techniques can be used to characterize permutations and APN functions with plateaued components.

  1. ↑ Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, On Almost Perfect Nonlinear Functions Over GF(2^n), IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70
Retrieved from "https://boolean.wiki.uib.no/index.php?title=Almost_Perfect_Nonlinear_(APN)_Functions&oldid=114"