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

Generic Construction of Boolean Functions with A Few Walsh Transform Values of Any Possible Algebraic Degree

1. 

College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu 730070, China

2. 

University of Chinese Academy of Sciences, Beijing 100049, China

3. 

Fujian Key Laboratory of Financial Information Processing, Putian University, Putian, Fujian 351100, China

*Corresponding author: Xiaoni Du

Received  March 2022 Revised  May 2022 Early access July 2022

Bent functions, semi-bent functions and other Boolean functions with a few Walsh spectra have important applications in coding theory, cryptography and sequence design. In this paper, motivated by the work of Tang et al.(IEEE Trans. Inf. Theory 63(10), 6149-6157, 2017), we provide several infinite families of bent, semi-bent functions and Boolean functions of $ n = 2m $ ($ m\ge 4 $ an integer) variables with five to thirteen-valued Walsh spectra by Kasami types, Gold-like types and Maiorana-MacFarland types. The conditions for these functions to be bent and semi-bent are sufficient and necessary. Furthermore, the dual functions of the new bent functions are given. The algebraic degree of the new functions range from $ 4 $ to $ m $ (or $ m+2 $ except for bent and semi-bent functions) and all the functions possess high nonlinearity.

Citation: Wengang Jin, Xiaoni Du, Wenling Wu, Zhixiong Chen. Generic Construction of Boolean Functions with A Few Walsh Transform Values of Any Possible Algebraic Degree. Advances in Mathematics of Communications, doi: 10.3934/amc.2022050
References:
[1]

K. Abdukhalikov, C. Ding and S. Mesnager, et al., Cyclic bent functions and their applications in sequences, IEEE Trans. Inf. Theory, 6 (2021), 3473–3485. doi: 10.1109/TIT.2021.3057896.

[2]

Y. Cai and C. Ding, Binary sequences with optimal autocorrelation, Theory Comput. Sci., 410 (2009), 2316-2322.  doi: 10.1016/j.tcs.2009.02.021.

[3]

A. Canteaut, C. Carlet and P. Charpin, et al., On cryptographic properties of the cosets of r(1, m), IEEE Trans. Inf. Theory, 4 (2001), 1494–1513. doi: 10.1109/18.923730.

[4]

A. CanteautP. Charpin and G. Kyureghyan, A new class of monomial bent functions, Finite Fields Appl., 1 (2008), 221-241. 

[5]

X. Cao and L. Hu, A construction of hyperbent functions with polynomial trace form, Sci. China Math., 54 (2011), 2229-2234.  doi: 10.1007/s11425-011-4264-z.

[6]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 3857 (2006), 1-28.  doi: 10.1007/11617983_1.

[7]

C. Carlet, Boolean functions for cryptography and error correcting codes, Computer Science, and Engineering, Chapter of the Monography Boolean Models and Methods in Mathematics, (2010), 257–397.

[8]

C. Carlet and C. Ding, Highly nonlinear mapping, J. Complexity, 20 (2004), 205-244.  doi: 10.1016/j.jco.2003.08.008.

[9]

C. Carlet and S. Mesnager, On Dillons class H of bent functions, Niho bent functions and O-polynomials, J. Comb. Theory, Ser. A, 118 (2011), 2392-2410.  doi: 10.1016/j.jcta.2011.06.005.

[10]

P. Charpin and G. Gong, Hyperbent functions, Kloosterman sums and Dickson polynomials, IEEE Trans. Inf. Theory, 54 (2008), 4230-4238.  doi: 10.1109/TIT.2008.928273.

[11]

S. Chee and K. Kim, Semi-bent functions, Advances in cryptology-ASIACRYPT'94, LNCS, 917 (1995), 107-118. 

[12]

J. Dillion, Elementary Hadamard Difference Sets, Ph.D. Thesis, Univ. of Maryland, City of College Park, 1974.

[13]

C. Ding, Linear codes from some 2-designs, IEEE Trans. Inf. Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.

[14]

