Permutation binomial functions over finite fields

A. V. Miloserdov

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 59-80.

Résumé

We consider binomial functions over a finite field of order $2^n$. Some necessary condition is found for such a binomial function to be a permutation. It is proved that there are no permutation binomial functions in the case that $2^n-1$ is prime. Permutation binomial functions are constructed in the case when $4n$ is composite and found for $n\le8$. Tab. 2, bibliogr. 30.

Détail

Keywords: vectorial Boolean function, APN function.
Mots-clés : binomial function, permutation

Bibliographie

[1] M. M. Glukhov, “On the approximation of discrete functions by linear functions”, Mat. Vopr. Kriptogr., 7:4 (2016), 29–50 (Russian) | DOI | MR

[2] A. A. Gorodilova, “From cryptanalysis to cryptographic property of a Boolean function”, Prikl. Diskretn. Mat., 2016, no. 3, 16–44 (Russian) | DOI | MR

[3] D. P. Pokrasenko, “On the maximal component algebraic immunity of vectorial Boolean functions”, J. Appl. Ind. Math., 10:2 (2016), 257–263 | DOI | DOI | MR | Zbl

[4] V. N. Sachkov, “Combinatorial properties of differentially 2-uniform substitutions”, Mat. Vopr. Kriptogr., 6:1 (2015), 159–179 (Russian) | DOI | MR

[5] N. N. Tokareva, Symmetric Cryptography, A Brief Course, Novosib. Gos. Univ., Novosibirsk, 2012, 234 pp. (Russian)

[6] M. E. Tuzhilin, “APN-functions”, Prikl. Diskretn. Mat., 2009, no. 3, 14–20 (Russian)

[7] Ayad M., Belghaba K., Kihel O., “On permutation binomials over finite fields”, Bull. Aust. Math. Soc., 89 (2014), 112–124 | DOI | MR | Zbl

[8] Bracken C., Byrne E., Markin N., McGuire G., “Fourier spectra of Binomial APN functions”, SIAM J. Discrete Math., 23:2 (2008), 596–608 | DOI | MR

[9] Budaghyan L., Construction and analysis of cryptographic functions, Springer-Verl., Berlin, 2015, 176 pp. | MR

[10] Budaghyan L., Carlet C., Felke P., Leander G., “An infinite class of quadratic APN functions which are not equivalent to power mappings”, Proc. 17th IEEE Int. Symp. Information Theory (Seattle, USA, July 9–14, 2006), IEEE, Piscataway, 2006, 2637–2641

[11] Budaghyan L., Carlet C., Leander G., “Another class of quadratic APN binomials over $\mathbb F_{2^n}$: the case $n$ divisible by 4”, Proc. Int. Workshop Coding Cryptography, WCC 2007 (Versailles, France, Apr. 16–20, 2007), 49–58

[12] Budaghyan L., Carlet C., Leander G., “Constructing new APN functions from known ones”, Finite Fields Appl., 15:2 (2009), 150–159 | DOI | MR | Zbl

[13] Canteaut A., Charpin P., Kyureghyan G., “A new class of monomial bent functions”, Finite Fields Appl., 14:1 (2008), 221–241 | DOI | MR | Zbl

[14] Carlet C., “On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions”, Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes, Proc. NATO Adv. Res. Workshop ACPTECC (Veliko Tarnovo, Bulgaria, Oct. 6–9, 2008), IOS Press, Amsterdam, 2009, 104–116 | MR

[15] Carlet C., “Boolean functions for cryptography and error-correcting codes”, Boolean models and methods in mathematics, computer science, and engineering, Encycl. Math. Its Appl., 134, Camb. Univ. Press, New York, 2010, 257–397 | Zbl

[16] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Encycl. Math. Its Appl., 134, Camb. Univ. Press, New York, 2010, 398–470

[17] Daemen J., Rijmen V., AES Proposal: Rijndael, Belgium, 1999

[18] Daemen J., Rijmen V., The design of Rijndael, Springer, Heidelberg, 2002, 238 pp. | MR | Zbl

[19] Dobbertin H., “Almost perfect nonlinear power functions on $\mathbb F_{2^n}$: the Welch case”, IEEE Trans. Inf. Theory, 45:4 (1999), 1271–1275 | DOI | MR | Zbl

[20] Dobbertin H., Leander G., “A survey of some recent results on bent functions”, Sequences and Their Applications – SETA 2004, Rev. Sel. Papers 3rd Int. Conf. (Seoul, Korea, Oct. 24–28, 2004), Lect. Notes Comput. Sci., 3486, Springer, Heidelberg, 2005, 1–29 | DOI | Zbl

[21] Dobbertin H., Leander G., Canteaut A., Carlet C., Felkea P., Gaborit P., “Construction of bent functions via Niho power functions”, J. Comb. Theory Ser. A, 113:5 (2006), 779–798 | DOI | MR | Zbl

[22] Hou X., “Permutation polynomials over finite fields – A survey of recent advances”, Finite Fields Their Appl., 32 (2015), 82–119 | DOI | MR | Zbl

[23] Masuda A. M., Zieve M. E., “Permutation binomials over finite fields”, Trans. Am. Math. Soc., 361:8 (2009), 4169–4180 | DOI | MR | Zbl

[24] Niederreiter H., Robinson K., “Complete mappings of finite fields”, J. Aust. Math. Soc., 33:2 (1982), 197–212 | DOI | MR | Zbl

[25] Nyberg K., “Differentially uniform mappings for cryptography”, Advances in Cryptology, EUROCRYPT'93, Proc. Workshop Theory Appl. Crypt. Tech. (Lofthus, Norway, May 23–27, 1993), Lect. Notes Comput. Sci., 765, Springer, Heidelberg, 1994, 55–64 | DOI | MR | Zbl

[26] Seroussi G., Table of low-weight binary irreducible polynomials, Tech. Rep. HPL-98-135, Hewlett-Packard, 1998

[27] Tokareva N. N., Bent functions: Results and applications to cryptography, Acad. Press, London, 2015, 220 pp. | MR | Zbl

[28] G. Turnwald, “Permutation polynomials of binomial type”, Contributions to General Algebra, v. 6, Hölder–Pichler–Tempsky, Vienna, 1988, 281–286 | MR

[29] Shallue C. J., Permutation polynomials of finite fields, Honours project, Monash University, 2012

[30] Yang M., Meng Q., Zhang H., Evolutionary design of trace form bent functions, Cryptology ePrint Arch. Rep. 2005/322, https://eprint.iacr.org/2005/322