A new construction of weightwise perfectly balanced Boolean functions
On the complexity of solving generic overdetermined bilinear systems
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
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.
Keywords: Boolean function, vectorial function, S-box, symmetric cryptography, almost perfect nonlinear.
Mathematics Subject Classification: Primary: 06E30, 11T71; Secondary: 11T06.
Citation: Claude Carlet. Revisiting some results on APN and algebraic immune functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2021035
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. Google Scholar
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. Google Scholar
L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
[7] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press, 2021. doi: 10.1017/9781108606806. Google Scholar
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. Google Scholar
M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, (2005), available from: http://eprint.iacr.org. Google Scholar
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. Google Scholar
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. Google Scholar
M. Lobanov, A method for obtaining lower bounds on the higher order nonlinearity, IACR Cryptology ePrint Archive, (2013), http://eprint.iacr.org/. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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
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
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
Hasib Khan, Cemil Tunc, Aziz Khan. Green function's properties and existence theorems for nonlinear singular-delay-fractional differential equations. Discrete & Continuous Dynamical Systems - S, 2020, 13 (9) : 2475-2487. doi: 10.3934/dcdss.2020139
Agnieszka Badeńska. No entire function with real multipliers in class $\mathcal{S}$. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3321-3327. doi: 10.3934/dcds.2013.33.3321
Peter Bella, Arianna Giunti. Green's function for elliptic systems: Moment bounds. Networks & Heterogeneous Media, 2018, 13 (1) : 155-176. doi: 10.3934/nhm.2018007
Virginia Agostiniani, Rolando Magnanini. Symmetries in an overdetermined problem for the Green's function. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 791-800. doi: 10.3934/dcdss.2011.4.791
Alfonso Sorrentino. Computing Mather's $\beta$-function for Birkhoff billiards. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 5055-5082. doi: 10.3934/dcds.2015.35.5055
Sungwon Cho. Alternative proof for the existence of Green's function. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1307-1314. doi: 10.3934/cpaa.2011.10.1307
Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial & Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467
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
Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial & Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345
Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911
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.
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
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
Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465
Claude Carlet