C. DingA. Munemasa and V. Tonchev, Bent vectorial functions, codes and designs, IEEE Trans. Inf. Theory, 65 (2019), 7533-7541.  doi: 10.1109/TIT.2019.2922401.

[15]

R. Gold, Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inf. Theory, 1 (1968), 154-156. 

[16]

T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X.

[17]

T. Helleseth, Correlation of m-sequences and related topics, Sequences and Their Applications, (1999), 49–66.

[18]

W. Jin, X. Du and J. Hu, et al., Boolean functions with a few Walsh transform values. ICAIS 2021, CCIS, 1423 (2021), 642–655.

[19]

K. Khoo, Sequence Design and Construction of Cryptographic Boolean Functions, Ph. D. Thesis, Univ. Waterloo (Canada), 2004.

[20]

G. Leander, Monomial bent functions, IEEE Trans. Inf. Theory, 52 (2006), 738-743.  doi: 10.1109/TIT.2005.862121.

[21]

N. Li, T. Helleseth and X. Tang, et al., Several new classes of bent functions from Dillon exponents, IEEE Trans. Inf. Theory, 59 (2013), 1818–1831. doi: 10.1109/TIT.2012.2229782.

[22]

F. MacWilliams and N. Sloane, The theory of Error-Correcting Codes, Amsterdam-New York-Oxford, 1977.

[23]

S. Mesnager, Bent and hyper-bent functions in polynomial form and their link with some exponential sums and Dickson polynomials, IEEE Trans. Inf. Theory, 57 (2011), 5996-6009.  doi: 10.1109/TIT.2011.2124439.

[24]

S. Mesnager, Several new infinite families of bent functions and their duals, IEEE Trans. Inf. Theory, 60 (2014), 4397-4407.  doi: 10.1109/TIT.2014.2320974.

[25]

Y. Niho, Multi-valued Cross-Correlation Functions Between Two Maximal Linear Recursive Sequences, Ph.D., Univ. Sothern Calif., Los Angeles, 1972.

[26]

J. OlsenR. Scholtz and L. Welch, Bent-function sequences, IEEE Trans. Inf. Theory, 28 (1982), 858-864.  doi: 10.1109/TIT.1982.1056589.

[27]

L. Qu, S. Fu and Q. Dai, et al., New results on the Boolean functions that can be expressed as the sum of two bent functions, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 99-A(8) (2016), 1584–1590.

[28]

O. Rothaus, On bent functions, J. Comb. Theory, Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[29]

C. Tang, Z. Zhou and Y. Qi, et al., Generic construction of bent function and bent idempotents with any possible algebraic degrees, IEEE Trans. Inf. Theory, 63 (2017), 6149–6157. doi: 10.1109/TIT.2017.2717966.

[30]

G. XuX. Cao and S. Xu, Several classes of Boolean functions with few Walsh transform values, AAECC, 28 (2017), 155-176.  doi: 10.1007/s00200-016-0298-3.

[31]

N. Yu and G. Gong, Construction of quadratic bent functions in polynomial forms, IEEE Trans. Inf. Theory, 52 (2006), 3291-3299.  doi: 10.1109/TIT.2006.876251.

[32]

Y. Zeng, C. Carlet and Y. Shan, et al., More balanced Boolean functions with optimal algebraic immunity and nonlinearity and resistance to fast algebraic attacks, IEEE Trans. Inf. Theory, 57 (2011), 6310–6320. doi: 10.1109/TIT.2011.2109935.

[33]

L. Zheng, J. Peng and H. Kan, et al., Several new infinite families of bent functions via second order derivatives, Cryptogr. Commun., 12 (2020), 1143–1160. doi: 10.1007/s12095-020-00436-0.

[34]

Y. Zheng and M. Zhang, Relationships between bent functions and complementary plateaued functions, LNCS, 1787 (1999), 60-75. 

[35]

Z. ZhouN. LiC. Fan and T. Helleseth, Linear codes with two or three weights from quadratic bent functions, Des. Codes Cryptogr., 81 (2016), 283-295.  doi: 10.1007/s10623-015-0144-9.

