Discrete Functions

On linear characteristics of some functions over Galois Rings

O. V. Kamlovskii, R. V. Penzyakov


Abstract: We define linear characteristic $\delta(f)$ and incomplete linear characteristic $\delta(f)^*$ of functions $f:R^n\to R$ over Galois ring $R=\text{GR}(q^l,p^l)$ and consider their properties. These characteristics show how “close” the functions are to the class of affine functions over the rings under consideration. We prove the criterion to be a bent function over Galois rings in terms of linear characteristics, which states that the necessary and sufficient condition is $\delta(f)=q^{-{nl}/{2}}$. We describe the function $f$ from the Eliseev — Maiorana — McFarland class: $f(\vec x,\vec y)=\langle \pi(\vec x),\vec y\rangle+h(\vec x)$, where $n=2k$, $\pi:R^k\to R^{k}$, $h:R^k\to R$, $\vec x,\vec y\in R^k$. We prove that in the case $|\pi^{-1}(\vec c)|\le t$ for all $\vec c\in R^k$ the inequalities $\delta(f)\le tq^{-{n}/{2}}$ and $\delta(f)^*\le tq^{-{nl}/{2}}$ are true. We also estimate linear characteristics of functions from the Dobbertin class: $f(\vec{x},\vec{y})=\langle \pi(\vec x),\vec y \rangle + h(\vec{x})$ if $\vec{x}\ne\vec{0}$ and $f(\vec{x},\vec{y})=g(\vec{y})$ if $\vec{x}=\vec{0}$, where $g:R^k\to R$ is balanced function, $\pi$ is bijection on $R^k$ and $\pi(\vec 0)=\vec 0$. We prove that in this case $\delta(f)\le q^{-{nl}/{2}}+q^{-{n}/{2}}$, $\delta(f)^*\le 2q^{-{nl}/{2}}$.

Keywords: linear characteristics of functions, Galois rings, additive character sums, bent functions.

UDC: 512.552

DOI: 10.17223/2226308X/18/13