Generalizations of bent functions

N. N. Tokareva

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 1, pp. 34-64.

Résumé

Bent functions (Boolean functions with extremal nonlinear properties) are intensively studied at present since they have numerous applications in cryptography, coding theory, and other areas. New statement of problems lead to appearance of many new generalizations of bent functions which are not well known to the specialists in Boolean functions. In the paper, a systematic survey of them is given. Bibl. 63.

Détail

Keywords: Boolean function, the Walsh–Hadamard transform, nonlinearity, bent function, CDMA.

Bibliographie

[1] Ageev D. V., “Osnovy teorii lineinoi selektsii. Kodovoe razdelenie kanalov”, Sb. nauchn. tr. Leningradskogo eksperimentalnogo in-ta svyazi, Izd-vo eksperimentalnogo in-ta svyazi, L., 1935, 3–35

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

[3] Ivanov A. V., “Ispolzovanie privedënnogo predstavleniya bulevykh funktsii pri postroenii ikh nelineinykh approksimatsii”, Vestn. Tomskogo gos. universiteta. Prilozhenie, 2007, no. 23, 31–35

[4] Ivanov A. V., “Monomialnye priblizheniya platovidnykh funktsii”, Prikl. diskret. matematika, 1:1 (2008), 10–14

[5] Ivanov A. V., “Blizost k klassu monomialnykh approksimatsii privedennogo predstavleniya bulevoi funktsii v zavisimosti ot vybora bazisa, v kotorom ono zadano”, Prikl. diskret. matematika. Prilozhenie, 2009, no. 1, 7–9

[6] Kuzmin A. S., Markov V. T., Nechaev A. A., Shishkov A. B., “Priblizhenie bulevykh funktsii monomialnymi”, Diskret. matematika, 18:1 (2006), 9–29 | MR | Zbl

[7] Kuzmin A. S., Nechaev A. A., Shishkin V. A., “Bent- i giperbent-funktsii nad konechnym polem”, Tr. po diskret. matematike, 10, 2007, 97–122

[8] Kuzmin A. S., Markov V. T., Nechaev A. A., Shishkin V. A., Shishkov A. B., “Bent-funktsii i giperbent-funktsii nad polem iz $2^l$ elementov”, Probl. peredachi inform., 44:1 (2008), 15–37 | MR | Zbl

[9] Kuzmin A. S., Nechaev A. A., Shishkin V. A., “Parametry (giper-) bent-funktsii nad polem iz $2^l$ elementov”, Tr. po diskret. matematike, 11, no. 1, 2008, 47–59

[10] Logachëv O. A., Salnikov A. A., Yaschenko V. V., “Bent-funktsii na konechnoi abelevoi gruppe”, Diskret. matematika, 9:4 (1997), 3–20 | MR | Zbl

[11] Logachëv O. A., Salnikov A. A., Yaschenko V. V., “Kriptograficheskie svoistva diskretnykh funktsii”, Mat. konf. “Moskovskii universitet i razvitie kriptografii v Rossii” (MGU, 2002), MTsNMO, M., 2003, 174–199

[12] Logachëv O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2004, 470 pp. | MR

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

[14] 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

[15] Tokareva N. N., “O kvadratichnykh approksimatsiyakh v blochnykh shifrakh”, Probl. peredachi inform., 44:3 (2008), 105–127 | MR | Zbl

[16] Tokareva N. N., “Opisanie $k$-bent-funktsii ot chetyrëkh peremennykh”, Diskret. analiz i issled. operatsii, 15:4 (2008), 74–83 | MR

[17] Tokareva N. N., “Bent-funktsii: rezultaty i prilozheniya. Obzor rabot”, Prikl. diskret. matematika, 2009, no. 1, 15–37

[18] Adams C., Tavares S., “The structured design of cryptographycally good\break S-boxes”, J. Cryptology, 3:1 (1990), 27–43 | DOI | MR

[19] Agievich S. V., “Bent rectangles”, NATO advanced study institute on Boolean functions in cryptology and information security, Proc. (Zvenigorod, Russia, September 8–18, 2007), IOS Press, Netherlands, 2008, 3–22 ; arxiv: 0804.0209[math.CO] | Zbl

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

[21] Carlet C., “Hyper-bent functions”, Intern. Conf. on the Theory and Applications of Cryptology, PRAGOCRYPT' 96, Czech Tech. Univ. Publ. House, Prague, 1996, 149–155 | MR

