Involutions over finite fields are permutations whose compositional inverses are themselves. Involutions especially over Fq with q is even have been used in many applications, including cryptography and coding theory. The explicit study of involutions (including their fixed points) has started with the paper (Charpin et al. IEEE Trans. Inf. Theory, 62(4), 2266–2276 2016) for binary fields and since then a lot of attention had been made in this direction following it; see for example, Charpin et al. (2016), Coulter and Mesnager (IEEE Trans. Inf. Theory, 64(4), 2979–2986, 2018), Fu and Feng (2017), Wang (Finite Fields Appl., 45, 422–427, 2017) and Zheng et al. (2019). In this paper, we study constructions of involutions over finite fields by proposing an involutory version of the AGW Criterion. We demonstrate our general construction method by considering polynomials of different forms. First, in the multiplicative case, we present some necessary conditions of f(x) = xrh(xs) over Fq to be involutory on Fq, where s∣(q − 1). Based on this, we provide three explicit classes of involutions of the form xrh(xq− 1) over Fq2. Recently, Zheng et al. (Finite Fields Appl., 56, 1–16 2019) found an equivalent relationship between permutation polynomials of g(x)qi−g(x)+cx+(1−c)δ and g(xqi−x+δ)+cx. The other part work of this paper is to consider the involutory property of these two classes of permutation polynomials, which fall into the additive case of the AGW criterion. On one hand, we reveal the relationship of being involutory between the form g(x)qi−g(x)+cx+(1−c)δ and the form g(xqi−x+δ)+cx over Fqm ; on the other hand, the compositional inverses of permutation polynomials of the form g(xqi−x+δ)+cx over Fqm are computed, where δ∈Fqm, g(x)∈Fqm[x] and integers m, i satisfy 1 ≤ i ≤ m − 1. In addition, a class of involutions of the form g(xqi−x+δ)+cx is constructed. Finally, we study the fixed points of constructed involutions and compute the number of all involutions with any given number of fixed points over Fq.

Additional Metadata
Keywords Compositional inverses, Finite fields, Fixed points, Involutions, Permutation polynomials
Persistent URL dx.doi.org/10.1007/s12095-019-00386-2
Journal Cryptography and Communications
Citation
Niu, T. (Tailin), Li, K. (Kangquan), Qu, L. (Longjiang), & Wang, Q. (2019). New constructions of involutions over finite fields. Cryptography and Communications. doi:10.1007/s12095-019-00386-2