zbMATH — the first resource for mathematics

On EA-equivalence of certain permutations to power mappings. (English) Zbl 1216.94049
Summary: 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, 2^n-1)> 1\), \(x^d+L(x)\) is never 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 [M. 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.

94A60 Cryptography
11T06 Polynomials over finite fields
Full Text: DOI
[1] Biham E., Shamir A.: Defferential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991) · Zbl 0729.68017 · doi:10.1007/BF00630563
[2] 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) · Zbl 1184.94224 · doi:10.1109/TIT.2006.880036
[3] 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). · Zbl 1094.94028
[4] Budaghyan L.: The simplest method for constructing APN polynomials EA-inequivalent to power functions. In: WAIFI 2007. LNCS 4547, pp. 177–188 (2007). · Zbl 1177.94133
[5] 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) · Zbl 1177.94136 · doi:10.1109/TIT.2005.864481
[6] Carlet C., Charpin P., Zinoviev V.: Codes, bent functions and permutations sutiable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (1998) · Zbl 0938.94011 · doi:10.1023/A:1008344232130
[7] 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). · Zbl 0879.94023
[8] 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). · Zbl 1180.11038
[9] 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).
[10] 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) · Zbl 1246.11185 · doi:10.1109/TIT.2005.862128
[11] Horadam K.J., Farmer D.G.: Bundels, presemifields and nonlinear functions. Des. Codes Cryptogr. 49, 79–94 (2008) · Zbl 1178.94190 · doi:10.1007/s10623-008-9172-z
[12] Hou X.D.: Affinity of permutations of \({{\mathbb{F}_{2}^{n}}}\) . Discret. Appl. Math. 154(2), 313–325 (2006) · Zbl 1089.94020 · doi:10.1016/j.dam.2005.03.022
[13] Lidl R., Niederreiter H.: Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20. Addison-Wesley, Massachusetts (1983) · Zbl 0554.12010
[14] Macchetti M.: Addendum to on the generalized linear equivalence of functions over finite fields. Cryptology ePrint Archive, Report2004/347 (2004).
[15] 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). · Zbl 0951.94519
[16] 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). · Zbl 1213.11196
[17] Nyberg K.: Differentially uniform mappings for cryptography. In: Advances in cryptography. EUROCRYPT’93. LNCS, vol. 765, pp. 55–64. Springer-Verlag, New York (1994). · Zbl 0951.94510
[18] 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). · Zbl 0939.94559
[19] Pasalic E.: On cryptographically significant mappings over GF(2 n ). In: WAIFI 2008. LNCS , vol. 5130, pp. 189–204. (2008). · Zbl 1247.94029
[20] Pasalic E., Charpin P.: Some results concerning cryptographically significant mappings over GF(2 n ). Des. Codes Cryptogr. (publised on line, 06 February) (2010). · Zbl 1197.94201
[21] 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). · Zbl 1213.11193
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.