Abstract
In this paper we investigate the existence of permutation polynomials of the form x d + L(x) on \({{\mathbb{F}_{2^n}}}\) , where \({{L(x)\in\mathbb{F}_{2^n}[x]}}\) is a linearized polynomial. It is shown that for some special d with gcd(d, 2n−1) > 1, x d + L(x) is nerve a permutation on \({{\mathbb{F}_{2^n}}}\) for any linearized polynomial \({{L(x)\in\mathbb{F}_{2^n}[x]}}\) . For the Gold functions \({{x^{2^i+1}}}\) , it is shown that \({{x^{2^i+1}+L(x)}}\) is a permutation on \({{\mathbb{F}_{2^n}}}\) if and only if n is odd and \({{L(x)=\alpha^{2^i}x+\alpha x^{2^i}}}\) for some \({{\alpha\in\mathbb{F}_{2^n}^{*}}}\) . We also disprove a conjecture in (Macchetti Addendum to on the generalized linear equivalence of functions over finite fields. Cryptology ePrint Archive, Report2004/347, 2004) in a very simple way. At last some interesting results concerning permutation polynomials of the form x −1 + L(x) are given.
Similar content being viewed by others
References
Biham E., Shamir A.: Defferential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)
Berger T., Canteaut A., Charpin P., Laigle-Chapuy Y.: On almost perfect nonlinear mappings over \({{\mathbb{F}_{2^n}}}\) . IEEE Trans. Inform. Theory 52(9), 4160–4170 (2006)
Breveglieri L., Cherubini A., Macchetti M.: On the generalized linear equivalence of functions over finite fields. In: Lee P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 79-91. Springer, Heidelberg (2004).
Budaghyan L.: The simplest method for constructing APN polynomials EA-inequivalent to power functions. In: WAIFI 2007. LNCS 4547, pp. 177–188 (2007).
Budaghyan L., Carlet C., Pott A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inform. Theory IT-52(3), 1141–1152 (2006)
Carlet C., Charpin P., Zinoviev V.: Codes, bent functions and permutations sutiable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (1998)
Chabaud F., Vaudenay S.: Links between differential and linear cryptanalysis. In: Advances in Cryptology-EUROCRYPT’94. LNCS, vol. 950, pp. 356–365. Springer-Verlag, New York (1995).
Charpin P., Kyureghyan G.: On a class of permutation polynomials over \({{\mathbb{F}_{2^n}}}\) . In: Proceedings of SETA 2008. LNCS, vol. 5203, pp. 368–376 (2008).
Dillon J.F.: APN polynomials: an update. In: Proceedings of: the 9th conference on finite fields and applications FQ9 (to be published). Dublin, Ireland (2009).
Edel Y., Kyureghyan G., Pott A.: A new APN function which is not equivalent to a power mapping. IEEE Trans. Inform. Theory. IT-52(2), 744–747 (2006)
Horadam K.J., Farmer D.G.: Bundels, presemifields and nonlinear functions. Des. Codes Cryptogr. 49, 79–94 (2008)
Hou X.D.: Affinity of permutations of \({{\mathbb{F}_{2}^{n}}}\) . Discret. Appl. Math. 154(2), 313–325 (2006)
Lidl R., Niederreiter H.: Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20. Addison-Wesley, Massachusetts (1983)
Macchetti M.: Addendum to on the generalized linear equivalence of functions over finite fields. Cryptology ePrint Archive, Report2004/347 (2004).
Matsui M.: Linear cryptanalysis method for DES cipher. In: Advances in Cryptology-EUROCRYPT’93. Lecture Notes in computer Science, vol. 765, pp. 386–397. Springer-Verlag, New York, (1994).
Nakagawa N., Yoshiara S.: A construction of differentially 4-uniform functions from commutative semifields of characteristic 2. In: WAIFI 2007. LNCS, vol. 4547, pp. 134–146. (2007).
Nyberg K.: Differentially uniform mappings for cryptography. In: Advances in cryptography. EUROCRYPT’93. LNCS, vol. 765, pp. 55–64. Springer-Verlag, New York (1994).
Nyberg K.: S-Boxes and round functions with controllable linearity and differential uniformity. In: Fast software encryption—FSE’94. Lecture Notes in Computers Science, vol. 1008, pp. 111–130. Springer-Verlag, Berlin (1995).
Pasalic E.: On cryptographically significant mappings over GF(2n). In: WAIFI 2008. LNCS , vol. 5130, pp. 189–204. (2008).
Pasalic E., Charpin P.: Some results concerning cryptographically significant mappings over GF(2n). Des. Codes Cryptogr. (publised on line, 06 February) (2010).
Yuan Y., Tong Y., Zhang H.: Complete mapping polynomials over finite field \({{\mathbb{F}_{16}}}\) . In: Arithmetic of finite fields. Lecture Notes in Computer Science, vol. 4547, pp. 147–158. Springer, Berlin (2007).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Pascale Charpin.
Rights and permissions
About this article
Cite this article
Li, Y., Wang, M. On EA-equivalence of certain permutations to power mappings. Des. Codes Cryptogr. 58, 259–269 (2011). https://doi.org/10.1007/s10623-010-9406-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-010-9406-8