Trims and extensions of quadratic APN functions (Q2119950)

For two integers \(m,n \in \mathbb{N}\) with \(m<n\) and two vectorial functions \(F:\mathbb{F}_2^n \rightarrow \mathbb{F}_2^n\) and \(G:\mathbb{F}_2^m \rightarrow \mathbb{F}_2^m\), \(F\) is an extension of \(G\) and \(G\) is a restriction of \(F\) if there is an injective affine mapping \(\phi: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) and an affine surjection \(\varphi:\mathbb{F}_2^n \rightarrow \mathbb{F}_2^m\) such that \(G=\varphi \circ F \circ \phi\). In this work, only the case \(m=n-1\) is considered. For the restriction, the authors define an operation called trimming as follows. Let \(\alpha, \beta \) be nonzero elements of \(\mathbb{F}_2^n\) and let \(H\) be one of the affine hyperplanes \(H=\alpha^{\bot}\)or \(H=\mathbb{F}_2^n\setminus \alpha^{\bot}\) of dimension \(n-1\). Choose \(\varepsilon=0\) if \(H=\alpha^{\bot}\) and let \(\varepsilon\) be an arbitrary element of \(H\) if \(H=\mathbb{F}_2^n\setminus \alpha^{\bot}\) and \(\gamma \in \mathbb{F}_2^n\) such that \(\left< \beta, \gamma\right> = 1\). Then trimming along \((H, \beta)\) on the set of vectorial Boolean functions \(F:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^n\) is defined as \[ T_{H,\beta}^{\varepsilon,\gamma}(x)=F(x+\epsilon)+\beta \left<\gamma, F(x+\varepsilon)\right>. \] Using this operation, a given function \(F\) is restricted to an affine hyperplane of dimension \(n-1\) and then the output is projected to an \((n-1)\) dimensional space. For fixed \((H,\beta)\) and varying \(\epsilon, \gamma\), the output functions in dimension \(n-1\) obtained through this operation are EA-equivalent (Proposition 1). Then it is shown that any restriction \(G\) in dimension \(n-1\) of \(F\) is EA-equivalent to a trim of \(F\) (Proposition 2). Moreover, the set of possible trims of EA-equivalent functions are the same (Proposition 3). Based on these results, the authors define the trim spectrum of a function, as the multiset of all trims of the given function. Note that for a quadratic function it is enough to consider linear subspaces to find out its trim spectrum. In the paper, the authors concentrate on quadratic APN functions in small dimensions. For each quadratic APN function in dimension \(3 \leq n \leq 7\), they first checked whether the trim spectrum contains an APN and then constructed the resulting trimming graph. Also, for each known quadratic APN function in dimension \(8\) (up to EA-equivalence) the authors checked whether it contains an APN in its trim spectrum. The results are summarized in Section 3.1 and also the related trimming graphs are given. Let \(G:\mathbb{F}_2^n \rightarrow \mathbb{F}_2^n\) be a quadratic APN function and \(r:\mathbb{F}_2^n \rightarrow \mathbb{F}_2\) be a Boolean function of algebraic degree at most \(2\). \(G\) is \(r\)-extendable if there exist two linear functions \(L:\mathbb{F}_2^n \rightarrow \mathbb{F}_2^n\) and \(\ell:\mathbb{F}_2^n \rightarrow \mathbb{F}_2\) such that \[ T(x,y)=(G(x)+L(x)y, r(x)+y\ell(x)) \] is APN. Using this extension, new quadratic APN functions in dimension \(8\) are obtained from quadratic APN functions in dimension \(7\), which were recently completely classified by Kalgin and Idrisova. Also, all the quadratic APN with maximal linearity \(2^7\) in dimension \(8\) are classified using the results of Kalgin and Idrisova, Theorem 1 and Proposition 6. Note that APN with maximal linearity exist only in even dimensions. In the last section the remaining open problems are listed.