show all references

References:
[1]

K. Abdukhalikov, C. Ding and S. Mesnager, et al., Cyclic bent functions and their applications in sequences, IEEE Trans. Inf. Theory, 6 (2021), 3473–3485. doi: 10.1109/TIT.2021.3057896.

[2]

Y. Cai and C. Ding, Binary sequences with optimal autocorrelation, Theory Comput. Sci., 410 (2009), 2316-2322.  doi: 10.1016/j.tcs.2009.02.021.

[3]

A. Canteaut, C. Carlet and P. Charpin, et al., On cryptographic properties of the cosets of r(1, m), IEEE Trans. Inf. Theory, 4 (2001), 1494–1513. doi: 10.1109/18.923730.

[4]

A. CanteautP. Charpin and G. Kyureghyan, A new class of monomial bent functions, Finite Fields Appl., 1 (2008), 221-241. 

[5]

X. Cao and L. Hu, A construction of hyperbent functions with polynomial trace form, Sci. China Math., 54 (2011), 2229-2234.  doi: 10.1007/s11425-011-4264-z.

[6]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 3857 (2006), 1-28.  doi: 10.1007/11617983_1.

[7]

C. Carlet, Boolean functions for cryptography and error correcting codes, Computer Science, and Engineering, Chapter of the Monography Boolean Models and Methods in Mathematics, (2010), 257–397.

[8]

C. Carlet and C. Ding, Highly nonlinear mapping, J. Complexity, 20 (2004), 205-244.  doi: 10.1016/j.jco.2003.08.008.

[9]

C. Carlet and S. Mesnager, On Dillons class H of bent functions, Niho bent functions and O-polynomials, J. Comb. Theory, Ser. A, 118 (2011), 2392-2410.  doi: 10.1016/j.jcta.2011.06.005.

[10]

P. Charpin and G. Gong, Hyperbent functions, Kloosterman sums and Dickson polynomials, IEEE Trans. Inf. Theory, 54 (2008), 4230-4238.  doi: 10.1109/TIT.2008.928273.

[11]

S. Chee and K. Kim, Semi-bent functions, Advances in cryptology-ASIACRYPT'94, LNCS, 917 (1995), 107-118. 

[12]

J. Dillion, Elementary Hadamard Difference Sets, Ph.D. Thesis, Univ. of Maryland, City of College Park, 1974.

[13]

C. Ding, Linear codes from some 2-designs, IEEE Trans. Inf. Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.

[14]

C. DingA. Munemasa and V. Tonchev, Bent vectorial functions, codes and designs, IEEE Trans. Inf. Theory, 65 (2019), 7533-7541.  doi: 10.1109/TIT.2019.2922401.

[15]

R. Gold, Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inf. Theory, 1 (1968), 154-156. 

[16]

T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X.

[17]

T. Helleseth, Correlation of m-sequences and related topics, Sequences and Their Applications, (1999), 49–66.

[18]

W. Jin, X. Du and J. Hu, et al., Boolean functions with a few Walsh transform values. ICAIS 2021, CCIS, 1423 (2021), 642–655.

[19]

K. Khoo, Sequence Design and Construction of Cryptographic Boolean Functions, Ph. D. Thesis, Univ. Waterloo (Canada), 2004.

[20]

G. Leander, Monomial bent functions, IEEE Trans. Inf. Theory, 52 (2006), 738-743.  doi: 10.1109/TIT.2005.862121.

[21]

N. Li, T. Helleseth and X. Tang, et al., Several new classes of bent functions from Dillon exponents, IEEE Trans. Inf. Theory, 59 (2013), 1818–1831. doi: 10.1109/TIT.2012.2229782.

[22]

F. MacWilliams and N. Sloane, The theory of Error-Correcting Codes, Amsterdam-New York-Oxford, 1977.

[23]

