×

zbMATH — the first resource for mathematics

Bent and hyper-bent functions over a field of \(2^{\ell}\) elements. (English. Russian original) Zbl 1235.94049
Probl. Inf. Transm. 44, No. 1, 12-33 (2008); translation from Probl. Peredachi Inf. 44, No. 1, 15-37 (2008).
Summary: We study the parameters of bent and hyper-bent (HB) functions in \(n\) variables over a field \(P = \mathbb{F}_q\) with \(q = 2^{\ell}\) elements, \(\ell > 1\). Any such function is identified with a function \(F: Q \to P\), where \(P < Q = \mathbb{F}_{q^n}\). The latter has a reduced trace representation \(F = \text{tr}_P^Q (\Phi)\), where \(\Phi(x)\) is a uniquely defined polynomial of a special type. It is shown that the most accurate generalization of results on parameters of bent functions from the case \(\ell = 1\) to the case \(\ell > 1\) is obtained if instead of the nonlinearity degree of a function one considers its binary nonlinearity index (in the case \(\ell = 1\) these parameters coincide). We construct a class of HB functions that generalize binary HB functions found in [A. M. Youssef and G. Gong, Advances in cryptology – EUROCRYPT 2001, Lect. Notes Comput. Sci. 2045, 406–419 (2001; Zbl 1013.94544)]; we indicate a set of parameters \(q\) and \(n\) for which there are no other HB functions. We introduce the notion of the period of a function and establish a relation between periods of (hyper-)bent functions and their frequency characteristics.

MSC:
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T06 Polynomials over finite fields
06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Youssef, A.M. and Gong, G., Hyper-Bent Functions, Advances in Cryptology–EUROCRYPT’2001. Proc. 20th Int. Ann. Conf. on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, B. Pfitzmann, Ed., Lect. Notes Comp. Sci., vol. 2045, Berlin: Springer, 2001, pp. 406–419. · Zbl 1013.94544
[2] Solodovnikov, V.I., Bent Functions from a Finite Abelian Group to a Finite Abelian Group, Diskret. Mat., 2002, vol. 14, no. 1, pp. 99–113 [Discrete Math. Appl. (Engl. Transl.), 2002, vol. 12, no. 2, pp. 111–126]. · Zbl 1047.94011
[3] Dillon, J.F., A Survey of Bent Functions, NSA Tech. J. (Special issue), 1972, pp. 191–215.
[4] Rothaus, O.S., On ”Bent” Functions, J. Combin. Theory, Ser. A, 1976, vol. 20, no. 3, pp. 300–305. · Zbl 0336.12012
[5] Kuz’min, A.S., Markov, V.T., Nechaev, A.A., and Shishkov, A.B., Approximation of Boolean Functions by Monomial Ones, Diskret. Mat., 2006, vol. 18, no. 1, pp. 9–29 [Discrete Math. Appl. (Engl. Transl.), 2006, vol. 16, no. 1, pp. 7–28]. · Zbl 1103.94035
[6] Dillon, J.F., Elementary Hadamard Difference Sets, PhD Thesis, Univ. of Maryland, 1974. · Zbl 0346.05003
[7] Carlet, C., Two New Classes of Bent Functions, Advances in Cryptology–EUROCRYPT’93. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, Helleseth, T., Ed., Lect. Notes Comp. Sci., vol. 765, Berlin: Springer, 1994, pp. 77–101. · Zbl 0951.94542
[8] Carlet, C., Generalized Partial Spreads, IEEE Trans. Inform. Theory, 1995, vol. 41, no. 5, pp. 1482–1487. · Zbl 0831.94022
[9] Carlet, C., A Construction of Bent Functions, in Proc. 7th Joint Swedish-Russian Int. Workshop on Information Theory, St. Petersburg, Russia, 1995, pp. 57–59.
[10] Kumar, P.V., Sholtz, R.A., and Welch, L.R., Generalized Bent Functions and Their Properties, J. Combin. Theory, Ser. A, 1985, vol. 40, no. 1, pp. 90–107. · Zbl 0585.94016
[11] Chung, H. and Kumar, P.V., A New General Construction for Generalized Bent Functions, IEEE Trans. Inform. Theory, 1989, vol. 35, no. 1, pp. 206–209. · Zbl 0677.05015
[12] Nyberg, K., Construction of Bent Functions and Difference Sets, Advances in Cryptology–EUROCRYPT’90. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Aarhus, Denmark, Damgård, I.B., Ed., Lect. Notes Comp. Sci., vol. 473, Berlin: Springer, 1991, pp. 151–160. · Zbl 0767.05031
[13] Ambrosimov, A.S., Properties of Bent Functions of q-Valued Logic over Finite Fields, Diskret. Mat., 1994, vol. 6, no. 3, pp. 50–60 [Discrete Math. Appl. (Engl. Transl.), 1994, vol. 4, no. 4, pp. 341–350]. · Zbl 0816.03010
[14] Logachev, O.S., Sal’nikov, A.A., and Yashchenko, V.V., Bent Functions on a Finite Abelian Group, Diskret. Mat., 1997, vol. 9, no. 4, pp. 3–20 [Discrete Math. Appl. (Engl. Transl.), 1997, vol. 7, no. 6, pp. 547–564].
[15] Carlet, C., Hyper-bent Functions, in Proc. PRAGOCRYPT’96, Prague: Czech Tech. Univ. Publ., 1996, pp. 145–155.
[16] Carlet, C. and Gaborit, P., Hyper-bent Functions and Cyclic Codes, J. Combin. Theory, Ser. A, 2006, vol. 113, no. 3, pp. 466–482. · Zbl 1086.94031
[17] Kuzmin, A.S., Nechaev, A.A., and Shishkin, V.A., Bent and Hyper-bent Functions over a Field with 2 Elements, Tr. Diskretn. Mat., 2007, vol. 10, pp. 86–111.
[18] The Cunningham Project, http://homes.cerias.purdue.edu/:_ssw/cun/index.html .
[19] Lidl, R. and Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and Its Applications, vol. 20, Reading: Addison-Wesley, 1983. Translated under the title Konechnye polya, 2 vols., Moscow: Mir, 1988. · Zbl 0554.12010
[20] Glukhov, M.M., Elizarov, V.P., and Nechaev A.A., Algebra, Moscow: Gelios ARV, 2003, Part 2.
[21] MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.
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.