On the inverses of Kasami and Bracken-Leander exponents

Abstract

We explicitly determine the binary representation of the inverse of all Kasami exponents $K_r=2^{2r}-2^r+1$ modulo $2^n-1$ for all possible values of $n$ and $r$. This includes as an important special case the APN Kasami exponents with $\gcd (r,n)=1$. As a corollary, we determine the algebraic degree of the inverses of the Kasami functions. In particular, we show that the inverse of an APN Kasami function on ${\mathbb{F}}_{2^n}$ always has algebraic degree $\frac{n+1}{2}$ if $n\equiv 0(\mathrm{mod}3)$. For $n\not\equiv 0(\mathrm{mod}3)$ we prove that the algebraic degree is bounded from below by $\frac{n}{3}$. We consider Kasami exponents whose inverses are quadratic exponents or Kasami exponents. We also determine the binary representation of the inverse of the Bracken-Leander exponent $B{L}_r=2^{2r}+2^r+1$ modulo $2^n-1$ where $n=4r$ and $r$ odd. We show that the algebraic degree of the inverse of the Bracken-Leander function is $\frac{n+2}{2}$.

Added a section on Gold exponents and an illustratory example of the method, and incorporated reviewer's comments. Accepted for publication in Designs, Codes and Cryptography