Almost Perfect Nonlinear (APN) Functions - Revision history

Ivi062 at 12:54, 11 October 2019

2019-10-11T12:54:07Z

← Older revision		Revision as of 12:54, 11 October 2019
Line 1:		Line 1:
	= Background and definition =		= Background and definition =

	Almost perfect nonlinear (APN) functions are the class of ~~<math>~~(n,n)~~</math>~~ [[Vectorial Boolean Functions]] that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function ~~<math>F</math>~~ is efficient when fixing some difference ~~<math>\delta</math>~~ and computing the output of ~~<math>F</math>~~ for all pairs of inputs ~~<math>~~(~~x_1~~,~~x_2~~)~~</math>~~ whose difference is ~~<math>\delta</math>~~ produces output pairs with a difference distribution that is far away from uniform.		Almost perfect nonlinear (APN) functions are the class of (𝑛,𝑛) [[Vectorial Boolean Functions]] that provide optimum resistance to against differential attack. Intuitively, the differential attack against a given cipher incorporating a vectorial Boolean function 𝐹 is efficient when fixing some difference 𝛿 and computing the output of 𝐹 for all pairs of inputs (𝑥₁,𝑥₂) whose difference is 𝛿 produces output pairs with a difference distribution that is far away from uniform.

	The formal definition of an APN function <~~math~~>~~F : \mathbb{F}_{~~2~~^n} \rightarrow \mathbb{F}_{~~2~~^n}~~</~~math~~> is usually given through the values		The formal definition of an APN function 𝐹 : 𝔽<sub>2<sup>𝑛</sup></sub> → 𝔽<sub>2<sup>𝑛</sup></sub> is usually given through the values
	<div><math>\Delta_F(a,b) = \| \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}\|</math></div>		<div><math>\Delta_F(a,b) = \| \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}\|</math></div>
	which, for ~~<math>a \ne 0</math>~~, express the number of input pairs with difference ~~<math>a</math>~~ that map to a given ~~<math>b</math>~~. The existence of a pair <math>(a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}</math> with a high value of <~~math~~>~~\Delta_F~~(a,b)</~~math~~> makes the function ~~<math>F</math>~~ vulnerable to differential cryptanalysis. This motivates the definition of ''differential uniformity'' as		which, for 𝑎≠0, express the number of input pairs with difference 𝑎 that map to a given 𝑏. The existence of a pair <math>(a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}</math> with a high value of Δ<sub>𝐹(𝑎,𝑏)</sub> makes the function 𝐹 vulnerable to differential cryptanalysis. This motivates the definition of ''differential uniformity'' as
	<div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div>		<div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div>
	which clearly satisfies <~~math~~>~~\Delta_F \ge 2~~</~~math~~> for any function ~~<math>F</math>~~. The functions meeting this lower bound are called ''almost perfect nonlinear (APN)''.		which clearly satisfies Δ<sub>𝐹</sub> ≥ 2 for any function 𝐹. The functions meeting this lower bound are called ''almost perfect nonlinear (APN)''.

	The characterization by means of the derivatives below suggests the following definition: a v.B.f. ~~<math>F</math>~~ is said to be ''strongly-plateuaed'' if, for every ~~<math>a</math>~~ and every ~~<math>v</math>~~, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on ~~<math>x</math>~~, or, equivalently, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}</math> does not depend on ~~<math>x</math>~~.		The characterization by means of the derivatives below suggests the following definition: a v.B.f. 𝐹 is said to be ''strongly-plateuaed'' if, for every 𝑎 and every 𝑣, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on 𝑥, or, equivalently, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}</math> does not depend on 𝑥.

	= Characterizations =		= Characterizations =
Line 15:		Line 15:
	== Walsh transform<ref name="chavau1994">Florent Chabaud, Serge Vaudenay, ''Links between differential and linear cryptanalysis'', Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg</ref> ==		== Walsh transform<ref name="chavau1994">Florent Chabaud, Serge Vaudenay, ''Links between differential and linear cryptanalysis'', Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg</ref> ==

	Any ~~<math>~~(n,m)~~</math>~~-function ~~<math>F</math>~~ satisfies		Any (𝑛,𝑚)-function 𝐹 satisfies

	<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n})</math></div>		<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n})</math></div>
