Explicit infinite families of bent functions outside the completed Maiorana–McFarland class

Abstract

Abstract During the last five decades, many different secondary constructions of bent functions were proposed in the literature. Nevertheless, apart from a few works, the question about the class inclusion of bent functions generated using these methods is rarely addressed. Especially, if such a “new” family belongs to the completed Maiorana–McFarland ( $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> ) class then there is no proper contribution to the theory of bent functions. In this article, we provide some fundamental results related to the inclusion in $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> and eventually we obtain many infinite families of bent functions that are provably outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> . The fact that a bent function f is in/outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> if and only if its dual is in/outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> is employed in the so-called 4-decomposition of a bent function on $${\mathbb {F}}_2^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> , which was originally considered by Canteaut and Charpin (IEEE Trans Inf Theory 49(8):2004–2019, 2003) in terms of the second-order derivatives and later reformulated in (Hodžić et al. in IEEE Trans Inf Theory 65(11):7554–7565, 2019) in terms of the duals of its restrictions to the cosets of an $$(n-2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -dimensional subspace V . For each of the three possible cases of this 4-decomposition of a bent function (all four restrictions being bent, semi-bent, or 5-valued spectra functions), we provide generic methods for designing bent functions provably outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> . For instance, for the elementary case of defining a bent function $$h(\textbf{x},y_1,y_2)=f(\textbf{x}) \oplus y_1y_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>h</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>y</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>y</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⊕</mml:mo> <mml:msub> <mml:mi>y</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:msub> <mml:mi>y</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:math> on $${\mathbb {F}}_2^{n+2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msubsup> </mml:math> using a bent function f on $${\mathbb {F}}_2^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> , we show that h is outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> if and only if f is outside $${{{\mathcal {M}}}{{\mathcal {M}}}}^\#$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>M</mml:mi> <mml:mi>M</mml:mi> </mml:mrow> <mml:mo>#</mml:mo> </mml:msup> </mml:math> . This approach is then generalized to the case when two bent functions are used. More precisely, the concatenation $$f_1||f_1||f_2||(1\oplus f_2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mrow> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mrow> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mrow> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow

Topics & Concepts