Constructions of Two Classes of Permutation Polynomials

  • Chenfan Huang China University of Mining and Technology
  • Shixiong Xia
  • Fengrong Zhang
  • Yong Zhou
Keywords: Boolean function, bent function, linear structure, permutation polynomial, linearized polynomial, Trace


In this paper, we first investigate the constructions of permutation polynomials of the shape  over. A mapping function which transforms a Boolean function on n variables to a univariate function over  is provided. On basis of the mapping function, we put forward two methods for constructing two classes of univariate functions over  . Further, two classes of permutation polynomials of the shape can be obtained using the two classes of univariate functions. At last, based on the one-to-one correspondence between Boolean permutations and Maiorana-McFarland’s (M-M) bent functions, we propose an algorithm to compute the algebraic normal form (ANF) of a 2k-variable M-M bent function from its truth-table. The complexity of this algorithm is much smaller than that of the Butterfly algorithm which is directly used to compute the ANF of a 2k-variable M-M bent function from its truth-table.


Download data is not yet available.


Zhang, F., Wei, Y., Pasalic, E., & Xia, S. (2018). Large sets of disjoint spectra plateaued functions

inequivalent to partially linear functions. IEEE Transactions on Information Theory, 64(4), 2987-2999.

Pasalic, E., Hodi, S., Zhang, F., & Wei, Y. (2018). Bent functions from nonlinear permutations and

conversely. Cryptography and Communications, 1-19.

Wei, Y., Pasalic, E., Zhang, F., & Hodi, S. (2017). Efficient probabilistic algorithm for estimating the

algebraic properties of Boolean functions for large n. Information Sciences, 402, 91-104.

Zha, Z., Hu, L., & Zhang, Z. (2018). New results on permutation polynomials of the form (x p m x+

) s+ x p m+ x over p 2m. Cryptography and Communications, 10(3), 567-578.

Xu, X., Li, C., Zeng, X., & Helleseth, T. (2018). Constructions of complete permutation polynomials.

Designs, Codes and Cryptography, 86(12), 2869-2892.

Wang, Y., Zha, Z., & Zhang, W. (2018). Six new classes of permutation trinomials over F33k. Applicable

Algebra in Engineering, Communication and Computing, 29(6), 479-499.

Zhang, F., Hu, Y., Xie, M., Gao, J., & Wang, Q. (2012). Constructions of cryptographically significant

boolean permutations. Appl. Math, 6(1), 117-123.

Zha, Z., & Hu, L. (2012). Two classes of permutation polynomials over finite fields. Finite Fields and

Their Applications, 18(4), 781-790.

Li, N., Helleseth, T., & Tang, X. (2013). Further results on a class of permutation polynomials over

finite fields. Finite Fields and Their Applications, 22, 16-23.

Tu, Z., Zeng, X., & Hu, L. (2014). Several classes of complete permutation polynomials. Finite Fields

and Their Applications, 25, 182-193.

Charpin, P., & Kyureghyan, G. M. (2008, September). On a Class of Permutation Polynomials over

F2n. In International Conference on Sequences and Their Applications (pp. 368-376). Springer, Berlin,


Dubuc, S. (2001). Characterization of linear structures. Designs, Codes and Cryptography, 22(1),


Charpin, P., & Kyureghyan, G. (2009). When does G (x)+ Tr (H (x)) permute Fpn?. Finite Fields

and Their Applications, 15(5), 615-632.

Charpin, P., & Sarkar, S. (2011). Polynomials with linear structure and MaioranaMcFarland construction. IEEE Transactions on Information Theory, 57(6), 3796-3804.

Rothaus, O. S. (1976). On bent functions. Journal of Combinatorial Theory, Series A, 20(3), 300-305.

Carlet, C. (2010). Boolean functions for cryptography and error correcting codes. Boolean models and

methods in mathematics, computer science, and engineering, 2, 257-397.

Carlet, C., & Mesnager, S. (2011). On Dillons class H of bent functions, Niho bent functions and

o-polynomials. Journal of Combinatorial Theory, Series A, 118(8), 2392-2410.

Meng, Q., Chen, L., & Fu, F. W. (2010). On homogeneous rotation symmetric bent functions. Discrete

Applied Mathematics, 158(10), 1111-1117.

McFarland, R. L. (1973). A family of difference sets in non-cyclic groups. Journal of Combinatorial

Theory, Series A, 15(1), 1-10

Preneel, B., Van Leekwijck, W., Van Linden, L., Govaerts, R., & Vandewalle, J. (1990, May). Propagation characteristics of Boolean functions. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 161-173). Springer, Berlin, Heidelberg.

Jansen, C. J. A. (1989). Investigations on nonlinear streamcipher systems: construction and evaluation


MacWilliams, F. J., & Sloane, N. J. A. (1977). The theory of error-correcting codes (Vol. 16). Elsevier.

Carlet, C. (2004). On the confusion and diffusion properties of MaioranaMcFarland’s and extended

MaioranaMcFarland’s functions. Journal of complexity, 20(2-3), 182-204.