Line 21:		Line 21:
	with equality characterizing APN functions.		with equality characterizing APN functions.

	In particular, for ~~<math>~~(n,n)~~</math>~~-functions we have		In particular, for (𝑛,𝑛)-functions we have

	<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)</math></div>		<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)</math></div>
Line 27:		Line 27:
	with equality characterizing APN functions.		with equality characterizing APN functions.

	Sometimes, it is more convenient to sum through all <~~math~~>~~b \in \mathbb{F}_{~~2~~^m}~~</~~math~~> instead of just the nonzero ones. In this case, the inequality for ~~<math>~~(n,m)~~</math>~~-functions becomes		Sometimes, it is more convenient to sum through all 𝑏 ∈ 𝔽<sub>2<sup>𝑚</sup></sub> instead of just the nonzero ones. In this case, the inequality for (𝑛,𝑚)-functions becomes

	<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)</math></div>		<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)</math></div>

	and the particular case for ~~<math>~~(n,n)~~</math>~~-functions becomes		and the particular case for (𝑛,𝑛)-functions becomes

	<div><math>\sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)</math></div>		<div><math>\sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)</math></div>
Line 39:		Line 39:
	== 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> ==		== 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 𝑓 : 𝔽<sub>2<sup>𝑛</sup></sub> → 𝔽<sub>2</sub>, the ''autocorrelation function'' of 𝑓 is defined as
	<div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div>		<div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div>

	Any ~~<math>~~(n,n)~~</math>~~-function ~~<math>F</math>~~ satisfies		Any (𝑛,𝑛)-function 𝐹 satisfies
	<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 𝑎 ∈ 𝔽*<sub>2<sup>𝑛</sup></sub> . 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		This allows APN functions to be characterized in terms of the ''sum-of-square-indicator'' <math>\nu(f)</math> defined as
Line 50:		Line 50:
	for <math>\varphi_a(x) = {\rm Tr}(ax)</math>.		for <math>\varphi_a(x) = {\rm Tr}(ax)</math>.

	Then any ~~<math>~~(n,n)~~</math>~~ function ~~<math>F</math>~~ satisfies		Then any (𝑛,𝑛) function 𝐹 satisfies
	<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \nu(f_\lambda) \ge (2^n-1)2^{2n+1}</math></div>		<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.		and equality occurs if and only if 𝐹 is APN.

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

Nikolay at 18:58, 7 February 2019

2019-02-07T18:58:37Z

← Older revision		Revision as of 18:58, 7 February 2019
Line 55:		Line 55:

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

	~~= Characterization of Plateaued Functions =~~

	== Characterization by the Derivatives <ref name="carletPlateaued">Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.</ref> ==

	~~=== First characterization ===~~

	~~Using the fact that two integer-valued functions over <math>\mathbb{F}_2^m</math> are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.~~

	~~Let <math>F</math> be an <math>(n,m)</math>-function. Then:~~

	~~- <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set~~

	~~<div><math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math></div>~~

	~~does not depend on <math>x</math>;~~

	~~- <math>F</math> is plateaued with single amplitude if and only if the size of the above set depends neither on <math>x</math> nor on <math>v</math> when <math>v \ne 0</math>.~~

	~~Moreover:~~

	- for any <math>(n,m)</math>-function <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals the value distribution of <math>D_aF(b) + D_aF(x)</math> as <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>;

	~~- if two plateuaed functions have the same distribution, then for every <math>u</math>, their component functions at <math>u</math> have the same amplitude.~~

	~~=== Characterization in the Case of Unbalanced Components ===~~

	~~Let <math>F</math> be an <math>(n,m)</math>-function. Then <math>F</math> is plateuaed with all components unbalanced if and only if, for every <math>v,x \in \mathbb{F}_2^n</math>, we have~~

	~~<div><math> \| \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} \| = \| \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \} \|.</math></div>~~

	~~Moreover, <math>F</math> is plateuaed with single amplitude if and only if, in addition, this value does not depend on <math>v</math> for <math>v \ne 0</math>.~~

	~~=== Properties of Strongly-Plateaued Functions ===~~

	A Boolean function is strongly-plateaued if and only if its partially-bent. A v.B.f. is strongly-plateaued if and only if all of its component functions are partially-bent. In particular, bent and quadratic Boolean and vectorial functions are strongly-plateaued.

	~~The image set <math>{\rm Im}(D_aF)</math> of any derivative of a strongly-plateaued function <math>F</math> is an affine space.~~

	~~=== Characterization by the Auto-Correlation Functions ===~~

