doi: 10.3934/amc.2021020
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.

A new construction of weightwise perfectly balanced Boolean functions

1. 

School of Mathematics and Statistics, Henan University, Kaifeng, 475004, China

2. 

Henan Engineering Research Center for Artificial Intelligence Theory and Algorithms, Henan University, Kaifeng, 475004, China

* Corresponding author: Sihong Su (E-mail: sush@henu.edu.cn)

Received  January 2021 Early access June 2021

Fund Project: The second author is supported by the Key Scientific Research Project of Colleges and Universities in Henan Province (Grant No. 21A413003) and the National Natural Science Foundation of China (Grant No. 61502147)

In this paper, we first introduce a class of quartic Boolean functions. And then, the construction of weightwise perfectly balanced Boolean functions on $ 2^m $ variables are given by modifying the support of the quartic functions, where $ m $ is a positive integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper.

Citation: Rui Zhang, Sihong Su. A new construction of weightwise perfectly balanced Boolean functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2021020
References:
[1]

C. CarletP. M$\mathrm{\acute{e}}$aux and Y. Rotella, Boolean functions with restricted input and their robustness: Application to the FLIP cipher, IACR Trans. Symm. Cryptol., 2017 (2017), 192-227.   Google Scholar

[2]

N. T. Coutois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-EUROCRYPT 2003, 2656 (2003), 345-359.  doi: 10.1007/3-540-39200-9_21.  Google Scholar

[3]

S. Duval, V. Lallemand and Y. Rotella, Cryptanalysis of the FLIP family of stream ciphers, in Advances in Cryptology—CRYPTO 2016, Lecture Notes in Computer Science, 9814, Berlin, Springer-Verlag, 2016,457–475. doi: 10.1007/978-3-662-53018-4_17.  Google Scholar

[4]

Y. Filmus, Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci., 14 (2016), 1-17.  doi: 10.4086/cjtcs.2016.014.  Google Scholar

[5]

Y. Filmus, An orthogonal basis for functions over a slice of the Boolean hypercube, Electron. J. Combin., 23 (2016), 1-23.   Google Scholar

[6]

J. Li and S. Su, Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity, Discrete Appl. Math., 279 (2020), 218-227.  doi: 10.1016/j.dam.2020.01.020.  Google Scholar

[7]

P. M$\mathrm{\acute{e}}$aux, A. Journault, F.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, in Advances in Cryptology-EUROCRYPT 2016, Lecture Notes in Computer Science, 9665, Berlin, Springer-Verlag, 2016,311–343. doi: 10.1007/978-3-662-49890-3_13.  Google Scholar

[8]

S. Mesnager and S. Su, On constructions of weightwise perfectly balanced Boolean functions, Cryptogr. Commun., (2021). doi: 10.1007/s12095-021-00481-32021.  Google Scholar

[9]

S. MesnagerZ. Zhou and C. Ding, On the nonlinearity of Boolean functions with restricted input, Cryptogr. Commun., 11 (2019), 63-76.  doi: 10.1007/s12095-018-0293-6.  Google Scholar

[10]

A. Richard, Orthogonal polynomials and special functions, in Regional Conference Series in Applied Mathematics, 21, SIAM, Philadelphia, PA, 1975, 59–60. Google Scholar

[11]

S. Su, The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions, Discrete Appl. Math., 297 (2021), 60-70.  doi: 10.1016/j.dam.2021.02.033.  Google Scholar

[12]

D. Tang and J. Liu, A family of weightwise perfectly balanced boolean functions with optimal algebraic immunity, Cryptogr. Commun., 11 (2019), 1185-1197.  doi: 10.1007/s12095-019-00374-6.  Google Scholar

[13]

E. W. Weisstein, Pascal's formula, From MathWorld-A Wolfram Web Resource. Available from: http://mathworld.wolfram.com/PascalsFormula.html. Google Scholar

show all references

References:
[1]

C. CarletP. M$\mathrm{\acute{e}}$aux and Y. Rotella, Boolean functions with restricted input and their robustness: Application to the FLIP cipher, IACR Trans. Symm. Cryptol., 2017 (2017), 192-227.   Google Scholar

[2]

N. T. Coutois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-EUROCRYPT 2003, 2656 (2003), 345-359.  doi: 10.1007/3-540-39200-9_21.  Google Scholar

[3]

S. Duval, V. Lallemand and Y. Rotella, Cryptanalysis of the FLIP family of stream ciphers, in Advances in Cryptology—CRYPTO 2016, Lecture Notes in Computer Science, 9814, Berlin, Springer-Verlag, 2016,457–475. doi: 10.1007/978-3-662-53018-4_17.  Google Scholar

[4]

Y. Filmus, Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci., 14 (2016), 1-17.  doi: 10.4086/cjtcs.2016.014.  Google Scholar

[5]

Y. Filmus, An orthogonal basis for functions over a slice of the Boolean hypercube, Electron. J. Combin., 23 (2016), 1-23.   Google Scholar

[6]

J. Li and S. Su, Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity, Discrete Appl. Math., 279 (2020), 218-227.  doi: 10.1016/j.dam.2020.01.020.  Google Scholar

[7]

