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 $F:{𝔽}_{2^n}\to {𝔽}_{2^n}$, the Boomerang Connectivity Table (BCT) is given by a $2^n\times 2^n$ table $T_F$,

$T_F(a,b)=|\{x\in {𝔽}_{2^n}:F^{-1}(F(x)+a)+F^{-1}(F(x+b)+a)=b\}|$.

The boomerang uniformity of $F$ is the maximal value, i.e. ${\beta }_F=\underset{a,b\in {𝔽}_{2^n}^{\ast }}{max}{T}_F(a,b)$

Main properties

For $F$ 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 $F^{\prime }$ an affine equivalent permutation, $F^{\prime }=A_2\circ F\circ A_1$, we have $T_{F^{\prime }}(a,b)=T_F(L_1(a),L_2^{-1}(b))$, with $L_i$ the linear part of $A_i$.
  • For the inverse we have $T_{F^{-1}}(a,b)=T_F(b,a)$.
• Relation with the differential uniformity: ${\delta }_F\le {\beta }_F$ and ${\delta }_F=2$ if and only if ${\beta }_F=2$.
• $T_F(a,b)=|\{(x,y):F(x+a)+F(y+a)=b,F(x)+F(y)=b\}|$.
• If $F$ is a power permutation, then ${\beta }_F=\underset{b\ne 0}{max}T(1,b)$.
• If $F$ is a quadratic permutation, then ${\delta }_F\le {\beta }_F\le {\delta }_F({\delta }_F-1)$.