# American Institute of Mathematical Sciences

doi: 10.3934/amc.2021035
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Revisiting some results on APN and algebraic immune functions

 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

Fund Project: This work was supported in part by the Trond Mohn Foundation

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.

Citation: Claude Carlet. Revisiting some results on APN and algebraic immune functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2021035
##### 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.

show all references

##### 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.
 [1] Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59 [2] SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010 [3] Wacław Marzantowicz, Justyna Signerska. Firing map of an almost periodic input function. Conference Publications, 2011, 2011 (Special) : 1032-1041. doi: 10.3934/proc.2011.2011.1032 [4] Hasib Khan, Cemil Tunc, Aziz Khan. Green function's properties and existence theorems for nonlinear singular-delay-fractional differential equations. Discrete and Continuous Dynamical Systems - S, 2020, 13 (9) : 2475-2487. doi: 10.3934/dcdss.2020139 [5] Agnieszka Badeńska. No entire function with real multipliers in class $\mathcal{S}$. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3321-3327. doi: 10.3934/dcds.2013.33.3321 [6] Peter Bella, Arianna Giunti. Green's function for elliptic systems: Moment bounds. Networks and Heterogeneous Media, 2018, 13 (1) : 155-176. doi: 10.3934/nhm.2018007 [7] Virginia Agostiniani, Rolando Magnanini. Symmetries in an overdetermined problem for the Green's function. Discrete and Continuous Dynamical Systems - S, 2011, 4 (4) : 791-800. doi: 10.3934/dcdss.2011.4.791 [8] Alfonso Sorrentino. Computing Mather's $\beta$-function for Birkhoff billiards. Discrete and Continuous Dynamical Systems, 2015, 35 (10) : 5055-5082. doi: 10.3934/dcds.2015.35.5055 [9] Sungwon Cho. Alternative proof for the existence of Green's function. Communications on Pure and Applied Analysis, 2011, 10 (4) : 1307-1314. doi: 10.3934/cpaa.2011.10.1307 [10] Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial and Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467 [11] Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048 [12] Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013 [13] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [14] Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial and Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345 [15] Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 [16] Dmitry Jakobson and Iosif Polterovich. Lower bounds for the spectral function and for the remainder in local Weyl's law on manifolds. Electronic Research Announcements, 2005, 11: 71-77. [17] Shengxin Zhu. Summation of Gaussian shifts as Jacobi's third Theta function. Mathematical Foundations of Computing, 2020, 3 (3) : 157-163. doi: 10.3934/mfc.2020015 [18] Andrei Korobeinikov, Philip K. Maini. A Lyapunov function and global properties for SIR and SEIR epidemiological models with nonlinear incidence. Mathematical Biosciences & Engineering, 2004, 1 (1) : 57-60. doi: 10.3934/mbe.2004.1.57 [19] Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585 [20] Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

2020 Impact Factor: 0.935