Abstract
We give a survey on the constructions of APN and differentially 4-uniform functions suitable for designing S-boxes for block ciphers. We recall why the search for more of such functions is necessary. We propose a way of designing functions which can possibly be APN or differentially 4-uniform and be bijective. We illustrate it with an example of a differentially 4-uniform (n,n)-permutation for n odd, based on the power function x 3 over the second order Galois extension of \({\Bbb F}_{2^{n+1}}\), and related to the Dickson polynomial D 3 over this field. These permutations have optimal algebraic degree and their nonlinearity happens to be rather good (but worse than that of the multiplicative inverse functions).
Annovation
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology 4(1), 3–72 (1991)
Bracken, C., Byrne, E., Markin, N., McGuire, G.: New families of quadratic almost perfect nonlinear trinomials and multinomials. Finite Fields and their Applications 14, 703–714 (2008)
Bracken, C., Byrne, E., Markin, N., McGuire, G.: A few more quadratic APN functions. arXiv:0804.4799v1 (2007)
Bracken, C., Byrne, E., McGuire, G., Nebe, G.: On the equivalence of quadratic APN functions. To appear in Designs, Codes and Cryptography (2011)
Bracken, C., Leander, G.: A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree. Finite Fields and Their Applications 16(4), 231–242 (2010)
Bracken, C., Leander, G.: New families of functions with differential uniformity of 4. In: Proceedings of the conference BFCA 2008, Copenhagen (2008) (to appear)
Brinkmann, M., Leander, G.: On the classification of APN functions up to dimension five. Designs, Codes and Cryptography 49(1-3), 273–288 (2008); Revised and extended version of a paper with the same title in the Proceedings of the Workshop on Coding and Cryptography WCC 2007, pp. 39-48 (2007)
Browning, K., Dillon, J.F., Kibler, R.E., McQuistan, M.: APN polynomials and related codes. Special volume of Journal of Combinatorics, Information and System Sciences, honoring the 75-th birthday of Prof. D.K.Ray-Chaudhuri 34, 135–159 (2009)
Budaghyan, L.: The simplest method for constructing APN polynomials EA-inequivalent to power functions. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 177–188. Springer, Heidelberg (2007)
Budaghyan, L., Carlet, C.: Classes of Quadratic APN Trinomials and Hexanomials and Related Structures. IEEE Trans. Inform. Theory 54(5), 2354–2357 (2008)
Budaghyan, L., Carlet, C.: On CCZ-equivalence and its use in secondary constructions of bent functions. In: Proceedings of WCC 2009 (2009)
Budaghyan, L., Carlet, C., Leander, G.: Two classes of quadratic APN binomials inequivalent to power functions. IEEE Trans. Inform. Theory 54(9), 4218–4229 (2008)
Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Finite Fields and Applications 15(2), 150–159 (2009)
Budaghyan, L., Carlet, C., Leander, G.: On a construction of quadratic APN functions. In: Proceedings of ITW workshop, Taormina, Italy, October 11-16 (2009)
Budaghyan, L., Carlet, C., Pott, A.: New Classes of Almost Bent and Almost Perfect Nonlinear Polynomials. In: Proceedings of the Workshop on Coding and Cryptography 2005, Bergen, pp. 306–315 (2005); A completed version has been published in IEEE Trans. Inform. Theory 52(3), 1141–1152 (March 2006)
Canteaut, A., Charpin, P., Dobbertin, H.: Binary m-sequences with three-valued crosscorrelation: A proof of Welch’s conjecture. IEEE Trans. Inform. Theory 46(1), 4–8 (2000)
Carlet, C.: Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions. Designs, Codes and Cryptography 59(1-3), 89–109 (2010); post-proceedings of WCC 2009
Carlet, C.: Boolean Functions for Cryptography and Error Correcting Codes. In: Crama, Y., Hammer, P. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press, Cambridge (2010); Preliminary version available at http://www-rocq.inria.fr/codes/Claude.Carlet/pubs.html
Carlet, C.: Vectorial Boolean Functions for Cryptography. In: Crama, Y., Hammer, P. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 398–469. Cambridge University Press, Cambridge (2010); Preliminary version available at http://www-rocq.inria.fr/codes/Claude.Carlet/pubs.html
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), 125–156 (1998)
Carlet, C., Ding, C.: Nonlinearities of S-boxes. Finite Fields and its Applications 13(1), 121–135 (2007)
Chabaud, F., Vaudenay, S.: Links between Differential and Linear Cryptanalysis. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 356–365. Springer, Heidelberg (1995)
Dillon, J.F.: APN polynomials: an update. In: Conference Finite Fields and Applications Fq9, Dublin, Ireland (July 2009)
Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications 3(1), 59–81 (2009)
de Hou, X., Mullen, G.L., Sellers, J.A., Yucas, J.L.: Sellers and J. L. Yucas. Reversed Dickson polynomials over finite fields. Finite Fields and Their Applications 15(6), 748–773 (2009)
Knudsen, L.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)
Lachaud, G., Wolfmann, J.: The Weights of the Orthogonals of the Extended Quadratic Binary Goppa Codes. IEEE Trans. Inform. Theory 36, 686–692 (1990)
Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Applications, vol. 20. Addison-Wesley, Reading (1983)
Li, Y., Wang, M.: On EA-equivalence of certain permutations to power mappings. Designs, Codes and Cryptography 58(3), 259–269 (2010)
Li, Y., Wang, M.: On permutation polynomials EA-equivalent to the inverse function over GF(2n). IACR ePrint Archive 2010/573
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Nyberg, K.: Perfect non-linear S-boxes. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 378–386. Springer, Heidelberg (1991)
Nyberg, K.: On the construction of highly nonlinear permutations. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 92–98. Springer, Heidelberg (1993)
Nyberg, K.: New bent mappings suitable for fast implementation. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 179–184. Springer, Heidelberg (1994)
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Rivain, M., Prouff, E.: Provably Secure Higher-Order Masking of AES. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 413–427. Springer, Heidelberg (2010)
Sidelnikov, V.M.: On the mutual correlation of sequences. Soviet Math. Dokl. 12, 197–201 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carlet, C. (2011). On Known and New Differentially Uniform Functions. In: Parampalli, U., Hawkes, P. (eds) Information Security and Privacy. ACISP 2011. Lecture Notes in Computer Science, vol 6812. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22497-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-22497-3_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22496-6
Online ISBN: 978-3-642-22497-3
eBook Packages: Computer ScienceComputer Science (R0)