American Institute of Mathematical Sciences

Advanced
November  2011, 5(4): 609-621. doi: 10.3934/amc.2011.5.609

On the number of bent functions from iterative constructions: lower bounds and hypotheses

Natalia Tokareva 1,

1. 

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Koptyuga 4, 630090, Novosibirsk, Russian Federation, and Novosibirsk State University, st. Pirogova 2, 630090, Novosibirsk, Russian Federation

Received  July 2010 Revised  August 2011 Published  November 2011

In the paper we study lower bounds on the number of bent functions that can be obtained by iterative constructions, namely by the construction proposed by A. Canteaut and P. Charpin in 2003. The number of bent iterative functions is expressed in terms of sizes of finite sets and it is shown that evaluation of this number is closely connected to the problem of decomposing Boolean function into sum of two bent functions. A new lower bound for the number of bent iterative functions that is supposed to be asymptotically tight is given. Applying Monte-Carlo methods the number of bent iterative functions in $8$ variables is counted. Based on the performed calculations several hypotheses on the asymptotic value of the number of all bent functions are formulated.
Keywords: bent sum decomposition, iterative construction, asymptotic value, Monte–Carlo methods., Bent function.
Mathematics Subject Classification: Primary: 06E30; Secondary: 94A6.
Citation: Natalia Tokareva. On the number of bent functions from iterative constructions: lower bounds and hypotheses. Advances in Mathematics of Communications, 2011, 5 (4) : 609-621. doi: 10.3934/amc.2011.5.609
References:
[1]

S. V. Agievich, On the representation of bent functions by bent rectangles,, in, (2000), 121.   Google Scholar

[2]

A. Canteaut and P. Charpin, Decomposing bent functions,, IEEE Trans. Inform. Theory, 49 (2003), 2004.  doi: 10.1109/TIT.2003.814476.  Google Scholar

[3]

A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Finding nonnormal bent functions,, Discrete Appl. Math., 154 (2006), 202.  doi: 10.1016/j.dam.2005.03.027.  Google Scholar

[4]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities,, in, (2006), 1.   Google Scholar

[5]

C. Carlet and A. Klapper, Upper bounds on the numbers of resilient functions and of bent functions,, in, (2002), 307.   Google Scholar

[6]

J.-J. Climent, F. García and V. Requena, On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables,, Adv. Math. Commun., 2 (2008), 421.  doi: 10.3934/amc.2008.2.421.  Google Scholar

[7]

J. F. Dillon, "Elementary Hadamard Difference Sets,'', Ph.D Thesis, (1974).   Google Scholar

[8]

V. E. Gmurman, "Probability Theory and Mathematical Statistics,'', Higher Educ., (2006).   Google Scholar

[9]

P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880,, Des. Codes Crypt., 59 (2011), 193.   Google Scholar

[10]

R. L. McFarland, A family of difference sets in non-cyclic groups,, J. Combin. Theory Ser. A, 15 (1973), 1.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar

[11]

O. Rothaus, On bent functions,, IDA CRD W. P. No. 169, (1966).   Google Scholar

[12]

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

[13]

N. N. Tokareva, Automorphism group of the set of all bent functions,, Discrete Math. Appl., 20 (2010), 655.  doi: 10.1515/DMA.2010.040.  Google Scholar

[14]

N. N. Tokareva, Generalizations of bent functions. A survey,, Discrete Anal. Oper. Res., 17 (2010), 34.   Google Scholar

[15]

N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'', LAP LAMBERT Academic Publishing, (2011).   Google Scholar

[16]

L. Wang and J. Zhang, A best possible computable upper bound on bent functions,, J. West China, 33 (2004), 113.   Google Scholar

show all references

References:
[1]

S. V. Agievich, On the representation of bent functions by bent rectangles,, in, (2000), 121.   Google Scholar

[2]

A. Canteaut and P. Charpin, Decomposing bent functions,, IEEE Trans. Inform. Theory, 49 (2003), 2004.  doi: 10.1109/TIT.2003.814476.  Google Scholar

[3]

A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Finding nonnormal bent functions,, Discrete Appl. Math., 154 (2006), 202.  doi: 10.1016/j.dam.2005.03.027.  Google Scholar

[4]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities,, in, (2006), 1.   Google Scholar

[5]

C. Carlet and A. Klapper, Upper bounds on the numbers of resilient functions and of bent functions,, in, (2002), 307.   Google Scholar

[6]

J.-J. Climent, F. García and V. Requena, On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables,, Adv. Math. Commun., 2 (2008), 421.  doi: 10.3934/amc.2008.2.421.  Google Scholar

[7]

J. F. Dillon, "Elementary Hadamard Difference Sets,'', Ph.D Thesis, (1974).   Google Scholar

[8]

V. E. Gmurman, "Probability Theory and Mathematical Statistics,'', Higher Educ., (2006).   Google Scholar

[9]

P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880,, Des. Codes Crypt., 59 (2011), 193.   Google Scholar

[10]

R. L. McFarland, A family of difference sets in non-cyclic groups,, J. Combin. Theory Ser. A, 15 (1973), 1.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar

[11]

O. Rothaus, On bent functions,, IDA CRD W. P. No. 169, (1966).   Google Scholar

[12]

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

[13]

N. N. Tokareva, Automorphism group of the set of all bent functions,, Discrete Math. Appl., 20 (2010), 655.  doi: 10.1515/DMA.2010.040.  Google Scholar

[14]

N. N. Tokareva, Generalizations of bent functions. A survey,, Discrete Anal. Oper. Res., 17 (2010), 34.   Google Scholar

[15]

N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'', LAP LAMBERT Academic Publishing, (2011).   Google Scholar

[16]

L. Wang and J. Zhang, A best possible computable upper bound on bent functions,, J. West China, 33 (2004), 113.   Google Scholar

[1]

Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027
[2]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020092
[3]

Joan-Josep Climent, Francisco J. García, Verónica Requena. On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables. Advances in Mathematics of Communications, 2008, 2 (4) : 421-431. doi: 10.3934/amc.2008.2.421
[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]

Jacques Wolfmann. Special bent and near-bent functions. Advances in Mathematics of Communications, 2014, 8 (1) : 21-33. doi: 10.3934/amc.2014.8.21
[7]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[8]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[9]

Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[10]

Claude Carlet, Fengrong Zhang, Yupu Hu. Secondary constructions of bent functions and their enforcement. Advances in Mathematics of Communications, 2012, 6 (3) : 305-314. doi: 10.3934/amc.2012.6.305
[11]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020069
[12]

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

Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683
[14]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[15]

Samir Hodžić, Enes Pasalic. Generalized bent functions -sufficient conditions and related constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 549-566. doi: 10.3934/amc.2017043
[16]

Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249
[17]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425
[18]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control & Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012
[19]

Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[20]

Chjan C. Lim, Joseph Nebus, Syed M. Assad. Monte-Carlo and polyhedron-based simulations I: extremal states of the logarithmic N-body problem on a sphere. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (37)
  • HTML views (0)
  • Cited by (17)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences