Ternary Binomial and Trinomial Bent Functions in the Completed Maiorana-McFarland Class ∗

Tor Helleseth, Alexander Kholosha, Niki Spithaki · 2025

Read Ternary Binomial and Trinomial Bent Functions in the Completed Maiorana-McFarland Class ∗ by Tor Helleseth, Alexander Kholosha, Niki Spithaki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20715.txt.

Introduction

Tor Helleseth, Alexander Kholosha, and Niki Spithaki construct new bent functions over a three-symbol alphabet in a 2025 paper. Bent functions are prized in coding and cryptography because they sit as far as possible from all simple linear functions, which resists attacks. The authors work inside a classic completed family of such functions and look for members built from just two or three power terms.

They find two classes of degree-four functions, one with two terms and one with three, and give exact rules for their coefficients. One two-term subclass matches a known family of special polynomials. Their proof rests on a new test that checks bentness through derivatives along a chosen half-sized subspace. The results add rare, fully described examples to a sparse catalogue.

Catalog record

CREATORTor Helleseth, Alexander Kholosha, Niki Spithaki
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20715

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ternary Binomial and Trinomial Bent Functions in the Completed Maiorana-McFarland Class ∗ Tor Helleseth, Alexander Kholosha, Niki Spithaki Abstract Two classes of ternary bent functions of degree four with two and three terms in the univariate representation that belong to the completed Maiorana-McFarland class are found. Binomials are mappings 𝔽 3 4 ​ k ↦ 𝔽 3 {\mathbb{F}}_{3^{4k}}\mapsto{\mathbb{F}}_{3} given by f ⁡ ( x ) = Tr 4 ​ k ⁡ ( a 1 ​ x 2 ​ ( 3 k + 1 ) + a 2 ​ x ( 3 k + 1 ) 2 ) f(x)={\operatorname{Tr}}_{4k}\big(a_{1}x^{2(3^{k}+1)}+a_{2}x^{(3^{k}+1)^{2}}\big) , where a 1 a_{1} is a nonsquare in 𝔽 3 4 ​ k {\mathbb{F}}_{3^{4k}} and a 2 a_{2} is defined explicitly by a 1 a_{1} . Particular subclasses of the binomial bent functions we found can be represented by exceptional polynomials over 𝔽 3 k {\mathbb{F}}_{3^{k}} . Bent trinomials are mappings 𝔽 3 2 ​ k ↦ 𝔽 3 {\mathbb{F}}_{3^{2k}}\mapsto{\mathbb{F}}_{3} given by f ⁡ ( x ) = Tr n ⁡ ( a 1 ​ x 2 ⋅ 3 k + 4 + a 2 ​ x 3 k + 5 + a 3 ​ x 2 ) f(x)={\operatorname{Tr}}_{n}\big(a_{1}x^{2\cdot 3^{k}+4}+a_{2}x^{3^{k}+5}+a_{3}x^{2}\big) with coefficients explicitly defined by the parity of k k . The proof is based on a new criterion that allows checking bentness by analyzing first- and second-order derivatives of f f in the direction of a chosen n / 2 n/2 -dimensional subspace. * * footnotetext: This work was supported by the Norwegian Research Council. 1 Introduction Boolean bent functions were first introduced by Rothaus in 1976 as an interesting combinatorial object with the important property of having the maximum Hamming distance to the set of all affine functions. Later the research in this area was stimulated by the significant relation to the following topics in computer science: coding theory, sequences and cryptography (design of stream ciphers and S -boxes for block ciphers). Kumar, Scholtz and Welch in [ 1 ] generalized the notion of Boolean bent functions to the case of functions over an arbitrary finite field. Complete classification of bent functions looks hopeless even in the binary case. In the case of generalized bent functions, things are naturally much more complicated. However, many explicit methods are known for constructing bent functions either from scratch or based on other, simpler bent functions. The finite field {\mathbb{F}}_{p^{k}} is a subfield of {\mathbb{F}}_{p^{n}} if and only if k divides n . The trace mapping from {\mathbb{F}}_{p^{n}} to the subfield {\mathbb{F}}_{p^{k}} is defined by {\operatorname{Tr}}_{k}^{n}(x)=\sum_{i=0}^{n/k-1}x^{p^{ik}} . In the case when k=1 , we use the notation {\operatorname{Tr}}_{n}(x) instead of {\operatorname{Tr}}_{1}^{n}(x) . Given a function f(x) mapping {\mathbb{F}}_{p^{n}} to {\mathbb{F}}_{p} , the direct and inverse Walsh transform operations on f are defined at a point by the following respective identities S_{f}(b)=\sum_{x\in{\mathbb{F}}_{p^{n}}}\omega^{f(x)-{\operatorname{Tr}}_{n}(bx)}\quad\mbox{and}\quad\omega^{f(x)}=\frac{1}{p^{n}}\sum_{b\in{\mathbb{F}}_{p^{n}}}S_{f}(b)\omega^{{\operatorname{Tr}}_{n}(bx)} where {\operatorname{Tr}}_{n}():{\mathbb{F}}_{p^{n}}\rightarrow{\mathbb{F}}_{p} denotes the absolute trace function, \omega=e^{\frac{2\pi i}{p}} is the complex primitive p^{\rm{th}} root of unity and elements of {\mathbb{F}}_{p} are considered as integers modulo p . According to [ 1 ] , f(x) is called a p -ary bent function if all its Walsh coefficients satisfy |S_{f}(b)|^{2}=p^{n} . A bent function f(x) is called regular (see [ 1 , Definition 3] and [ 2 , p. 576] ) if for every b\in{\mathbb{F}}_{p^{n}} the normalized Walsh coefficient p^{-n/2}S_{f}(b) is equal to a complex p^{\rm{th}} root of unity, i.e., p^{-n/2}S_{f}(b)=\omega^{f^{*}(b)} for some function f^{*} mapping {\mathbb{F}}_{p^{n}} into {\mathbb{F}}_{p} . A bent function f(x) is called weakly regular if there exists a complex u having unit magnitude such that up^{-n/2}S_{f}(b)=\omega^{f^{*}(b)} for all b\in{\mathbb{F}}_{p^{n}} . We call u^{-1}p^{n/2} the magnitude of S_{f}(b) . Recently, weakly regular bent functions were shown to be useful for constructing certain combinatorial objects such as partial difference sets, strongly regular graphs and association schemes (see [ 3 , 4 ] ). This justifies why the classes of (weakly) regular bent functions are of independent interest. For a comprehensive reference on monomial and quadratic p -ary bent functions we refer reader to [ 5 ] and to the general survey on p -ary bent functions [ 6 ] . Definition 1 Functions f,g:{\mathbb{F}}_{p}^{n}\mapsto{\mathbb{F}}_{p} are extended-affine equivalent (in brief, EA-equivalent) if there exists an affine permutation L of {\mathbb{F}}_{p}^{n} , an affine function l:{\mathbb{F}}_{p}^{n}\mapsto{\mathbb{F}}_{p} and a\in{\mathbb{F}}_{p}^{*} such that g(x)=a(f\circ L)(x)+l(x) . A class of functions is complete if it is a union of EA-equivalence classes. The completed class is the smallest possible complete class that contains the original one. It is interesting to find bent functions allowing few terms in their univariate representation. It looks like that the currently known list of bent monomials that give infinite classes is complete (see [ 6 ] ). The only known binomial class is for n=4k with f(x)={\operatorname{Tr}}_{n}\big(x^{p^{3k}+p^{2k}-p^{k}+1}+x^{2}\big) proven in [ 7 ] to be a weakly regular bent function for any odd p . In this paper, we find other ternary binomial and trinomial classes having the form f(x)={\operatorname{Tr}}_{n}\left(a_{1}x^{d_{1}}+a_{2}x^{d_{2}}+a_{3}x^{d_{3}}\right) with a_{i}\in{\mathbb{F}}_{3^{n}} and particular integer exponents d_{i} for i=\{1,2,3\} . These functions belong to the completed Maiorana-McFarland class and we develop some new tools to prove bentness in this case. The paper is organized as follows. In Section 2 , we prove new criteria for a function to be bent in the Maiorana-McFarland class. This result is interesting on its own since it provides a method for proving bentness that may work in the case when all the other approaches seem to fail. We use these criteria in the following sections. In Section 4 , we present ternary binomial bent function for n=4k given by f(x)={\operatorname{Tr}}_{n}\big(a_{1}x^{2(3^{k}+1)}+a_{2}x^{(3^{k}+1)^{2}}\big) , where a_{1} is a nonsquare in {\mathbb{F}}_{3^{n}} and a_{2} is defined explicitly by a_{1} . In Section 5 , we found bent trinomials f(x)={\operatorname{Tr}}_{n}\big(a_{1}x^{2\cdot 3^{k}+4}+a_{2}x^{3^{k}+5}+a_{3}x^{2}\big) with n=2k , k not divisible by four, and coefficients explicitly defined. Binomial bent functions considered in Section 3 are also Maiorana-McFarland but the proof is provided using a different technique that works in general and this is just a particular case that we ended up in the Maiorana-McFarland class. For small dimensions, we checked computationally that these functions are EA equivalent to the functions in a more general class from Section 4 but proving this in general remains open. The final Section 6 , we discuss the subclass of the earlier found binomial bent functions that can be represented by exceptional polynomials. 2 Proving Bentness in Maiorana-McFarland Case In this section, we discuss how to prove bentness of a function that will belong to the completed Maiorana-McFarland class. Normally, one would first check that a function is bent and then apply some criteria of being in the completed class of \mathcal{M} . Our result in Theorem 2.1 provides a new direct method of proving bentness specially customized to this case. Commonly, Maiorana-McFarland bent functions are represented in bivariate form. Construction 1 (Maiorana-McFarland [ 8 , 9 , 1 ] ) Take any permutation \pi of {\mathbb{F}}_{p}^{m} and any function g:{\mathbb{F}}_{p}^{m}\to{\mathbb{F}}_{p} . Then f:{\mathbb{F}}_{p}^{m}\times{\mathbb{F}}_{p}^{m}\to{\mathbb{F}}_{p} with f(x,y):=x\cdot\pi(y)+g(y) is a bent function. Moreover, the bijectiveness of \pi is necessary and sufficient for f being bent. Such bent functions are regular and the dual function is equal to f^{*}(x,y)=-y\cdot\pi^{-1}(x)+g(\pi^{-1}(x)) that is also a Maiorana-McFarland bent function. Here dot function is the inner product of {\mathbb{F}}_{p}^{m}

Read the complete text