-
Previous Article
Convolutional codes over finite chain rings, MDP codes and their characterization
- AMC Home
- This Issue
-
Next Article
On the pseudorandom properties of $ k $-ary Sidel'nikov sequences
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.
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 |
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.
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. |
[2] |
C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020.
doi: 10.1017/9781108606806.![]() ![]() |
[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. |
[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. |
[5] |
G. Cohen, I. Honkala and S. Litsyn, Covering Codes, North-Holland, Amsterdam, 1997. |
[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. |
[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. |
[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. |
[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. |
[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. |
[11] |
R. Gode and S. Gangopadhyay, On second order nonlinearity of cubic monomial Boolean functions., Available at: http://eprint.iacr.org/2009/502.pdf. |
[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. |
[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. |
[14] |
G. Leander,
Monomial bent functions, IEEE Transactions on Information Theory, 52 (2006), 738-743.
doi: 10.1109/TIT.2005.862121. |
[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. |
[16] |
R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.
![]() ![]() |
[17] |
F. J. Macwilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amesterdam, 1977. |
[18] |
S. Sarkar and S. Gangopadhyay, On the second order nonlinearity of a cubic Maiorana-Mcfarland bent function, Finite Fields Appl., 2009. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[2] |
C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020.
doi: 10.1017/9781108606806.![]() ![]() |
[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. |
[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. |
[5] |
G. Cohen, I. Honkala and S. Litsyn, Covering Codes, North-Holland, Amsterdam, 1997. |
[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. |
[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. |
[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. |
[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. |
[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. |
[11] |
R. Gode and S. Gangopadhyay, On second order nonlinearity of cubic monomial Boolean functions., Available at: http://eprint.iacr.org/2009/502.pdf. |
[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. |
[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. |
[14] |
G. Leander,
Monomial bent functions, IEEE Transactions on Information Theory, 52 (2006), 738-743.
doi: 10.1109/TIT.2005.862121. |
[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. |
[16] |
R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.
![]() ![]() |
[17] |
F. J. Macwilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amesterdam, 1977. |
[18] |
S. Sarkar and S. Gangopadhyay, On the second order nonlinearity of a cubic Maiorana-Mcfarland bent function, Finite Fields Appl., 2009. |
[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. |
[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. |
[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. |
[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. |
[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. |
Number of |
|
0 | |
Number of |
|
0 | |
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 |
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 |
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 | 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 and 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, 2021, 15 (4) : 757-775. 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 and Continuous Dynamical Systems, 2012, 32 (11) : 4045-4067. doi: 10.3934/dcds.2012.32.4045 |
[4] |
Seick Kim, Longjuan Xu. Green's function for second order parabolic equations with singular lower order coefficients. Communications on Pure and Applied Analysis, 2022, 21 (1) : 1-21. doi: 10.3934/cpaa.2021164 |
[5] |
Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 |
[6] |
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 |
[7] |
Eugenii Shustin, Emilia Fridman, Leonid Fridman. Oscillations in a second-order discontinuous system with delay. Discrete and Continuous Dynamical Systems, 2003, 9 (2) : 339-358. doi: 10.3934/dcds.2003.9.339 |
[8] |
Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems and Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721 |
[9] |
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 |
[10] |
Leonardo Colombo, David Martín de Diego. Second-order variational problems on Lie groupoids and optimal control applications. Discrete and Continuous Dynamical Systems, 2016, 36 (11) : 6023-6064. doi: 10.3934/dcds.2016064 |
[11] |
Qiong Meng, X. H. Tang. Solutions of a second-order Hamiltonian system with periodic boundary conditions. Communications on Pure and Applied Analysis, 2010, 9 (4) : 1053-1067. doi: 10.3934/cpaa.2010.9.1053 |
[12] |
Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial and Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455 |
[13] |
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 |
[14] |
Shanjian Tang. A second-order maximum principle for singular optimal stochastic controls. Discrete and Continuous Dynamical Systems - B, 2010, 14 (4) : 1581-1599. doi: 10.3934/dcdsb.2010.14.1581 |
[15] |
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 |
[16] |
Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 |
[17] |
Raegan Higgins. Asymptotic behavior of second-order nonlinear dynamic equations on time scales. Discrete and Continuous Dynamical Systems - B, 2010, 13 (3) : 609-622. doi: 10.3934/dcdsb.2010.13.609 |
[18] |
Xiaoping Wang. Ground state homoclinic solutions for a second-order Hamiltonian system. Discrete and Continuous Dynamical Systems - S, 2019, 12 (7) : 2163-2175. doi: 10.3934/dcdss.2019139 |
[19] |
Jaume Llibre, Amar Makhlouf. Periodic solutions of some classes of continuous second-order differential equations. Discrete and Continuous Dynamical Systems - B, 2017, 22 (2) : 477-482. doi: 10.3934/dcdsb.2017022 |
[20] |
Jae-Hong Pyo, Jie Shen. Normal mode analysis of second-order projection methods for incompressible flows. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 817-840. doi: 10.3934/dcdsb.2005.5.817 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]