# 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:
 [1] Buryakov M.L., Logachev O.A.: On the affinity level of Boolean functions. Discret. Math. Appl. 15(5), 479-488 (2005). · Zbl 1104.94065 [2] Canteaut, A; Daum, M; Dobbertin, H; Leander, G, Finding nonnormal bent functions, Discret. Appl. Math., 154, 202-218, (2006) · Zbl 1091.94021 [3] Carlet, C, Partially-bent functions, Des. Codes Cryptogr., 3, 135-145, (1993) · Zbl 0772.94005 [4] 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 [5] 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 [6] 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 [7] 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 [8] Charpin, P, Normal Boolean functions, J. Complex., 20, 245-265, (2004) · Zbl 1052.94015 [9] Crama C., Hammer P.L.: Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, New York (2010). · Zbl 1196.06001 [10] Cusick T.W., Stanica P.: Cryptographic Boolean Functions and Applications. Academic Press, Elsevier (2009). · Zbl 1173.94002 [11] 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 [12] 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 [13] 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). [14] 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 [15] Kolomeec, NA, A threshold property of quadratic Boolean functions, J. Appl. Ind. Math., 9, 83-87, (2015) [16] 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). [17] Leander, G; McGuire, G, Construction of bent functions from near-bent function, J. Comb. Theory Ser. A, 116, 960-970, (2009) · Zbl 1184.94240 [18] 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). [19] McFarland, RL, A family of difference sets in non-cyclic groups, J. Comb. Theory Ser. A, 15, 1-10, (1973) · Zbl 0268.05011 [20] 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 [21] Rothaus, O, On bent functions, J. Comb. Theory Ser. A., 20, 300-305, (1976) · Zbl 0336.12012 [22] Tokareva, NN, The group of automorphisms of the set of bent functions, Discret. Math. Appl., 20, 655-664, (2011) · Zbl 1211.94057 [23] Tokareva N.: Bent Functions, Results and Applications to Cryptography. Academic Press, Elsevier (2015). · Zbl 1372.94002 [24] 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 [25] 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.