# zbMATH — the first resource for mathematics

The graph of minimal distances of bent functions and its properties. (English) Zbl 1417.94138
Summary: A notion of the graph of minimal distances of bent functions is introduced. It is an undirected graph $$(V,E)$$ where $$V$$ is the set of all bent functions in $$2k$$ variables and $$(f, g) \in E$$ if the Hamming distance between $$f$$ and $$g$$ is equal to $$2^k$$. It is shown that the maximum degree of the graph is equal to $$2^k (2^1 + 1) (2^2 + 1) \cdots (2^k + 1)$$ and all its vertices of maximum degree are quadratic bent functions. It is obtained that the degree of a vertex from Maiorana-McFarland class is not less than $$2^{2k + 1} - 2^k$$. It is proven that the graph is connected for $$2k = 2, 4, 6$$, disconnected for $$2k \geq 10$$ and its subgraph induced by all functions EA-equivalent to Maiorana-McFarland bent functions is connected.

##### MSC:
 94D10 Boolean functions 06E30 Boolean functions
##### Keywords:
Boolean functions; bent functions; minimal distance; affinity
Full Text:
##### References:
  Buryakov M.L., Logachev O.A.: On the affinity level of Boolean functions. Discret. Math. Appl. 15(5), 479-488 (2005). · Zbl 1104.94065  Canteaut, A; Daum, M; Dobbertin, H; Leander, G, Finding nonnormal bent functions, Discret. Appl. Math., 154, 202-218, (2006) · Zbl 1091.94021  Carlet, C, Partially-bent functions, Des. Codes Cryptogr., 3, 135-145, (1993) · Zbl 0772.94005  Carlet C.: Two new classes of bent functions. In: Advances in Cryptology—EUROCRYPT’93, Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993. LNCS, vol. 765, pp. 77-101 (1994). · Zbl 1057.94016  Carlet, C, On the confusion and diffusion properties of maiorana-mcfarlands and extended maiorana-mcfarlands functions, J. Complex., 20, 182-204, (2004) · Zbl 1057.94016  Carlet, C, On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions, IEEE Trans. Inf. Theory, 50, 2178-2185, (2004) · Zbl 1192.94090  Carlet C.: Open problems on binary bent functions. In: Proceedings of the Conference “Open Problems in Mathematical and Computational Sciences”, Istanbul, Turkey, 18-20 Sept (2013). · Zbl 1342.94134  Charpin, P, Normal Boolean functions, J. Complex., 20, 245-265, (2004) · Zbl 1052.94015  Crama C., Hammer P.L.: Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, New York (2010). · Zbl 1196.06001  Cusick T.W., Stanica P.: Cryptographic Boolean Functions and Applications. Academic Press, Elsevier (2009). · Zbl 1173.94002  Dobbertin H.: Construction of bent functions and balanced Boolean functions with high nonlinearity. In: Fast Software Encryption International Workshop (Leuven, Belgium, 14-16 Dec, 1994). LNCS, vol. 1008, pp. 61-74 (1995). · Zbl 1184.94240  Helleseth T., Kholosha A.: Bent functions and their connections to combinatorics. In: Blackburn S.R., Gerke S., Wildon M. (eds.) Surveys in Combinatorics 2013, pp. 91-126. Cambridge University Press, Cambridge (2013). · Zbl 1315.11099  Kolomeec N.A.: An upper bound for the number of bent functions at the distance $$2^k$$ from an arbitrary bent function in $$2k$$ variables. Prikl. Diskretn. Mat. 25, 28-39 (2014) (in Russian).  Kolomeec, NA, Enumeration of the bent functions of least deviation from a quadratic bent function, J. Appl. Ind. Math., 6, 306-317, (2012) · Zbl 1324.94032  Kolomeec, NA, A threshold property of quadratic Boolean functions, J. Appl. Ind. Math., 9, 83-87, (2015)  Kolomeec N.A., Pavlov A.V.: Bent functions on the minimal distance. In: Proceedings of IEEE Region 8 International Conference on Computational Technologies in Electrical and Electronics Engineering (SIBIRCON), 11-15 July 2010, pp. 145-149 (2010).  Leander, G; McGuire, G, Construction of bent functions from near-bent function, J. Comb. Theory Ser. A, 116, 960-970, (2009) · Zbl 1184.94240  Logachev O.A., Sal’nikov A.A., Yashenko V.V.: Boolean functions in coding theory and cryptography, Moscow center of uninterrupted mathematical education, Moscow (2004). Translated in English by AMS in series “Translations of Mathematics Monographs” (2012).  McFarland, RL, A family of difference sets in non-cyclic groups, J. Comb. Theory Ser. A, 15, 1-10, (1973) · Zbl 0268.05011  Potapov, VN, Cardinality spectra of components of correlation immune functions, bent functions, perfect colorings, and codes, Probl. Inf. Transm., 48, 47-55, (2012) · Zbl 1276.06008  Rothaus, O, On bent functions, J. Comb. Theory Ser. A., 20, 300-305, (1976) · Zbl 0336.12012  Tokareva, NN, The group of automorphisms of the set of bent functions, Discret. Math. Appl., 20, 655-664, (2011) · Zbl 1211.94057  Tokareva N.: Bent Functions, Results and Applications to Cryptography. Academic Press, Elsevier (2015). · Zbl 1372.94002  Yashenko V.V.: On the propagation criterion for Boolean functions and on bent functions. Probl. Peredachi Inf. 33(1), 75-86 (1997) (in Russian). · Zbl 1091.94021  Zheng Y., Zhang X.-M.: Plateaued functions. In: ICICS’99. LNCS, vol. 1726, pp. 284-300 (1999). · Zbl 0982.94038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.