American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020136

The lower bounds on the second-order nonlinearity of three classes of Boolean functions

Qian Liu ,

College of Mathematics and Computer Science, Key Laboratory of Information Security of Network Systems, Fuzhou University, Fuzhou 350108, China

* Corresponding author: Qian Liu

Received  October 2020 Revised  January 2021 Early access  March 2021

Fund Project: This work was supported by Educational Research Projects of Young and Middle-aged Teachers in Fujian Province (No. JAT200033) and the Talent Fund project of Fuzhou University (No. 0030510858)

In this paper, by calculating the lower bounds on the nonlinearity of the derivatives of the following three classes of Boolean functions, we provide the tight lower bounds on the second-order nonlinearity of these Boolean functions: (1) $ f_1(x) = Tr_1^n(x^{2^{r+1}+2^r+1}) $, where $ n = 2r+2 $ with even $ r $; (2) $ f_2(x) = Tr_1^n(\lambda x^{2^{2r}+2^{r+1}+1}) $, where $ \lambda \in \mathbb{F}_{2^r}^* $ and $ n = 4r $ with even $ r $; (3) $ f_3(x,y) = yTr_1^n(x^{2^r+1})+Tr_1^n(x^{2^r+3}) $, where $ (x, y)\in \mathbb{F}_{2^n}\times \mathbb{F}_2 $, $ n = 2r $ with odd $ r $. The results show that our bounds are better than previously known lower bounds in some cases.

Keywords: Boolean function, cryptography, cubic function, second-order nonlinearity, Walsh transform.
Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 06E30.
Citation: Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2020136
References:
[1]

A. Canteaut, P. Charpin and G. M. Kyureghyan, A new class of monomial bent functions, Finite Fields and Their Applications, 14 (2008), 221-241.  doi: 10.1016/j.ffa.2007.02.004.  Google Scholar

[2] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020.  doi: 10.1017/9781108606806.  Google Scholar
[3]

C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, Cambridge, (2010), 257-397. doi: 10.1017/CBO9780511780448.  Google Scholar

[4]

C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Transactions on Information Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar

[5]

G. Cohen, I. Honkala and S. Litsyn, Covering Codes, North-Holland, Amsterdam, 1997. Google Scholar

[6]

H. Dobbertin, G. Leander, A. Canteaut, C. Carlet, P. Felke and P. Gaborit, Construction of bent functions via Niho power functions, Journal of Combinatorial Theory, Series A, 113 (2006), 779-798.  doi: 10.1016/j.jcta.2005.07.009.  Google Scholar

[7]

I. Dumer, G. Kabatiansky and C. Tavernier, List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity, 2006 IEEE International Symposium on Information Theory, (2006), 138-142. doi: 10.1109/ISIT.2006.261690.  Google Scholar

[8]

R. Fourquet and C. Tavernier, An improved list decoding algorithm for the second order Reed-Muller codes and its applications, Designs Codes and Cyptography, 49 (2008), 323-340.  doi: 10.1007/s10623-008-9184-8.  Google Scholar

[9]

S. Gangopadhyay, S. Sarkar and R. Telang, On the lower bounds of the second order nonlinearities of some Boolean functions, Information Sciences, 180 (2010), 266-273.  doi: 10.1016/j.ins.2009.09.006.  Google Scholar

[10]

Q. Gao and D. Tang, A lower bound on the second-order nonlinearity of the generalized Maiorana-McFarland Boolean functions, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E101.A (2018), 2397-2401.  doi: 10.1587/transfun.E101.A.2397.  Google Scholar

[11]

R. Gode and S. Gangopadhyay, On second order nonlinearity of cubic monomial Boolean functions., Available at: http://eprint.iacr.org/2009/502.pdf. Google Scholar

[12]

G. Kabatiansky and C. Tavernier, List decoding of second order Reed-Muller codes, Proceedings of the Eighteen International Symposium of Communication Theory and Applications, Ambleside, UK, 2005. Google Scholar

[13]

L. R. Knudsen and M. J. B. Robshaw, Non-linear approximations in linear cryptanalysis, Advances in Cryptology-Eurocrypt, Springer, Berlin, 1996, 224-236. doi: 10.1007/3-540-68339-9_20.  Google Scholar