[22] Carlet C., “On the higher order nonlinearities of Boolean functions and S-boxes, and their generalizations”, 5th Intern. Conf. on Sequences and their Applications, SETA' 2008, Proc. (Lexington, Kentucky, USA, September 14–18, 2008), Lect. Notes Comput. Sci., 5203, Springer-Verl., Berlin, 2008, 345–367 | Zbl

[23] Carlet C., “Boolean functions for cryptography and error correcting codes”, Chapter of the monograph, Boolean Methods and Models, eds. P. Hammer, Y. Crama, Cambridge Univ. Press, Cambridge (to appear)

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

[25] Carlet C., Ding C., “Nonlinearities of S-boxes”, Finite Fields Appl., 13:1 (2007), 121–135 | DOI | MR | Zbl

[26] Carlet C., Gaborit P., “Hyper-bent functions and cyclic codes”, J. Comb. Theory Ser. A, 113:3 (2006), 466–482 | DOI | MR | Zbl

[27] Carlet C., Prouff E., “On plateaued functions and their constructions”, Fast software encryption, FSE' 2003, Proc. 10th Int. Workshop (Lund, Sweden, February 24–26, 2003), Lect. Notes Comput. Sci., 2887, Springer-Verl., Berlin, 2003, 54–73 | Zbl

[28] Charnes C., Rotteler M., Beth T., “Homogeneous bent functions, invariants, and designs”, Des. Codes Cryptography, 26:1–3 (2002), 139–154 | DOI | MR | Zbl

[29] Chee S., Lee S., Kim K., “Semi-bent functions”, Advances in cryptology, ASIACRYPT' 94, Proc. 4th Int. Conf. on the Theory and Applications of Cryptology (Wollongong, Australia, November 28 – December 1, 1994), Lect. Notes Comput. Sci., 917, Springer-Verl., Berlin, 1995, 107–118 | MR | Zbl

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

[31] Dillon J. F., McGuire G., “Near bent functions on a hyperplane”, Finite Fields Appl., 14 (2008), 715–720 | DOI | MR | Zbl

[32] Dobbertin H., Leander G., Cryptographer's toolkit for construction of 8-bit bent functions, Cryptology ePrint Archive, Report 2005/089 http://eprint.iacr.org/2005/089

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

[34] Helleseth T., Kalosha A., Monomial and quadratic bent functions over the finite fields of odd characteristic, Reports in informatics, 2005. Report 310, University of Bergen, Bergen, 2005, 34 pp.

[35] Hou X. D., “$q$-Ary bent functions constructed from chain rings”, Finite Fields Appl., 4:1 (1998), 55–61 | DOI | MR | Zbl

[36] Hou X. D., “$p$-Ary and $q$-ary versions of certain results about bent functions and resilient functions”, Finite Fields Appl., 10:4 (2004), 566–582 | DOI | MR | Zbl

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

[38] Leander N. G., McGuire G., “Construction of bent functions from near-bent functions”, J. Comb. Theory Ser. A, 116:4 (2009), 960–970 | DOI | MR | Zbl

[39] Leveiller S., Zemor G., Guillot P., Boutros J., “A new cryptanalytic attack for PN-generators filtered by a Boolean function”, Selected areas of cryptography, SAC' 2002, Proc. (Newfoundland, Canada, August 15–16, 2002), Lect. Notes Comput. Sci., 2595, Springer-Verl., Berlin, 2003, 232–249 | MR | Zbl

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

[41] Matsufuji S., Imamura K., “Real-valued bent functions and its application to the design of balanced quadriphase sequences with optimal correlation properties”, Intern. Symposium on Applied Algebra, Algebraic Algorithms and Error-correcting Codes, AAECC-8, Proc. (Tokyo, Japan, August 20–24, 1990), Lect. Notes Comput. Sci., 508, Springer-Verl., Berlin, 1990, 106–112 | MR

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

[43] Meng Q., Zhang H., Yang M. C., Cui J., “On the degree of homogeneous bent functions”, Discr. Appl. Math., 155:5 (2007), 665–669 | DOI | MR | Zbl

[44] Olsen J. D., Scholtz R. A., Welch L. R., “Bent-function sequences”, IEEE Trans. Inform. Theory, 28:6 (1982), 858–864 | DOI | MR | Zbl

