doi: 10.3934/amc.2020136

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

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 Published  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.

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. CanteautP. 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. DobbertinG. LeanderA. CanteautC. CarletP. 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. GangopadhyayS. 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. LiY. 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. TangC. 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. TangH. D. YanZ. 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. CanteautP. 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. DobbertinG. LeanderA. CanteautC. CarletP. 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. GangopadhyayS. 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. LiY. 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. TangC. 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. TangH. D. YanZ. 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}} $
$ 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
$ 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
$ 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]

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

[2]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[3]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[4]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[5]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

[6]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004

[7]

Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017

[8]

Huan Zhang, Jun Zhou. Asymptotic behaviors of solutions to a sixth-order Boussinesq equation with logarithmic nonlinearity. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021034

[9]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2619-2633. doi: 10.3934/dcds.2020377

[10]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[11]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019

[12]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

[13]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020

[14]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

[15]

Akane Kawaharada. Singular function emerging from one-dimensional elementary cellular automaton Rule 150. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021125

[16]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[17]

Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010

[18]

Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021021

[19]

Tomoyuki Tanaka, Kyouhei Wakasa. On the critical decay for the wave equation with a cubic convolution in 3D. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021048

[20]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]