[14]

G. Leander, Monomial bent functions, IEEE Transactions on Information Theory, 52 (2006), 738-743.  doi: 10.1109/TIT.2005.862121.  Google Scholar

[15]

X. L. Li, Y. P. Hu and J. T. Gao, Lower bounds on the second order nonlinearity of Boolean functions, International Journal of Foundations of Computer Science, 22 (2011), 1331-1349.  doi: 10.1142/S012905411100874X.  Google Scholar

[16] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.   Google Scholar
[17]

F. J. Macwilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amesterdam, 1977.  Google Scholar

[18]

S. Sarkar and S. Gangopadhyay, On the second order nonlinearity of a cubic Maiorana-Mcfarland bent function, Finite Fields Appl., 2009. Google Scholar

[19]

G. H. Sun and C. K. Wu, The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity, Information Sciences, 179 (2009), 267-278.  doi: 10.1016/j.ins.2008.10.002.  Google Scholar

[20]

G. H. Sun and C. K. Wu, The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity, Applicable Algebra in Engineering Communication and Computing, 22 (2011), 37-45.  doi: 10.1007/s00200-010-0136-y.  Google Scholar

[21]

D. Tang, C. Carlet and X. H. Tang, On the second-order nonlinearities of some bent functions, Information Sciences, 223 (2013), 322-330.  doi: 10.1016/j.ins.2012.08.024.  Google Scholar

[22]

D. Tang, H. D. Yan, Z. C. Zhou and X. S. Zhang, A new lower bound on the second-order nonlinearity of a class of monomial bent functions, Cryptography and Communications, 12 (2020), 77-83.  doi: 10.1007/s12095-019-00360-y.  Google Scholar

[23]

H. D. Yan and D. Tang, Improving lower bounds on the second-order nonlinearity of three classes of Boolean functions, Discrete Mathematics, 343 (2020), 11698. doi: 10.1016/j.disc.2019.111698.  Google Scholar

show all references

References:
[1]

A. Canteaut, P. Charpin and G. M. Kyureghyan, A new class of monomial bent functions, Finite Fields and Their Applications, 14 (2008), 221-241.  doi: 10.1016/j.ffa.2007.02.004.  Google Scholar

[2] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020.  doi: 10.1017/9781108606806.  Google Scholar
[3]

C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, Cambridge, (2010), 257-397. doi: 10.1017/CBO9780511780448.  Google Scholar

[4]

C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Transactions on Information Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar

[5]

G. Cohen, I. Honkala and S. Litsyn, Covering Codes, North-Holland, Amsterdam, 1997. Google Scholar

[6]

H. Dobbertin, G. Leander, A. Canteaut, C. Carlet, P. Felke and P. Gaborit, Construction of bent functions via Niho power functions, Journal of Combinatorial Theory, Series A, 113 (2006), 779-798.  doi: 10.1016/j.jcta.2005.07.009.  Google Scholar

[7]

I. Dumer, G. Kabatiansky and C. Tavernier, List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity, 2006 IEEE International Symposium on Information Theory, (2006), 138-142. doi: 10.1109/ISIT.2006.261690.  Google Scholar

[8]

R. Fourquet and C. Tavernier, An improved list decoding algorithm for the second order Reed-Muller codes and its applications, Designs Codes and Cyptography, 49 (2008), 323-340.  doi: 10.1007/s10623-008-9184-8.  Google Scholar

[9]

S. Gangopadhyay, S. Sarkar and R. Telang, On the lower bounds of the second order nonlinearities of some Boolean functions, Information Sciences, 180 (2010), 266-273.  doi: 10.1016/j.ins.2009.09.006.  Google Scholar

[10]

Q. Gao and D. Tang, A lower bound on the second-order nonlinearity of the generalized Maiorana-McFarland Boolean functions, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E101.A (2018), 2397-2401.  doi: 10.1587/transfun.E101.A.2397.  Google Scholar

[11]

R. Gode and S. Gangopadhyay, On second order nonlinearity of cubic monomial Boolean functions., Available at: http://eprint.iacr.org/2009/502.pdf. Google Scholar

