Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 3/2017

05-12-2016

The graph of minimal distances of bent functions and its properties

Author: Nikolay Kolomeec

Published in: Designs, Codes and Cryptography | Issue 3/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
next article Large sets of Kirkman triple systems of prime power sizes
Literature
1.
Buryakov M.L., Logachev O.A.: On the affinity level of Boolean functions. Discret. Math. Appl. 15(5), 479–488 (2005).
2.
3.
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).
5.
Carlet C.: On the confusion and diffusion properties of Maiorana–McFarlands and extended Maiorana–McFarlands functions. J. Complex. 20, 182–204 (2004).MathSciNetCrossRefMATH
6.
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
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).
8.
9.
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.
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.
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.
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.
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).
Metadata
Title
The graph of minimal distances of bent functions and its properties
Author
Nikolay Kolomeec
Publication date
05-12-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 3/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0306-4

Other articles of this Issue 3/2017

Designs, Codes and Cryptography 3/2017 Go to the issue

OriginalPaper

Mapping prefer-opposite to prefer-one de Bruijn sequences

OriginalPaper

Covering arrays from m-sequences and character sums

OriginalPaper

Nonexistence of two classes of generalized bent functions

OriginalPaper

New bounds of permutation codes under Hamming metric and Kendall’s -metric

OriginalPaper

On symmetric BIBDs with the same 3-concurrence

OriginalPaper

On equivalence of negaperiodic Golay pairs

Premium Partner

    Image Credits