Boomerang uniformity

From Boolean
Revision as of 08:46, 23 September 2019 by Ivi062 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Background and definitions

The Boomerang attack, introduced in 1999 by Wagner [1], is a cryptanalysis technique against block ciphers based on differential cryptanalysis. To study the resistance to this attack, Cid et al.[2] introduced the Boomerang Connectivity Table (BCT). Next, Boura and Canteaut[3] , 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].
  1. Wagner D. The boomerang attack.In Lars R. Knudsen, editor, FSE'99, vol. 1636 of LNCS, pp. 156-170. Springer, Heidelberg, March 1999
  2. 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
  3. Boura C., Canteaut A. On the boomerang uniformity of cryptographic Sboxes. IACR Transaction on Symmetric Cryptology, pp. 290-310, Sep 2018