[12]

G. Kabatiansky and C. Tavernier, List decoding of second order Reed-Muller codes, Proceedings of the Eighteen International Symposium of Communication Theory and Applications, Ambleside, UK, 2005. Google Scholar

[13]

L. R. Knudsen and M. J. B. Robshaw, Non-linear approximations in linear cryptanalysis, Advances in Cryptology-Eurocrypt, Springer, Berlin, 1996, 224-236. doi: 10.1007/3-540-68339-9_20.  Google Scholar

[14]

G. Leander, Monomial bent functions, IEEE Transactions on Information Theory, 52 (2006), 738-743.  doi: 10.1109/TIT.2005.862121.  Google Scholar

[15]

X. L. Li, Y. P. Hu and J. T. Gao, Lower bounds on the second order nonlinearity of Boolean functions, International Journal of Foundations of Computer Science, 22 (2011), 1331-1349.  doi: 10.1142/S012905411100874X.  Google Scholar

[16] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.   Google Scholar
[17]

F. J. Macwilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amesterdam, 1977.  Google Scholar

[18]

S. Sarkar and S. Gangopadhyay, On the second order nonlinearity of a cubic Maiorana-Mcfarland bent function, Finite Fields Appl., 2009. Google Scholar

[19]

G. H. Sun and C. K. Wu, The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity, Information Sciences, 179 (2009), 267-278.  doi: 10.1016/j.ins.2008.10.002.  Google Scholar

[20]

G. H. Sun and C. K. Wu, The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity, Applicable Algebra in Engineering Communication and Computing, 22 (2011), 37-45.  doi: 10.1007/s00200-010-0136-y.  Google Scholar

[21]

D. Tang, C. Carlet and X. H. Tang, On the second-order nonlinearities of some bent functions, Information Sciences, 223 (2013), 322-330.  doi: 10.1016/j.ins.2012.08.024.  Google Scholar

[22]

D. Tang, H. D. Yan, Z. C. Zhou and X. S. Zhang, A new lower bound on the second-order nonlinearity of a class of monomial bent functions, Cryptography and Communications, 12 (2020), 77-83.  doi: 10.1007/s12095-019-00360-y.  Google Scholar

[23]

H. D. Yan and D. Tang, Improving lower bounds on the second-order nonlinearity of three classes of Boolean functions, Discrete Mathematics, 343 (2020), 11698. doi: 10.1016/j.disc.2019.111698.  Google Scholar

Table 1.  The Walsh spectrum of $ f $
$ W_f(\omega) $ Number of $ \omega $
0 $ 2^n-2^{n-k} $
$ 2^{\frac{n+k}{2}} $ $ 2^{n-k-1}+(-1)^{f(0)}2^{\frac{n-k-2}{2}} $
$ -2^{\frac{n+k}{2}} $ $ 2^{n-k-1}-(-1)^{f(0)}2^{\frac{n-k-2}{2}} $
Table Options

Download as excel

$ W_f(\omega) $ Number of $ \omega $
0 $ 2^n-2^{n-k} $
$ 2^{\frac{n+k}{2}} $ $ 2^{n-k-1}+(-1)^{f(0)}2^{\frac{n-k-2}{2}} $
$ -2^{\frac{n+k}{2}} $ $ 2^{n-k-1}-(-1)^{f(0)}2^{\frac{n-k-2}{2}} $
Table 2.  Comparison of the lower bound on second-order nonlinearity with the known results
$ n $ bound in [19] bound in [9] bound in [11] bound in [15] Our new bound in Theorem 3.6
8 62 63 64 38 80
16 28615 24561 28672 26974 29815
24 8125467 7339906 8126464 8017875 8202293
32 2130690153 2013264900 2130706432 2123757059 2135604974
40 548681810337 532575936520 548682072064 548237313548 548996316833
Table Options

Download as excel

