Paper 2024/1007

On the vector subspaces of $\mathbb{F}_{2^n}$ over which the multiplicative inverse function sums to zero

Abstract

We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields), with respect to a recently introduced generalization of almost perfect nonlinearity (APN), called $k$th-order sum-freedom, that extends a classical characterization of APN functions, and has also some relationship with integral attacks. This generalization corresponds to the fact that a vectorial function $F:\mathbb F_2^n\mapsto \mathbb F_2^m$ sums to a nonzero value over every $k$-dimensional affine subspace of $\mathbb F_2^n$, for some $k\leq n$. The sum of the values of the inverse function $x\in \mathbb F_{2^n}\mapsto x^{2^n-2}\in \mathbb F_{2^n}$ over any affine subspace $A$ of $\mathbb{F}_{2^n}$ not containing 0 (i.e. being not a vector space) is easy to address: there exists a simple expression of such sum which shows that it never vanishes. We study in the present paper the case of a vector subspace (a linear subspace), which is much less simple to handle. We show that the sum depends on a coefficient in subspace polynomials. We derive several expressions of this coefficient. Then we study for which values of $k$ the multiplicative inverse function can sum to nonzero values over all $k$-dimensional vector subspaces. We show that, for every $k$ not co-prime with $n$, it sums to zero over at least one $k$-dimensional $\mathbb{F}_2$-subspace of $\mathbb{F}_{2^n}$. We study the behavior of the inverse function over direct sums of vector spaces and we deduce that the property of the inverse function to be $k$th-order sum-free happens for $k$ if and only if it happens for $n-k$. We derive several results on the sums of values of the inverse function over vector subspaces, addressing in particular the cases of dimension at most 3 (equivalently, of co-dimension at most 3). We leave other cases open and provide computer investigation results.