APN trinomials and hexanomials

Abstract

In this paper we give a new family of APN trinomials of the form $X^{2^k+1}+({\mathsf{tr}}_m^n(X){)}^{2^k+1}$ on ${\mathbb{F}}_{2^n}$ where $\mathsf{gcd}(k,n)=1$ and $n=2m=4t$, and prove its important properties. The family satisfies for all $n=4t$ an interesting property of the Kim function which is, up to equivalence, the only known APN function equivalent to a permutation on ${\mathbb{F}}_{2^{2m}}$. As another contribution of the paper, we consider a family of hexanomials $g_{C,k}$ which was shown to be differentially $2^{\mathsf{gcd}(m,k)}$-uniform by Budaghyan and Carlet (2008) when a quadrinomial $P_{C,k}$ has no roots in a specific subgroup. In this paper, for all $(m,k)$ pairs, we characterize, construct and count all $C\in {\mathbb{F}}_{2^n}$ satisfying the condition. Bracken, Tan and Tan (2014) and Qu, Tan and Li (2014) constructed some elements $C$ satisfying the condition when $m\equiv 2\text{or}4(\mathrm{mod}6)$ and $m\equiv 0(\mathrm{mod}6)$ respectively, both requiring $\mathsf{gcd}(m,k)=1$. Bluher (2013) proved that such $C$ exists if and only if $k\ne m$ without characterizing, constructing or counting those $C$. To prove the results, we effectively use a Trace-$0$/Trace-$1$ (relative to the subfield ${\mathbb{F}}_{2^m}$) decomposition of ${\mathbb{F}}_{2^n}$.

19 pages; submitted Feb 12, 2014; updated Jul 29, 2014