×

Finding nonnormal bent functions. (English) Zbl 1091.94021

Summary: The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in \(n\) variables is called normal if there exists an affine subspace of dimension \(n\)/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in J.F. Dillon and H. Dobbertin [Finite Fields Appl. 10, No. 3, 342–389 (2004; Zbl 1043.05024)], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.

MSC:

94A60 Cryptography
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03B70 Logic in computer science

Citations:

Zbl 1043.05024
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Canteaut, A.; Charpin, P., Decomposing bent functions, IEEE Trans. Inform. Theory, 49, 8, 2004-2019 (2003) · Zbl 1184.94230
[2] C. Carlet, Two new classes of bent functions, in: Advances in Cryptology—EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765, Springer, Berlin, 1994, pp. 77-101.; C. Carlet, Two new classes of bent functions, in: Advances in Cryptology—EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765, Springer, Berlin, 1994, pp. 77-101. · Zbl 0951.94542
[3] Carlet, C., On cryptographic complexity of Boolean functions, (Finite Fields with Applications to Coding Theory, Cryptography and Related Areas (Proceedings of Fq6) (2002), Springer: Springer Berlin), 53-69 · Zbl 1021.94524
[4] P. Charpin, Normal Boolean functions, J. Complexity 20 (2004) 245-265 (special issue) (“Complexity Issues in Cryptography and Coding Theory”, dedicated to Prof. Harald Niederreiter on the occasion of his 60th birthday.); P. Charpin, Normal Boolean functions, J. Complexity 20 (2004) 245-265 (special issue) (“Complexity Issues in Cryptography and Coding Theory”, dedicated to Prof. Harald Niederreiter on the occasion of his 60th birthday.)
[5] J.F. Dillon, Elementary hadamard difference sets, Ph.D. Thesis, University of Maryland, USA, 1974.; J.F. Dillon, Elementary hadamard difference sets, Ph.D. Thesis, University of Maryland, USA, 1974. · Zbl 0346.05003
[6] J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, Finite Fields Appl. 10 (2004) 342-389.; J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, Finite Fields Appl. 10 (2004) 342-389. · Zbl 1043.05024
[7] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption—FSE’94, Lecture Notes in Computer Science, vol. 1008, Springer, Berlin, 1995, pp. 61-74.; H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption—FSE’94, Lecture Notes in Computer Science, vol. 1008, Springer, Berlin, 1995, pp. 61-74. · Zbl 0939.94563
[8] S. Dubuc-Camus, Etude des fonctions booléennes dégénérées et sans corrélation, Ph.D. Thesis, Université de Caen, France, 1998.; S. Dubuc-Camus, Etude des fonctions booléennes dégénérées et sans corrélation, Ph.D. Thesis, Université de Caen, France, 1998.
[9] B. Preneel, Analysis and design of cryptographic hash functions, Ph.D. Thesis, Katholieke Universiteit Leuven, Belgium, 1993.; B. Preneel, Analysis and design of cryptographic hash functions, Ph.D. Thesis, Katholieke Universiteit Leuven, Belgium, 1993.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.