zbMATH — the first resource for mathematics

Approximation of Boolean functions by monomial ones. (English, Russian) Zbl 1103.94035
Discrete Math. Appl. 16, No. 1, 7-28 (2006); translation from Diskretn. Mat. 18, No. 1, 9-29 (2006).
Summary: Every Boolean function of \(n\) variables is identified with a function \(F:{\mathcal Q}\to P\), where \({\mathcal Q} = GF(2^n)\), \(P = GF(2)\). A. Youssef and G. Gong showed that for \(n = 2\lambda\) there exist functions \(F\) which have equally bad approximations not only by linear functions (that is, by functions \(\text{tr}(\mu x)\), where \(\mu\in {\mathcal Q}^*\) and \(\text{tr}:{\mathcal Q}\to P\) is the trace function), but also by proper monomial functions (functions \(\text{tr}(\mu x^\delta)\), where \((\delta, 2^n-1) = 1)\). Such functions \(F\) were called hyper-bent functions (HB functions, HBF ), and for any \(n = 2\lambda\) a non-empty class of HBF having the property \(F(0) = 0\) was constructed. This class consists of the functions \(F(x) = G(X^{2^\lambda-1})\) such that the equation \(F(x) = 1\) has exactly \((2^\lambda - 1)2^{\lambda-1}\) solutions in \(\mathcal Q\). In the present paper, we give some essential restrictions on the parameters of an arbitrary HBF showing that the class of HBF is far less than that of bent functions. In particular, we show that any HBF is a bent function having the degree of nonlinearity \(\lambda\), and for some \(n\) (for instance, if \(\lambda > 2\) and \(2^\lambda=1\) is prime, or \(\lambda\in\{4,9,25, 27\})\) the class of HBF is exhausted by the functions \(F(x) = G(x^{2^{\lambda-1}})\) described by A. Youssef and G. Gong. For \(n = 4\), in addition to 10 HBF listed above there exist 18 more HBF with property \(F(0) = 0\). The question of whether there exist other hyper-bent functions for \(n > 4\) remains open.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30 Boolean functions
13M10 Polynomials and finite commutative rings
Full Text: DOI
[1] S. W. Golomb, On the classification of Boolean functions. Trans. JRE, CT-6, 1959.
[2] Zierler N., J. Algebra 27 pp 147– (1973)
[3] Rothaus O. S., J. Comb. Theory 20 pp 300– (1976)
[4] Dilon J. F., The NSA Technical J. pp 191– (1972)
[5] G. Gong and S. W. Golomb, Transform Domain Analysis of DES. Techn. Rep. Univ. Waterloo, Canada, 1998. · Zbl 0958.94024
[6] M. M. Glukhov, V. P. Elizarov, and A. A. Nechaev. Algebra, v. 2. Helios, Moscow, 2003 (in Russian).
[7] T. Y. Lam, A First Course in Noncommutative Rings. Springer, Berlin, 1991. · Zbl 0728.16001
[8] R. Lidl and H. Niederreiter, Finite Fields, v. 1, 2. Addison-Wesley, London, 1983. · Zbl 0554.12010
[9] F. J. MacWilliams and N. J. A. Sloane, Theory of Error-Correcting Codes. North Holland, Amsterdam, 1977. · Zbl 0369.94008
[10] Logachev O. A., Discrete Math. Appl. 9 pp 245– (1999)
[11] M. M. Postnikov, Introduction to the Theory of Algebraic Numbers. Nauka, Moscow, 1982 (in Russian). · Zbl 0527.12001
[12] A. M. Youssef and G. Gong, Hyper-bent functions. Lect. Notes Comput. Sci. (2001) 2045, 406-419. · Zbl 1013.94544
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.