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:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{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 \mathbb {F} _{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}=\max _{a,b\in \mathbb {F} _{2^{n}}^{*}}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'$ an affine equivalent permutation, $F'=A_{2}\circ F\circ A_{1}$, we have $T_{F'}(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}\leq \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}=\max _{b\neq 0}T(1,b)$.
• If $F$ is a quadratic permutation, then $\delta _{F}\leq \beta _{F}\leq \delta _{F}(\delta _{F}-1)$.

Wagner D. The boomerang attack.In Lars R. Knudsen, editor, FSE'99, vol. 1636 of LNCS, pp. 156-170. Springer, Heidelberg, March 1999

Cid C., Huang T., Peyrin T., Sasaki Y., Song L. Boomerang connectivity table: A new cryptanalysis tool. EUROCRYPT 2018, Part II, vol. 10821 of LNCS, pp. 683-714. Springer, Heidelberg, 2018

Boura C., Canteaut A. On the boomerang uniformity of cryptographic Sboxes. IACR Transaction on Symmetric Cryptology, pp. 290-310, Sep 2018