S. Mesnager, Bent and hyper-bent functions in polynomial form and their link with some exponential sums and Dickson polynomials, IEEE Trans. Inf. Theory, 57 (2011), 5996-6009.  doi: 10.1109/TIT.2011.2124439.

[24]

S. Mesnager, Several new infinite families of bent functions and their duals, IEEE Trans. Inf. Theory, 60 (2014), 4397-4407.  doi: 10.1109/TIT.2014.2320974.

[25]

Y. Niho, Multi-valued Cross-Correlation Functions Between Two Maximal Linear Recursive Sequences, Ph.D., Univ. Sothern Calif., Los Angeles, 1972.

[26]

J. OlsenR. Scholtz and L. Welch, Bent-function sequences, IEEE Trans. Inf. Theory, 28 (1982), 858-864.  doi: 10.1109/TIT.1982.1056589.

[27]

L. Qu, S. Fu and Q. Dai, et al., New results on the Boolean functions that can be expressed as the sum of two bent functions, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 99-A(8) (2016), 1584–1590.

[28]

O. Rothaus, On bent functions, J. Comb. Theory, Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[29]

C. Tang, Z. Zhou and Y. Qi, et al., Generic construction of bent function and bent idempotents with any possible algebraic degrees, IEEE Trans. Inf. Theory, 63 (2017), 6149–6157. doi: 10.1109/TIT.2017.2717966.

[30]

G. XuX. Cao and S. Xu, Several classes of Boolean functions with few Walsh transform values, AAECC, 28 (2017), 155-176.  doi: 10.1007/s00200-016-0298-3.

[31]

N. Yu and G. Gong, Construction of quadratic bent functions in polynomial forms, IEEE Trans. Inf. Theory, 52 (2006), 3291-3299.  doi: 10.1109/TIT.2006.876251.

[32]

Y. Zeng, C. Carlet and Y. Shan, et al., More balanced Boolean functions with optimal algebraic immunity and nonlinearity and resistance to fast algebraic attacks, IEEE Trans. Inf. Theory, 57 (2011), 6310–6320. doi: 10.1109/TIT.2011.2109935.

[33]

L. Zheng, J. Peng and H. Kan, et al., Several new infinite families of bent functions via second order derivatives, Cryptogr. Commun., 12 (2020), 1143–1160. doi: 10.1007/s12095-020-00436-0.

[34]

Y. Zheng and M. Zhang, Relationships between bent functions and complementary plateaued functions, LNCS, 1787 (1999), 60-75. 

[35]

Z. ZhouN. LiC. Fan and T. Helleseth, Linear codes with two or three weights from quadratic bent functions, Des. Codes Cryptogr., 81 (2016), 283-295.  doi: 10.1007/s10623-015-0144-9.

[1]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[2]

Sihem Mesnager, Fengrong Zhang. On constructions of bent, semi-bent and five valued spectrum functions from old bent functions. Advances in Mathematics of Communications, 2017, 11 (2) : 339-345. doi: 10.3934/amc.2017026

[3]

Xiwang Cao, Hao Chen, Sihem Mesnager. Further results on semi-bent functions in polynomial form. Advances in Mathematics of Communications, 2016, 10 (4) : 725-741. doi: 10.3934/amc.2016037

[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]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069

[7]

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

[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]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[10]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete and Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939

[11]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[12]

H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181

[13]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

[14]

Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42.

[15]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete and Continuous Dynamical Systems, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

[16]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2022, 16 (3) : 485-501. doi: 10.3934/amc.2020121

[17]

Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control and Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

[18]

Welington Cordeiro, Manfred Denker, Michiko Yuri. A note on specification for iterated function systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3475-3485. doi: 10.3934/dcdsb.2015.20.3475

[19]

Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control and Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167

[20]

Todd Kapitula, Björn Sandstede. Eigenvalues and resonances using the Evans function. Discrete and Continuous Dynamical Systems, 2004, 10 (4) : 857-869. doi: 10.3934/dcds.2004.10.857

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (85)
  • HTML views (43)
  • Cited by (0)

Other articles
by authors

[Back to Top]