Low \(c\)-differential uniformity for functions modified on subfields (Q2096651): Difference between revisions

Let \(p\) be a fixed prime number and let \(GF(p^n)\) denote the finite field with \(p^n\) elements, where \(n>0\) is an integer. A \(p\)-ary function is a mapping \(f:G(p^n)\to GF(p)\), while an \((n,m)\)-function (also called a vectorial function) is a mapping \(f:G(p^n)\to GF(p^m)\), where \(m>0\) is an integer. The application of \((n,m)\)-functions to cryptography often begins with the introduction of bent, or perfectly non-linear, functions. These are functions \(f:G(p^n)\to GF(p^m)\) with the property that the derivative is balanced: that is, the cardinalities \(|(D_af)^{-1}(y)|\) do not depend on \(y \in GF(p^m)\), where \[ D_af(x) = f(x + a) - f(x),\quad a\in GF(p^n)\ \mathrm{fixed}, \] denotes the derivative with respect to \(a\). (Incidentally, from this it follows that \(|(D_af)^{-1}(y)|=p^{n-m}\) for each \(y\in GF(p^m)\).) The paper under review replaces this derivative by the (multiplicative) \(c\)-derivative of \(f\) with respect to \(a\): \[ _cD_df(x) = f(x+a)-cf(x), \] for \(x \in GF(p^n)\) and \(c\in GF(p^m)\). The cardinality of the pre-image of the \(c\)-derivative will be denoted \[ _c\Delta_f(a,y) = |\{x\in GF(p^n)\ |\ f(x+a)-cf(x)=y\}|,\quad y\in GF(p^m). \] The maximum of these values, denoted \(\delta_{f,c}\), is called the \(c\)-differential uniformity of \(f\): \[ \delta_{f,c} = max\{ \, _c\Delta_f(a,y) \ |\ a\in GF(p^n), y\in GF(p^m),\ \text{ and } a\not= 0\ \text{ if }\ c=1\}. \] In this case, we say that \(f\) has \(c\)-uniformity \(\delta_{f,c}\). Now assume \(m=n\). If \(\delta_{f,c} = 1\) then \(f\) is called a perfect \(c\)-nonlinear function. These generalize bent functions (which form the case \(c=1\)). If \(\delta_{f,c} = 2\) then \(f\) is called an almost perfect \(c\)-nonlinear function. We now roughly and very briefly describe the main results of this paper. Section 2 defines a polynomial \(F=F_{f,g}\)on \(GF(2^n)\) from polynomials \(f,g\) whose coefficients belong to a subfield \(GF(2^s)\) (where \(s\) divides \(n\)): \[ F(x) = f(x)+(f(x)+g(x))(x^{2^s}+x)^{2^n-1}. \] Under certain technical hypotheses, Theorems 2.3 proves an explicit upper bound on the differential uniformity of \(F\) in the case \(p=2\). (This is further generalized in Theorems 2.5, 2.7, 2.8, 2.10, for \(p\geq 2\).) Under further technical hypotheses, Theorem 2.4 proves an explicit lower bound on the nonlinearity of \(F\), again for \(p=2\). These types of results are then applied to an finding upper bound on the differential uniformity of generalized Gold functions for \(p=2\). Section 3 uses concatination to construct a perfect \(c\)-nonlinear function over \(GF(q^n)\) from \(n\) perfect \(c\)-nonlinear function over \(GF(q)\). Section 4 has some concluding remarks and suggests directions for further investigations. The reader is referred to the paper itself for more precise details.