$ n $ bound in [19] bound in [9] bound in [11] bound in [15] Our new bound in Theorem 3.6
8 62 63 64 38 80
16 28615 24561 28672 26974 29815
24 8125467 7339906 8126464 8017875 8202293
32 2130690153 2013264900 2130706432 2123757059 2135604974
40 548681810337 532575936520 548682072064 548237313548 548996316833
Table 3.  Comparison of the lower bound on second-order nonlinearity with the known results for odd $ r $
$ r $ 1 3 5 7 9 11 13
bound in [4] 0 19 662 13487 238971 4008935 65625942
Our new bound in Theorem 3.9 1 32 763 14309 245641 4062737 66058274
Table Options

Download as excel

$ r $ 1 3 5 7 9 11 13
bound in [4] 0 19 662 13487 238971 4008935 65625942
Our new bound in Theorem 3.9 1 32 763 14309 245641 4062737 66058274
[1]

Florian Schneider. Second-order mixed-moment model with differentiable ansatz function in slab geometry. Kinetic & Related Models, 2018, 11 (5) : 1255-1276. doi: 10.3934/krm.2018049
[2]

Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020095
[3]

Chiara Zanini, Fabio Zanolin. Periodic solutions for a class of second order ODEs with a Nagumo cubic type nonlinearity. Discrete & Continuous Dynamical Systems, 2012, 32 (11) : 4045-4067. doi: 10.3934/dcds.2012.32.4045
[4]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010
[5]

José F. Cariñena, Javier de Lucas Araujo. Superposition rules and second-order Riccati equations. Journal of Geometric Mechanics, 2011, 3 (1) : 1-22. doi: 10.3934/jgm.2011.3.1
[6]

Eugenii Shustin, Emilia Fridman, Leonid Fridman. Oscillations in a second-order discontinuous system with delay. Discrete & Continuous Dynamical Systems, 2003, 9 (2) : 339-358. doi: 10.3934/dcds.2003.9.339
[7]

Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems & Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721
[8]

Armin Eftekhari, Michael B. Wakin, Ping Li, Paul G. Constantine. Randomized learning of the second-moment matrix of a smooth function. Foundations of Data Science, 2019, 1 (3) : 329-387. doi: 10.3934/fods.2019015
[9]

Leonardo Colombo, David Martín de Diego. Second-order variational problems on Lie groupoids and optimal control applications. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 6023-6064. doi: 10.3934/dcds.2016064
[10]

Qiong Meng, X. H. Tang. Solutions of a second-order Hamiltonian system with periodic boundary conditions. Communications on Pure & Applied Analysis, 2010, 9 (4) : 1053-1067. doi: 10.3934/cpaa.2010.9.1053
[11]

Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial & Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455
[12]

W. Sarlet, G. E. Prince, M. Crampin. Generalized submersiveness of second-order ordinary differential equations. Journal of Geometric Mechanics, 2009, 1 (2) : 209-221. doi: 10.3934/jgm.2009.1.209
[13]

Shanjian Tang. A second-order maximum principle for singular optimal stochastic controls. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1581-1599. doi: 10.3934/dcdsb.2010.14.1581
[14]

José F. Cariñena, Irina Gheorghiu, Eduardo Martínez. Jacobi fields for second-order differential equations on Lie algebroids. Conference Publications, 2015, 2015 (special) : 213-222. doi: 10.3934/proc.2015.0213
[15]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[16]

Raegan Higgins. Asymptotic behavior of second-order nonlinear dynamic equations on time scales. Discrete & Continuous Dynamical Systems - B, 2010, 13 (3) : 609-622. doi: 10.3934/dcdsb.2010.13.609
[17]

Xiaoping Wang. Ground state homoclinic solutions for a second-order Hamiltonian system. Discrete & Continuous Dynamical Systems - S, 2019, 12 (7) : 2163-2175. doi: 10.3934/dcdss.2019139
[18]

Jaume Llibre, Amar Makhlouf. Periodic solutions of some classes of continuous second-order differential equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (2) : 477-482. doi: 10.3934/dcdsb.2017022
[19]

Jae-Hong Pyo, Jie Shen. Normal mode analysis of second-order projection methods for incompressible flows. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 817-840. doi: 10.3934/dcdsb.2005.5.817
[20]

Simone Fiori, Italo Cervigni, Mattia Ippoliti, Claudio Menotta. Synthetic nonlinear second-order oscillators on Riemannian manifolds and their numerical simulation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021088

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (72)
  • HTML views (192)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences