Difference between revisions of "Almost Perfect Nonlinear (APN) Functions"

From Boolean Functions
Jump to: navigation, search
m
 
(3 intermediate revisions by one other user not shown)
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. 𝐹 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 13: 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 19: 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 25: 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 37: 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 48: 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.

Latest revision as of 13:54, 11 October 2019

Background and definition

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 𝐹 : 𝔽2𝑛 β†’ 𝔽2𝑛 is usually given through the values

which, for π‘Žβ‰ 0, express the number of input pairs with difference π‘Ž that map to a given 𝑏. The existence of a pair with a high value of Δ𝐹(π‘Ž,𝑏) makes the function 𝐹 vulnerable to differential cryptanalysis. This motivates the definition of differential uniformity as

which clearly satisfies Δ𝐹 β‰₯ 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. 𝐹 is said to be strongly-plateuaed if, for every π‘Ž and every 𝑣, the size of the set does not depend on π‘₯, or, equivalently, the size of the set does not depend on π‘₯.

Characterizations

Walsh transform[1]

Any (𝑛,π‘š)-function 𝐹 satisfies

with equality characterizing APN functions.

In particular, for (𝑛,𝑛)-functions we have

with equality characterizing APN functions.

Sometimes, it is more convenient to sum through all 𝑏 ∈ 𝔽2π‘š instead of just the nonzero ones. In this case, the inequality for (𝑛,π‘š)-functions becomes

and the particular case for (𝑛,𝑛)-functions becomes

with equality characterizing APN functions in both cases.

Autocorrelation functions of the directional derivatives [2]

Given a Boolean function 𝑓 : 𝔽2𝑛 β†’ 𝔽2, the autocorrelation function of 𝑓 is defined as

Any (𝑛,𝑛)-function 𝐹 satisfies

for any π‘Ž ∈ 𝔽*2𝑛 . Equality occurs if and only if is APN.

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

for .

Then any (𝑛,𝑛) function 𝐹 satisfies

and equality occurs if and only if 𝐹 is APN.

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

  1. ↑ 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
  2. ↑ 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