×

zbMATH — the first resource for mathematics

Distance duality on some classes of Boolean functions. (English) Zbl 1432.94228
Summary: A function \(f\) is at a distance \(d(f, \mathcal S)\) from a set \(\mathcal S\) of Boolean functions if the minimum Hamming distance between \(f\) and all \(g\in\mathcal S\) is \(d(f, \mathcal S)\). Given a set \(\mathcal S\) of Boolean functions, the set \(\hat{\mathcal S}\) of functions is said to have a maximum distance from \(\mathcal S\) if it has the property that for all \(f\in \hat{\mathcal S}\), \(d(f, \mathcal S)\) is maximum. The well-studied bent Boolean functions \((\mathcal S)\) are defined to have a maximum distance from the set of affine functions \((\hat{ \mathcal S})\). N. Tokareva [Bent functions. Results and applications to cryptography. Amsterdam: Elsevier/Academic Press (2015; Zbl 1372.94002)] showed the converse is also true. That is, \(\mathcal S\) is a maximum distance from \(\hat{\mathcal S}\). In such a case, we say that \(\mathcal S\) and \(\hat{\mathcal S}\) are mutually maximally distant.
We introduce partition set functions, which include symmetric functions, rotation symmetric functions, self-anti-dual-functions, linear structure functions, and degenerate functions. We show that partition set functions associated with a partition on the domain \(\mathbb F^n_2\) are mutually maximally distant from another set \(\hat{\mathcal S}\) of functions. We show that the distributions of weights in \(\hat{\mathcal S}\) is binomial and centered at \(2^{n-1}\), the point at which a function is perfectly balanced.
Because there is much interest in symmetric functions, we consider this special case, and verify a prior enumeration of functions that are maximally distant from symmetric functions [I. Ivchenko, Yu. I. Medvedev, and V. A. Mironova, “Symmetric Boolean functions and their metric properties matrices of transitions of differences when using some modular groups” (Russian), Mat. Vopr. Kriptogr. 4, No. 4, 49–63 (2013)] (we call them maximally asymmetric functions). We characterize balanced maximally asymmetric functions. A similar analysis is done on rotation symmetric functions.

MSC:
94D10 Boolean functions
06E30 Boolean functions
PDF BibTeX XML Cite