Boomerang uniformity

Background and definitions

The Boomerang attack, introduced in 1999 by Wagner , is a cryptanalysis technique against block ciphers based on differential cryptanalysis. To study the resistance to this attack, Cid et al. introduced the Boomerang Connectivity Table (BCT). Next, Boura and Canteaut , introduced the notion of boomerang uniformity.

For a permutation [math]\displaystyle{ F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n} }[/math], the Boomerang Connectivity Table (BCT) is given by a [math]\displaystyle{ 2^n\times2^n }[/math] table [math]\displaystyle{ T_F }[/math],

[math]\displaystyle{ T_F(a,b)=|\{ x\in\mathbb{F}_{2^n} : F^{-1}(F(x)+a)+F^{-1}(F(x+b)+a)=b\}| }[/math].

The boomerang uniformity of [math]\displaystyle{ F }[/math] is the maximal value, i.e. [math]\displaystyle{ \beta_F=\max_{a,b\in\mathbb{F}^*_{2^n}} T_F(a,b) }[/math]

Main properties

For [math]\displaystyle{ F }[/math] a permutation, the following properties on the boomerang uniformity were proven.

• The boomerang uniformity is invariant for inverse and affine equivalence but not for EA- and CCZ-equivalence.
  • For [math]\displaystyle{ F' }[/math] an affine equivalent permutation, [math]\displaystyle{ F'=A_2\circ F\circ A_1 }[/math], we have [math]\displaystyle{ T_{F'}(a,b)=T_F(L_1(a),L_2^{-1}(b)) }[/math], with [math]\displaystyle{ L_i }[/math] the linear part of [math]\displaystyle{ A_i }[/math].
  • For the inverse we have [math]\displaystyle{ T_{F^{-1}}(a,b)=T_F(b,a) }[/math].
• Relation with the differential uniformity: [math]\displaystyle{ \delta_F\le\beta_F }[/math] and [math]\displaystyle{ \delta_F=2 }[/math] if and only if [math]\displaystyle{ \beta_F=2 }[/math].
• [math]\displaystyle{ T_F(a,b)=|\{ (x,y) : F(x+a)+F(y+a)=b,F(x)+F(y)=b \}| }[/math].
• If [math]\displaystyle{ F }[/math] is a power permutation, then [math]\displaystyle{ \beta_F=\max_{b\neq0}T(1,b) }[/math].
• If [math]\displaystyle{ F }[/math] is a quadratic permutation, then [math]\displaystyle{ \delta_F\le\beta_F\le\delta_F(\delta_F-1) }[/math].