Bent functions and their generalizations

N. N. Tokareva

Prikladnaâ diskretnaâ matematika, no. 11 (2009), pp. 5-17.

Résumé

The lecture is about bent functions – Boolean functions on the maximal possible distances from the set of all affine functions. In the compact form we present main properties, constructions, generalizations of bent functions and discuss main open problems in this area.

Bibliographie

[1] Ambrosimov A. S., “Svoistva bent-funktsii $q$-znachnoi logiki nad konechnymi polyami”, Diskretnaya matematika, 6:3 (1994), 50–60 | MR | Zbl

[2] Logachev O. A., Salnikov A. A., Yaschenko V. V., “Bent-funktsii na konechnoi abelevoi gruppe”, Diskretnaya matematika, 9:4 (1997), 3–20 | MR | Zbl

[3] Solodovnikov V. I., “Bent-funktsii iz konechnoi abelevoi gruppy v konechnuyu abelevu gruppu”, Diskretnaya matematika, 14:1 (2002), 99–113 | MR | Zbl

[4] Tokareva N. N., “Bent-funktsii s bolee silnymi svoistvami nelineinosti: $k$-bent-funktsii”, Diskret. analiz i issled. operatsii. Ser. 1, 14:4 (2007), 76–102 | MR

[5] Tokareva N. N., “Bent-funktsii: rezultaty i prilozheniya. Obzor rabot”, Prikladnaya diskretnaya matematika, 2009, no. 1, 15–37 ; http://mi.mathnet.ru/pdm50

[6] Tokareva N. N., “Obobscheniya bent-funktsii. Obzor rabot”, Diskret. analiz i issled. operatsii (to appear)

[7] Yaschenko V. V., “O kriterii rasprostraneniya dlya bulevykh funktsii i o bent-funktsiyakh”, Probl. peredachi informatsii, 33:1 (1997), 75–86

[8] , Cornell University. Department of Mathematics, 2003, Annual Report 2002–2003 http://www.math.cornell.edu/News/AnnRep/AR2002-pdf

[9] Agievich S. V., “On the representation of bent functions by bent rectangles”, Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics, Proc. (Petrozavodsk, Russia, June 1 – 6, 2000), VSP, Boston, 2000, 121–135; Available at http://arxiv.org/abs/math/0502087

[10] Bernasconi A., Codenotti B., “Spectral analysis of Boolean functions as a graph eigenvalue problem”, IEEE Trans. Computers, 48:3 (1999), 345–351 | DOI | MR

[11] Bernasconi A., Codenotti B., VanderKam J. M., “A characterization of bent functions in terms of strongly regular graphs”, IEEE Trans. Computers, 50:9 (2001), 984–985 | DOI | MR

[12] Carlet C., “Partially-bent functions”, Designs, Codes and Cryptography, 3:2 (1993), 135–145 | DOI | MR | Zbl

[13] Carlet C., “On the higher order nonlinearities of Boolean functions and S-boxes, and their generalizations”, The Fifth Int. Conf. on Sequences and Their Applications – SETA'2008 Proc. (Lexington, Kentucky, USA. September 14 – 18, 2008), Lecture Notes in Comput. Sci., 5203, Springer, Berlin, 2008, 345–367 | Zbl

[14] Carlet C., Ding C., “Highly nonlinear mappings”, J. Complexity, 20:2–3 (2004), 205–244 | DOI | MR | Zbl

[15] Carlet C., Guillot P., “An alternate characterization of the bentness of binary functions, with uniqueness”, Designs, Codes and Cryptography, 14 (1998), 133–140 | DOI | MR | Zbl

[16] Carlet C., Klapper A., “Upper bounds on the numbers of resilient functions and of bent functions”, 23rd Symposium on Information Theory, Proc. The full version will appear in Lecture Notes dedicated to Philippe Delsarte (Benelux, Belgium. May, 2002), 2002, 307–314 ; Available at http://www.cs.engr.uky.edu/~klapper/ps/bent.ps

[17] Chee S., Lee S., Kim ;K., “Semi-bent Functions”, Advances in Cryptology – ASIACRYPT'94 – 4th International Conference on the Theory and Applications of Cryptology, Proc. (Wollongong, Australia. November 28 – December 1, 1994), Lecture Notes in Comput. Sci., 917, Springer, Berlin, 1995, 107–118 | MR | Zbl

[18] Detombe J., Tavares S., “Constructing large cryptographically strong S-boxes”, Advances in Cryptology – AUSCRYPT'92, Proc. (Gold Coast, Queensland, Australia. December 13 – 16, 1992), Lecture Notes in Comput. Sci., 718, Springer, Berlin, 1993, 165–181 | Zbl

