Ambiguity and Deficiency of Permutations Over Finite Fields With Linearized Difference Map

作者：Panario Daniel^*; Sakzad Amin; Stevens Brett; Thomson David; Wang Qiang

来源：IEEE Transactions on Information Theory, 2013, 59(9): 5616-5626.

DOI：10.1109/TIT.2013.2262021

• Ambiguity
• deficiency
• Dembowski-Ostrom (DO) polynomials
• finite fields
• linearized polynomials
• nonlinearity
• permutation polynomials

The concepts of ambiguity and deficiency for a bijection on a finite Abelian group were recently introduced. In this paper, we present some further fundamental results on the ambiguity and deficiency of functions; in particular, we note that they are invariant under the well-known Carlet-Charpin-Zinoviev-equivalence, we obtain upper and lower bounds on the ambiguity and deficiency of differentially-uniform functions, and we give a lower bound on the nonlinearity of functions that achieve the lower bound of ambiguity and deficiency. In addition, we provide an explicit formula in terms of the ranks of matrices on the ambiguity and deficiency of a Dembowski-Ostrom (DO) polynomial, and using this technique, we find exact values for known cases of DO permutations with few terms. We also derive exact values for the ambiguities and deficiencies of DO permutations obtained from trace functions. The key relationship between the above polynomials is that they all have linearized difference map.

• 出版日期2013-9