[45] Parker M. G., “The constabent properties of Golay–Davis–Jedwab sequences”, IEEE Intern. Symp. on Information Theory, ISIT' 2000, Proc. (Sorrento, Italy, June 25–30, 2000), Institute of Electrical and Electronics Engineers, New York, 2000, 302

[46] Parker M. G., Pott A., “On Boolean functions which are bent and negabent”, Sequences, Subsequences, and Consequences, SSC' 2007, Proc. Intern. Workshop (Los Angeles, CA, USA, May 3 – June 2, 2007), Lect. Notes Comput. Sci., 4893, Springer-Verl., Berlin, 2007, 9–23 | Zbl

[47] Paterson K. G., “On codes with low peak-to-average power ratio for Multicode CDMA”, IEEE Trans. Inform. Theory, 50:3 (2004), 550–558 | DOI | MR

[48] Poinsot L., “Multidimensional bent functions”, GESTS Intern. Transactions on Comput. Sci. Eng., 18:1 (2005), 185–195

[49] Poinsot L., Harari S., “Nonabelian bent functions”, IEEE Trans. Inform. Theory (to appear)

[50] Poinsot L., Harari S., “Generalized Boolean bent functions”, Progress in cryptology, Indocrypt' 2004, Proc. (Chennai (Madras), India, December 20–22, 2004), Lect. Notes Comput. Sci., 3348, Springer-Verl., Berlin, 2005, 107–119 | MR

[51] Preneel B., van Leekwijck W., van Linden L., Govaerts R., Vandevalle J., “Propagation characteristics of Boolean functions”, Adv. Cryptology, EUROCRYPT' 1990, Proc. Intern. Conf. on the Theory and Application of Cryptographic Techniques (Aarhus, Denmark, May 21–24, 1990), Lect. Notes Comput. Sci., 473, Springer-Verl., Berlin, 1991, 161–173 | MR

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

[53] Riera C., Parker M. G., “Generalised bent criteria for Boolean functions (I)”, IEEE Trans. Inform. Theory, 52:9 (2006), 4142–4159 | DOI | MR

[54] Savicky P., “On the bent Boolean functions that are symmetric”, Eur. J. Comb., 15:4 (1994), 407–410 | DOI | MR | Zbl

[55] Schmidt K.-U., “Quaternary constant-amplitude codes for multicode CDMA”, IEEE Intern. Symp. on Information Theory, ISIT' 2007, Proc. (Nice, France, June 24–29, 2007), 2007, 2781–2785; arxiv: cs/0611162[cs.IT]

[56] Solé P., Tokareva N., Connections between quaternary and binary bent functions, Cryptology ePrint Archive, Report 2009/544 , 13 pp. http://eprint.iacr.org/2009/544

[57] Wada T., “Characteristic of bit sequences applicable to constant amplitude orthogonal multicode systems”, IEICE Trans. Fundamentals, E83-A:11 (2000), 2160–2164

[58] Wang X., Zhou J., “Generalized partially bent functions”, Future generation communication and networking, Proc. (Jeju-Island, Korea, December 6–8, 2007), 2007, 16–21

[59] Xia T., Seberry J., Pieprzyk J., Charnes C., “Homogeneous bent functions of degree $n$ in $2n$ variables do not exist for $n>3$”, Discrete Appl. Math., 142:1–3 (2004), 127–132 | DOI | MR | Zbl

[60] Youssef A., Gong G., “Hyper-bent functions”, Adv. Cryptology, EUROCRYPT' 2001, Proc. Intern. Conf. on the Theory and Application of Cryptographic Techniques (Innsbruk, Austria, May 6–10, 2001), Lect. Notes Comput. Sci., 2045, Springer-Verl., Berlin, 2001, 406–419 | MR | Zbl

[61] Youssef A. M., “Generalized hyper-bent functions over $GF(p)$”, Discrete Appl. Math., 155:8 (2007), 1066–1070 | DOI | MR | Zbl

[62] Zheng Y., Zhang X.-M., “Relationships between bent functions and complementary plateaued functions”, Proc. Intern. Conf. on Information Security and Cryptology, ICISC' 99 (Seoul, Korea, December 9–10, 1999), Lect. Notes Comput. Sci., 1787, Springer-Verl., Berlin, 2000, 60–75 | MR

[63] Zheng Y., Zhang X.-M., “On plateaued functions”, IEEE Trans. Inform. Theory, 47:3 (2001), 1215–1223 | DOI | MR | Zbl