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

Qian Liu

doi:10.3934/amc.2020136

Article Contents

2023, Volume 17, Issue 2: 418-430. Doi: 10.3934/amc.2020136

This issue Previous Article Duadic codes over

$ \mathbb{Z}_4+u\mathbb{Z}_4 $

Next Article An optimization approach to the Langberg-Médard multiple unicast conjecture

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
^* Corresponding author: Qian Liu

Received: October 2020

Revised: January 2021

Early access: March 2021

Published: April 2023

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)

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 06E30.

Citation:

Full Text(HTML)

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}} $

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.