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.  Google Scholar

[2]

T. BergerA. CanteautP. 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

[3]

L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014.  Google Scholar

[4]

L. BudaghyanC. CarletT. 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

[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.  Google Scholar

[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.  Google Scholar

[7] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press, 2021.  doi: 10.1017/9781108606806.  Google Scholar
[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.  Google Scholar

[9]

M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, (2005), available from: http://eprint.iacr.org. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[12]

M. Lobanov, A method for obtaining lower bounds on the higher order nonlinearity, IACR Cryptology ePrint Archive, (2013), http://eprint.iacr.org/. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

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.  Google Scholar

[2]

T. BergerA. CanteautP. 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

[3]

L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014.  Google Scholar

[4]

L. BudaghyanC. CarletT. 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

[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.  Google Scholar

[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.  Google Scholar

[7] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press, 2021.  doi: 10.1017/9781108606806.  Google Scholar
[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.  Google Scholar

[9]

M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, (2005), available from: http://eprint.iacr.org. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[12]

M. Lobanov, A method for obtaining lower bounds on the higher order nonlinearity, IACR Cryptology ePrint Archive, (2013), http://eprint.iacr.org/. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & Applied Analysis, 2011, 10 (4) : 1307-1314. doi: 10.3934/cpaa.2011.10.1307

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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.

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (21)
  • HTML views (41)
  • Cited by (0)

Other articles
by authors

[Back to Top]