×

zbMATH — the first resource for mathematics

Construction of bent functions from near-bent functions. (English) Zbl 1184.94240
A function \(f\) from an \(n\)-dimensional vector space \(V_n\) over \(\mathbb{F}_2\) into \(\mathbb{F}_2\) is called bent (near-bent) if its Walsh transform \(\hat{f}(u) = \sum_{x\in V_n}(-1)^{f(x)+\langle u,x\rangle}\) where \(\langle\;,\;\rangle\) denotes any inner product on \(V_n\) takes values in \(\{\pm 2^{n/2}\}\) (\(\{0,\pm 2^{(n+1)/2}\}\)) only. The authors suggest the construction of bent functions \(g(x,y) = yh(x)+(y+1)f(x)\) from \(V_n\times V_1\) into \(\mathbb{F}_2\) from two near-bent functions \(f,h\) on \(V_n\). A necessary and sufficient condition for \(g\) being bent is that \(\{u \in V_n\;|\;\hat{f}(u) \neq 0\;\text{and}\;\hat{h}(u) \neq 0\} = \emptyset\).
The authors implement their construction using Gold near-bent functions and general quadratic near-bent functions obtaining bent functions of algebraic degree \(3\), and Kasami-Welch near-bent functions to obtain further not quadratic bent functions.
A Boolean function \(f\) of dimension \(n\) is called normal (weakly-normal) if there exists an affine subspace of dimension \(n/2\) on which \(f\) is constant (affine). The authors point out the significance of their construction presenting non-weakly-normal bent functions in dimension \(12\) and \(10\). Until then the smallest dimension where a non-weakly-normal bent function has been found is \(14\), [see A. Canteaut et al. Discrete Appl. Math. 154 (2), 202–218 (2006; Zbl 1091.94021)].

MSC:
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
42C10 Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.)
06E30 Boolean functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Braeken, An; Wolf, Christopher; Preneel, Bart, A randomised algorithm for checking the normality of cryptographic Boolean functions, (), 51-66 · Zbl 1088.68595
[2] Canteaut, A.; Carlet, C.; Charpin, P.; Fontaine, C., On cryptographic properties of the cosets of \(r(1, m)\), IEEE trans. inform. theory, 47, 4, 1494-1513, (2001) · Zbl 1021.94014
[3] Canteaut, Anne; Charpin, Pascale, Decomposing bent functions, IEEE trans. inform. theory, 49, 8, 2004-2019, (2003) · Zbl 1184.94230
[4] Canteaut, Anne; Daum, Magnus; Dobbertin, Hans; Leander, Gregor, Finding nonnormal bent functions, Discrete appl. math., 154, 2, 202-218, (2006) · Zbl 1091.94021
[5] C. Carlet, On cryptographic complexity of boolean functions, in: Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Proceedings of Fq6, 2002, pp. 53-69 · Zbl 1021.94524
[6] Carlet, Claude; Dobbertin, Hans; Leander, Gregor, Normal extensions of bent functions, IEEE trans. inform. theory, 50, 11, 2880-2885, (2004) · Zbl 1184.94232
[7] Dillon, J.; McGuire, G., Near-bent functions on a hyperplane, Finite fields appl., 14, 3, 715-720, (2008) · Zbl 1159.11051
[8] Hans Dobbertin, Construction of bent functions and balanced boolean functions with high nonlinearity, in: Preneel [13], pp. 61-74 · Zbl 0939.94563
[9] Xuejia Lai, Additive and linear structures of cryptographic functions, in: Preneel [13], pp. 75-85 · Zbl 0939.94508
[10] P. Langevin, G. Leander, and G. McGuire, Analysis of Kasami-Welch functions in odd dimension using Stickelberger’s theorem, submitted for publication, 2008 · Zbl 1245.11120
[11] MacWilliams, F.J.; Sloane, N.J., The theory of error-correcting codes, (1977), North-Holland Amsterdam · Zbl 0369.94008
[12] McGuire, Gary, Spectra of functions, subspaces of matrices, and going up versus going down, (), 51-66 · Zbl 1195.06010
[13] ()
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.