Article Contents

2023, Volume 17, Issue 5: 1012-1026. Doi: 10.3934/amc.2021035

This issue Previous Article Next Article Domination mappings into the hamming ball: Existence, constructions, and algorithms

Revisiting some results on APN and algebraic immune functions

Claude Carlet^1,

Universities of Bergen, Norway and Paris 8, France, Bergen, 5005, Norway and Saint-Denis 93526, France

Received: May 2021

Revised: August 2021

Early access: August 2021

Published: October 2023

This work was supported in part by the Trond Mohn Foundation

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

We push a little further the study of two recent characterizations of almost perfect nonlinear (APN) functions. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to a new result about APN power functions and more general APN polynomials with coefficients in a subfield $ \mathbb{F}_{2^k} $, which eases the research of such functions. It also allows to construct automatically many differentially uniform functions from them (this avoids calculations for proving their differential uniformity as done in a recent paper, which are tedious and specific to each APN function). In a second part, we give simple proofs of two important results on Boolean functions, one of which deserves to be better known but needed clarification, while the other needed correction.

Keywords:

Mathematics Subject Classification: Primary: 06E30, 11T71; Secondary: 11T06.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	T. Beth and C. Ding, On almost perfect nonlinear permutations, Advances in cryptology EUROCRYPT '93 (Lofthus, 1993), Lecture Notes in Comput. Sci., 765, Springer, Berlin, (1994), 65–76. doi: 10.1007/3-540-48285-7_7.
[2]	T. Berger, A. Canteaut, P. Charpin and Y. Laigle-Chapuy, On almost perfect nonlinear functions, IEEE Trans. Inform. Theory, 52 (2006), 4160-4170. doi: 10.1109/TIT.2006.880036.
[3]	L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014.
[4]	L. Budaghyan, C. Carlet, T. Helleseth and N. Kaleyski, On the distance between APN functions, IEEE Trans. Inform. Theory, 66 (2020), 5742-5753. doi: 10.1109/TIT.2020.2983684.
[5]	M. Calderini, Differentially low uniform permutations from known 4-uniform functions, Des. Codes Cryptogr., 89 (2021), 33-52. doi: 10.1007/s10623-020-00807-x.
[6]	C. Carlet, On the higher order nonlinearities of algebraic immune functions, Proceedings of CRYPTO 2006, Lecture Notes in Computer Science, 4117 (2006), 584-601. doi: 10.1007/11818175_35.
[7]	C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press, 2021. doi: 10.1017/9781108606806.
[8]	C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, Advances in cryptology ASIACRYPT, Lecture Notes in Comput. Sci., 5350, Springer, Berlin, (2008), 425–440. doi: 10.1007/978-3-540-89255-7_26.
[9]	M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, (2005), available from: http://eprint.iacr.org.
[10]	M. S. Lobanov, Exact relation between nonlinearity and algebraic immunity, Diskret. Mat., Translation in Discrete Math. Appl., 16 (2006), 453-460. doi: 10.1515/156939206779238418.
[11]	M. Lobanov, Tight bounds between algebraic immunity and nonlinearities of high orders, NATO Science for Peace and Security Series - D: Information and Communication Security, Vol 18: Boolean Functions in Cryptology and Information Security, IOS Press, 18 (2008), 296–306.
[12]	M. Lobanov, A method for obtaining lower bounds on the higher order nonlinearity, IACR Cryptology ePrint Archive, (2013), http://eprint.iacr.org/.
[13]	F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
[14]	S. Mesnager, Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity, IEEE Transactions on Information Theory, 54 (2008), 3656-3662. doi: 10.1109/TIT.2008.926360.
[15]	K. Nyberg, Perfect non-linear S-boxes, Proceedings of EUROCRYPT 1991, Lecture Notes in Comput. Sci., 547 (1991), 378-386. doi: 10.1007/3-540-46416-6_32.
[16]	K. Nyberg, On the construction of highly nonlinear permutations, Proceedings of EUROCRYPT 1992, Lecture Notes in Comput. Sci., 658 (1993), 92-98. doi: 10.1007/3-540-47555-9_8.
[17]	K. Nyberg, Differentially uniform mappings for cryptography, Proceedings of EUROCRYPT 1993, Comput. Sci., 765 (1994), 55-64. doi: 10.1007/3-540-48285-7_6.
[18]	K. Nyberg and L. R. Knudsen, Provable security against differential cryptanalysis, Advances in cryptology CRYPTO 1992 (Santa Barbara, CA, 1992), Lecture Notes in Comput. Sci., 740, Springer, Berlin, (1993), 566–574. doi: 10.1007/3-540-48071-4_41.
[19]	Z. Tu and Y. Deng, A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity, DDes. Codes Cryptogr., 60 (2011), 1-14. doi: 10.1007/s10623-010-9413-9.
[20]	Q. Wang and T. Johansson, A note on fast algebraic attacks and higher order nonlinearities, Information Security and Cryptology, Lecture Notes in Comput. Sci., 6584, Springer, Heidelberg, (2011), 404–414. doi: 10.1007/978-3-642-21518-6_28.
[21]	Y. Wang, W. G. Zhang and Z. Zha, Low differentially uniform permutations from Dobbertin APN function over $\mathbb{F}_{2^n}$, Preprint, 2021, available from: https://arXiv.org/abs/2103.10687.