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

Natalia Tokareva

doi:10.3934/amc.2011.5.609

Article Contents

2011, Volume 5, Issue 4: 609-621. Doi: 10.3934/amc.2011.5.609

This issue Previous Article The merit factor of binary arrays derived from the quadratic character Next Article Explicit formulas for real hyperelliptic curves of genus 2 in affine representation

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

Received: June 30, 2010

Revised: July 31, 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

References

[1]	S. V. Agievich, On the representation of bent functions by bent rectangles, in "Proc. of the Int. Petrozavodsk Conf. on Probabilistic Methods in Discrete Mathematics,'' (2000), 121-135; preprint, arXiv:math/0502087v1
[2]	A. Canteaut and P. Charpin, Decomposing bent functions, IEEE Trans. Inform. Theory, 49 (2003), 2004-2019.doi: 10.1109/TIT.2003.814476.
[3]	A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Finding nonnormal bent functions, Discrete Appl. Math., 154 (2006), 202-218.doi: 10.1016/j.dam.2005.03.027.
[4]	C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities, in "Applied Algebra, Algebraic Algorithms and Error Correcting Codes,'' Las Vegas, USA, (2006), 1-28.
[5]	C. Carlet and A. Klapper, Upper bounds on the numbers of resilient functions and of bent functions, in "Proc. of 23rd Symposium on Information Theory,'' (2002), 307-314.
[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-431.doi: 10.3934/amc.2008.2.421.
[7]	J. F. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D Thesis, University of Maryland, 1974.
[8]	V. E. Gmurman, "Probability Theory and Mathematical Statistics,'' Higher Educ., Moscow, 2006.
[9]	P. Langevin, G. Leander, Counting all bent functions in dimension eight 99270589265934370305785861242880, Des. Codes Crypt., 59 (2011), 193-205.
[10]	R. L. McFarland, A family of difference sets in non-cyclic groups, J. Combin. Theory Ser. A, 15 (1973), 1-10.doi: 10.1016/0097-3165(73)90031-9.
[11]	O. Rothaus, On bent functions, IDA CRD W. P. No. 169, 1966.
[12]	O. Rothaus, On bent functions, J. Combin. Theory Ser. A, 20 (1976), 300-305.doi: 10.1016/0097-3165(76)90024-8.
[13]	N. N. Tokareva, Automorphism group of the set of all bent functions, Discrete Math. Appl., 20 (2010), 655-664.doi: 10.1515/DMA.2010.040.
[14]	N. N. Tokareva, Generalizations of bent functions. A survey, Discrete Anal. Oper. Res., 17 (2010), 34-64.
[15]	N. Tokareva, "Nonlinear Boolean Functions: Bent Functions and Their Generalizations,'' LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011.
[16]	L. Wang and J. Zhang, A best possible computable upper bound on bent functions, J. West China, 33 (2004), 113-115.