Nikolay at 13:29, 7 February 2019

2019-02-07T13:29:46Z

@@ Line 8: / Line 8: @@
 <div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div>
 which clearly satisfies <math>\Delta_F \ge 2</math> for any function <math>F</math>. The functions meeting this lower bound are called ''almost perfect nonlinear (APN)''.
 = Characterizations =
@@ Line 85: / Line 87: @@
 Moreover, <math>F</math> is plateuaed with single amplitude if and only if, in addition, this value does not depend on <math>v</math> for <math>v \ne 0</math>.

Nikolay at 13:21, 7 February 2019

2019-02-07T13:21:41Z

← Older revision		Revision as of 13:21, 7 February 2019
Line 53:		Line 53:

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

			= Characterization of Plateaued Functions =

			== Characterization by the Derivatives <ref name="carletPlateaued">Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.</ref> ==

			=== First characterization ===

			Using the fact that two integer-valued functions over <math>\mathbb{F}_2^m</math> are equal precisely when their Fourier transforms are equal, one can obtain the following characterization.

			Let <math>F</math> be an <math>(n,m)</math>-function. Then:

			- <math>F</math> is plateaued if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set

			<div><math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math></div>

			does not depend on <math>x</math>;

			- <math>F</math> is plateaued with single amplitude if and only if the size of the above set depends neither on <math>x</math> nor on <math>v</math> when <math>v \ne 0</math>.

			Moreover:

			- for any <math>(n,m)</math>-function <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals the value distribution of <math>D_aF(b) + D_aF(x)</math> as <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>;

			- if two plateuaed functions have the same distribution, then for every <math>u</math>, their component functions at <math>u</math> have the same amplitude.

			=== Characterization in the Case of Unbalanced Components ===

			Let <math>F</math> be an <math>(n,m)</math>-function. Then <math>F</math> is plateuaed with all components unbalanced if and only if, for every <math>v,x \in \mathbb{F}_2^n</math>, we have

			<div><math> \| \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \} \| = \| \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \} \|.</math></div>

			Moreover, <math>F</math> is plateuaed with single amplitude if and only if, in addition, this value does not depend on <math>v</math> for <math>v \ne 0</math>.

Nikolay at 09:01, 18 January 2019

2019-01-18T09:01:45Z

← Older revision		Revision as of 09:01, 18 January 2019
Line 13:		Line 13:
	== Walsh transform<ref name="chavau1994">Florent Chabaud, Serge Vaudenay, ''Links between differential and linear cryptanalysis'', Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg</ref> ==		== Walsh transform<ref name="chavau1994">Florent Chabaud, Serge Vaudenay, ''Links between differential and linear cryptanalysis'', Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg</ref> ==

	Any <math>(p,q)</math>-function <math>F</math> satisfies		Any <math>(n,m)</math>-function <math>F</math> satisfies

	<div><math>\sum_{a \in \mathbb{F}_{2^p}, b \in \mathbb{F}_{2^q}^*} W_F^4(a,b) \ge 2^{2p}(3 \cdot 2^{p+q} - 2^{q+1} - 2^{2p})</math></div>		<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}^*} W_F^4(a,b) \ge 2^{2n}(3 \cdot 2^{n+m} - 2^{m+1} - 2^{2n})</math></div>

	with equality characterizing APN functions.		with equality characterizing APN functions.

			In particular, for <math>(n,n)</math>-functions we have

			<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^n}^*} W_F^4(a,b) \ge 2^{3n+1}(2^n-1)</math></div>

			with equality characterizing APN functions.

			Sometimes, it is more convenient to sum through all <math>b \in \mathbb{F}_{2^m}</math> instead of just the nonzero ones. In this case, the inequality for <math>(n,m)</math>-functions becomes

			<div><math>\sum_{a \in \mathbb{F}_{2^n}, b \in \mathbb{F}_{2^m}} W_F^4(a,b) \ge 2^{2n + m}(3 \cdot 2^n - 2)</math></div>

			and the particular case for <math>(n,n)</math>-functions becomes

			<div><math>\sum_{a,b \in \mathbb{F}_{2^n}} W_F^4(a,b) \ge 2^{3n+1}(3 \cdot 2^{n-1} - 1)</math></div>

			with equality characterizing APN functions in both cases.

	== 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> ==		== 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> ==

