nach oben

Designs, Codes and Cryptography

Erschienen in:

05.12.2016

The graph of minimal distances of bent functions and its properties

verfasst von: Nikolay Kolomeec

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 \ge 10\) and its subgraph induced by all functions EA-equivalent to Maiorana—McFarland bent functions is connected.

Nächster Artikel Large sets of Kirkman triple systems of prime power sizes

Buryakov M.L., Logachev O.A.: On the affinity level of Boolean functions. Discret. Math. Appl. 15(5), 479–488 (2005).

Canteaut A., Daum M., Dobbertin H., Leander G.: Finding nonnormal bent functions. Discret. Appl. Math. 154(2), 202–218 (2006).MathSciNetCrossRefMATH

Carlet C.: Partially-bent functions. Des. Codes Cryptogr. 3(2), 135–145 (1993).MathSciNetCrossRefMATH

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).

Carlet C.: On the confusion and diffusion properties of Maiorana–McFarlands and extended Maiorana–McFarlands functions. J. Complex. 20, 182–204 (2004).MathSciNetCrossRefMATH

Carlet C.: On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean Functions, with developments on symmetric functions. IEEE Trans. Inf. Theory 50(9), 2178–2185 (2004).CrossRefMATH

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).

Charpin P.: Normal Boolean functions. J. Complex. 20, 245–265 (2004).MathSciNetCrossRefMATH

Crama C., Hammer P.L.: Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, New York (2010).CrossRefMATH

10.

Cusick T.W., Stanica P.: Cryptographic Boolean Functions and Applications. Academic Press, Elsevier (2009).MATH

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).

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).

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 N.A.: Enumeration of the bent functions of least deviation from a quadratic bent function. J. Appl. Ind. Math. 6(3), 306–317 (2012).MathSciNetCrossRef

15.

Kolomeec N.A.: A threshold property of quadratic Boolean functions. J. Appl. Ind. Math. 9(1), 83–87 (2015).MathSciNetCrossRef

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).MathSciNetCrossRefMATH

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 R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15, 1–10 (1973).MathSciNetCrossRefMATH

20.

Potapov V.N.: Cardinality spectra of components of correlation immune functions, bent functions, perfect colorings, and codes. Probl. Inf. Transm. 48(1), 47–55 (2012).MathSciNetCrossRefMATH

21.

Rothaus O.: On bent functions. J. Comb. Theory Ser. A. 20(3), 300–305 (1976).CrossRefMATH

22.

Tokareva N.N.: The group of automorphisms of the set of bent functions. Discret. Math. Appl. 20(5), 655–664 (2011).MathSciNetMATH

23.

Tokareva N.: Bent Functions, Results and Applications to Cryptography. Academic Press, Elsevier (2015).

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).

25.

Zheng Y., Zhang X.-M.: Plateaued functions. In: ICICS’99. LNCS, vol. 1726, pp. 284–300 (1999).

Titel: The graph of minimal distances of bent functions and its properties
verfasst von: Nikolay Kolomeec
Publikationsdatum: 05.12.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0306-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2017

On symmetric BIBDs with the same 3-concurrence

Strongly regular graphs from classical generalized quadrangles

Nonexistence of two classes of generalized bent functions

Consolidation for compact constraints and Kendall tau LP decodable permutation codes

Covering arrays from m-sequences and character sums

Large sets of Kirkman triple systems of prime power sizes