[19] Dillon J. F., “A survey of bent functions”, The NSA Technical J., Special Issue (1972), 191–215

[20] DillonJ. F., Elementary Hadamard Difference sets, Ph. D. Thesis, Univ. of Maryland, 1974

[21] Dobbertin H., Leander G., “A survey of some recent results on bent functions”, Sequences and their applications. – SETA Third Int. conference, Revised selected papers (Seoul, Korea, October 24–28, 2004), Lecture Notes in Comput. Sci., 3486, Springer, Berlin, 2005, 1–29 | Zbl

[22] Dobbertin H., Leander G., Cryptographer's Toolkit for Construction of 8-Bit Bent Functions Cryptology ePrint Archive, available at , Report 2005/089 http://eprint.iacr.org/

[23] Dobbertin H., Leander G., Canteaut\;A., et al., “Construction of Bent Functions via Niho Power Functions”, J. Combin. Theory. Ser. A, 113:5 (2006), 779–798 ; Available at http://www-rocq.inria.fr/secret/Anne.Canteaut/Publications/index-pub.html | DOI | MR | Zbl

[24] Gong G., Golomb S. W., “Transform Domain Analysis of DES”, IEEE Trans. Inform. Theory, 45:6 (1999), 2065–2073 | DOI | MR | Zbl

[25] Kumar P. V., Scholtz R. A., Welch L. R., “Generalized bent functions and their properties”, J. Combin. Theory. Ser. A, 40:1 (1985), 90–107 | DOI | MR | Zbl

[26] Classification of Boolean Quartics Forms in eight Variables (Langevin P.), , 2008 http://langevin.univ-tln.fr/project/quartics/

[27] Langevin P., Leander G., Counting all bent functions in dimension 8, Workshop on Coding and Cryptograpy, 2009, to appear

[28] Leveiller S., Zemor G., Guillot P., and Boutros J., “A new cryptanalytic attack for PN-generators filtered by a Boolean function”, Selected Areas of Cryptography — SAC Proc., Lecture Notes in Comput. Sci., 2595, 2002, 232–249 | MR

[29] McFarland R. L., “A family of difference sets in non-cyclic groups”, J. Combin. Theory. Ser. A, 15:1 (1973), 1–10 | DOI | MR | Zbl

[30] Meng Q., Zhang H., Yang M. C., Cui J., On the degree of homogeneous bent functions, Available at , 2004/284 http://eprint.iacr.org

[31] Nyberg K., “Perfect nonlinear $S$-boxes”, Advances in cryptology – EUROCRYPT' Int. conference on the theory and application of cryptographic techniques, Proc. (Brighton, UK, April 8 – 11, 1991), Lecture Notes in Comput. Sci., 547, Springer, Berlin, 1991, 378–386 | MR

[32] Olejár D., Stanek M., “On cryptographic properties of random Boolean functions”, J. Universal Computer Science, 4:8 (1998), 705–717 | MR | Zbl

[33] Poinsot L., “Multidimensional bent functions”, GESTS International Transactions on Computer Science and Engeneering, 18:1 (2005), 185–195

[34] Poinsot L., Harari S., “Generalized Boolean bent functions”, Progress in Cryptology – Indocrypt 2004, Proc. (Chennai (Madras), India. December 20 – 22, 2004), Lecture Notes in Comput. Sci., 3348, Springer, 2004, 107–119 | MR | Zbl

[35] Qu C., Seberry J., Pieprzyk J., “Homogeneous bent functions”, Discrete Appl. Math., 102:1–2 (2000), 133–139 | MR | Zbl

[36] Rothaus O., “On bent functions”, IDA CRD W. P., 169 (1966)

[37] Rothaus O., “On bent functions”, J. Combin. Theory. Ser. A, 20:3 (1976), 300–305 | DOI | MR | Zbl

[38] Schmidt K-U., “Quaternary Constant-Amplitude Codes for Multicode CDMA”, IEEE International Symposium on Information Theory – ISIT', Proc. (Nice, France. June 24 – 29, 2007), 2007, 2781–2785; Available at http://arxiv.org/abs/cs.IT/0611162

[39] Yang M., Meng Q., Zhang\;H., Evolutionary design of trace form bent functions Cryptology ePrint Archive, available at , Report 2005/322 http://eprint.iacr.org/

[40] Youssef A., Gong G., “Hyper-bent functions”, Advances in cryptology – EUROCRYPT' Int. conference on the theory and application of cryptographic techniques, Proc. (Innsbruk, Austria, May 6 – 10, 2001), Lecture Notes in Comput. Sci., 2045, Springer, Berlin, 2001, 406–419 | MR | Zbl