P. M$\mathrm{\acute{e}}$aux, A. Journault, F.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, in Advances in Cryptology-EUROCRYPT 2016, Lecture Notes in Computer Science, 9665, Berlin, Springer-Verlag, 2016,311–343. doi: 10.1007/978-3-662-49890-3_13.  Google Scholar

[8]

S. Mesnager and S. Su, On constructions of weightwise perfectly balanced Boolean functions, Cryptogr. Commun., (2021). doi: 10.1007/s12095-021-00481-32021.  Google Scholar

[9]

S. MesnagerZ. Zhou and C. Ding, On the nonlinearity of Boolean functions with restricted input, Cryptogr. Commun., 11 (2019), 63-76.  doi: 10.1007/s12095-018-0293-6.  Google Scholar

[10]

A. Richard, Orthogonal polynomials and special functions, in Regional Conference Series in Applied Mathematics, 21, SIAM, Philadelphia, PA, 1975, 59–60. Google Scholar

[11]

S. Su, The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions, Discrete Appl. Math., 297 (2021), 60-70.  doi: 10.1016/j.dam.2021.02.033.  Google Scholar

[12]

D. Tang and J. Liu, A family of weightwise perfectly balanced boolean functions with optimal algebraic immunity, Cryptogr. Commun., 11 (2019), 1185-1197.  doi: 10.1007/s12095-019-00374-6.  Google Scholar

[13]

E. W. Weisstein, Pascal's formula, From MathWorld-A Wolfram Web Resource. Available from: http://mathworld.wolfram.com/PascalsFormula.html. Google Scholar

Table 1.  The $ k $-weight nonlinearity of $ g_3 $ in (11) for $ k = 2,3,4,5,6 $
k $ k $-weight nonlinearity of $ g_3 $ in (11) $ \lfloor {8\choose k}/{2}-\sqrt{8\choose k}/{2}\rfloor $
2 $ \mathrm{NL}_{2}(g_{3})=2 $ 11
3 $ \mathrm{NL}_{3}(g_3)=12 $ 24
4 $ \mathrm{NL}_{4}(g_3)=19 $ 30
5 $ \mathrm{NL}_{5}(g_3)=12 $ 24
6 $ \mathrm{NL}_{6}(g_3)=6 $ 11
k $ k $-weight nonlinearity of $ g_3 $ in (11) $ \lfloor {8\choose k}/{2}-\sqrt{8\choose k}/{2}\rfloor $
2 $ \mathrm{NL}_{2}(g_{3})=2 $ 11
3 $ \mathrm{NL}_{3}(g_3)=12 $ 24
4 $ \mathrm{NL}_{4}(g_3)=19 $ 30
5 $ \mathrm{NL}_{5}(g_3)=12 $ 24
6 $ \mathrm{NL}_{6}(g_3)=6 $ 11
Table 2.  The algebraic immunity of $ g_{m} $ for $ m = 2,3,4 $
$ m $ algebraic immunity of $ g_{m} $ in (11) optimal algebraic immunity
2 $ AI(g_2)=2 $ 2
3 $ AI(g_3)=3 $ 4
4 $ AI(g_4)=3 $ 8
$ m $ algebraic immunity of $ g_{m} $ in (11) optimal algebraic immunity
2 $ AI(g_2)=2 $ 2
3 $ AI(g_3)=3 $ 4
4 $ AI(g_4)=3 $ 8
[1]

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031

[2]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

[3]

Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009

[4]

Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017

[5]

Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003

[6]

Yvjing Yang, Yang Liu, Jungang Lou, Zhen Wang. Observability of switched Boolean control networks using algebraic forms. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1519-1533. doi: 10.3934/dcdss.2020373

[7]

Domingo Gómez-Pérez, László Mérai. Algebraic dependence in generating functions and expansion complexity. Advances in Mathematics of Communications, 2020, 14 (2) : 307-318. doi: 10.3934/amc.2020022

[8]

Claude Carlet. Revisiting some results on APN and algebraic immune functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021035

[9]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[10]

Daniele Bartoli, Leo Storme. On the functional codes arising from the intersections of algebraic hypersurfaces of small degree with a non-singular quadric. Advances in Mathematics of Communications, 2014, 8 (3) : 271-280. doi: 10.3934/amc.2014.8.271

[11]

Yaping Wu, Xiuxia Xing, Qixiao Ye. Stability of travelling waves with algebraic decay for $n$-degree Fisher-type equations. Discrete & Continuous Dynamical Systems, 2006, 16 (1) : 47-66. doi: 10.3934/dcds.2006.16.47

[12]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056

[13]

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201

[14]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[15]

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307

[16]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[17]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038

[18]

Peter Haïssinsky, Kevin M. Pilgrim. An algebraic characterization of expanding Thurston maps. Journal of Modern Dynamics, 2012, 6 (4) : 451-476. doi: 10.3934/jmd.2012.6.451

[19]

Aihua Li. An algebraic approach to building interpolating polynomial. Conference Publications, 2005, 2005 (Special) : 597-604. doi: 10.3934/proc.2005.2005.597

[20]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

2020 Impact Factor: 0.935

Article outline

Figures and Tables

[Back to Top]