Almost perfect nonlinear trinomials and hexanomials

In this paper we give a new family of almost perfect nonlinear (APN) trinomials of the form X2k+1+(trmn(X))2k+1 on F2nF2n where gcd(k,n)=1gcd(k,n)=1 and n=2m=4tn=2m=4t, and prove its important properties. The family satisfies for all n=4tn=4t an interesting property of the Kim function which is, up to equivalence, the only known APN function equivalent to a permutation on F22mF22m. As another contribution of the paper, we consider a family of hexanomials gC,kgC,k which was shown to be differentially 2gcd(m,k)2gcd(m,k)-uniform by Budaghyan and Carlet (2008) when a quadrinomial PC,kPC,k has no roots in a specific subgroup. In this paper, for all (m,k)(m,k) pairs, we characterize, construct and count all C∈F2nC∈F2n satisfying the condition. Bracken, Tan and Tan (2014) and Qu, Tan and Li (2014) constructed some elements C   satisfying the condition when m≡2 or 4(mod 6) and m≡0(mod 6) respectively, both requiring gcd(m,k)=1gcd(m,k)=1. Bluher (2013) proved that such C   exists if and only if k≠mk≠m without characterizing, constructing or counting those C  . To prove the results, we effectively use a Trace-0/Trace-1 (relative to the subfield F2mF2m) decomposition of F2nF2n.