Nikolay at 08:42, 18 January 2019

2019-01-18T08:42:28Z

← Older revision		Revision as of 08:42, 18 January 2019
Line 10:		Line 10:

	= Characterizations =		= Characterizations =

			== Walsh transform<ref name="chavau1994">Florent Chabaud, Serge Vaudenay, ''Links between differential and linear cryptanalysis'', Workshop on the Theory and Application of Cryptographic Techniques, 1994 May 9, pp. 356-365, Springer, Berlin, Heidelberg</ref> ==

			Any <math>(p,q)</math>-function <math>F</math> satisfies

			<div><math>\sum_{a \in \mathbb{F}_{2^p}, b \in \mathbb{F}_{2^q}^*} W_F^4(a,b) \ge 2^{2p}(3 \cdot 2^{p+q} - 2^{q+1} - 2^{2p})</math></div>

			with equality characterizing APN functions.


	== 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> ==		== 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> ==

Nikolay at 10:50, 15 January 2019

2019-01-15T10:50:11Z

← Older revision		Revision as of 10:50, 15 January 2019
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.

Nikolay at 10:00, 15 January 2019

2019-01-15T10:00:05Z

← Older revision		Revision as of 10:00, 15 January 2019
Line 10:		Line 10:

	= Characterizations =		= Characterizations =

			== Autocorrelation functions of the directional derivatives ==

			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
			<div><math>\mathcal{F}(f) = \sum_{x \in \mathbb{F}_{2^n}} (-1)^{f(x)} = 2^n - 2wt(f).</math></div>

			Any <math>(n,n)</math>-function <math>F</math> satisfies
			<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.

Nikolay: Created page with "= Background and definition = Almost perfect nonlinear (APN) functions are the class of $(n,n)$ Vectorial Boolean Functions that provide optimum resistance to..."

2019-01-15T09:22:05Z

Created page with "= Background and definition = Almost perfect nonlinear (APN) functions are the class of <math>(n,n)</math> Vectorial Boolean Functions that provide optimum resistance to..."

New page

= Background and definition =

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

The formal definition of an APN function <math>F : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}</math> is usually given through the values
<div><math>\Delta_F(a,b) = | \{ x \in \mathbb{F}_{2^n} : F(x) + F(a+x) = b \}|</math></div>
which, for <math>a \ne 0</math>, express the number of input pairs with difference <math>a</math> that map to a given <math>b</math>. The existence of a pair <math>(a,b) \in \mathbb{F}_{2^n}^* \times \mathbb{F}_{2^n}</math> with a high value of <math>\Delta_F(a,b)</math> makes the function <math>F</math> vulnerable to differential cryptanalysis. This motivates the definition of ''differential uniformity'' as
<div><math>\Delta_F = \max \{ \Delta_F(a,b) : a \in \mathbb{F}_{2^n}^*, b \in \mathbb{F}_{2^n} \}</math></div>
which clearly satisfies <math>\Delta_F \ge 2</math> for any function <math>F</math>. The functions meeting this lower bound are called ''almost perfect nonlinear (APN)''.

= Characterizations =