Skip to Main content Skip to Navigation
Conference papers

Finite Field Power Permutations and Three-Valued Weil Sums of Binomials

Abstract : Let k be the finite field of characteristic p and order q = p e , and suppose that gcd(d, q − 1) = 1. Then the map x → x d is a permutation of k, known as a power permutation. If Tr is the absolute trace from k to the prime field F p , then x → Tr(x d) is a p-ary function that is of interest in differential cryptanalysis. The Walsh transform compares our p-ary function with all the F p-linear functionals, which have the form x → Tr(ax) with a ∈ F p. Thus the Walsh transform is used to determine the nonlinearity of our p-ary function. If we let ψ k (x) = e 2πiTr(x)/p be the canonical additive character of k, then the spectrum of the Walsh transform is given by the values of a Weil sum with ψ k applied to a binomial argument, W k,d (a) = x∈k ψ k (x d − ax), where k and d are fixed, and we let a run through k. In fact, since W k,d (0) = 0 trivially, our interest is in the distribution of values as a runs through k ×. The values of W k,d give not only the Walsh transform of a power permutation , but also to the cross-correlation spectrum of a pair of maximal linear recursive sequences of length q − 1 and relative decimation d, as well as the weight distribution of the dual of the cyclic code of length q −1 whose zeroes are two primitive elements α and α d of the field k. If d is a power of p modulo q − 1, then the canonical additive character ψ k has the same value when applied to the binomial x d − ax as it does when applied to the monomial (1 − a)x, and we obtain W k,d (1) = q and W k,d (a) = 0 for all a = 1. Thus the Weil sum can only take two distinct values, and we say that d is degenerate over k. In 1976, Helleseth proved that if d is nondegenerate over k, then W k,d assumes at least three values. We are interested in the case when Wk,d takes exactly three values for a ∈ k ×, in which case we say that Wk,d is three-valued. We shall examine all the known infinite families of fields k and exponents d that produce three-valued Weil sums. Then we shall indicate patterns, both conjectured and proved, that have been observed in the three-valued spectra. We review recent progress on these conjectures, and conclude with some open problems.
Document type :
Conference papers
Complete list of metadata
Contributor : Jean-Pierre Tillich <>
Submitted on : Friday, February 19, 2016 - 5:51:22 PM
Last modification on : Wednesday, July 24, 2019 - 4:02:06 PM


  • HAL Id : hal-01276697, version 1



Daniel J. Katz. Finite Field Power Permutations and Three-Valued Weil Sums of Binomials. Proceedings of the Ninth International Workshop on Coding and Cryptography 2015 WCC2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01276697⟩



Record views