Discrete Functions

Cryptographic properties of suitable functions

I. A. Pankratova, A. A. Medvedev


Abstract: We consider «suitable» Boolean functions $f$, that is, functions such that the function $F:\mathbb{F}_2^n\to\mathbb{F}_2^n$ of the form $F(x)=\big(f(x),f(\pi(x)),f(\pi^2(x)),\ldots, f(\pi^{n-1}(x))\big)$, where $\pi$ is a cyclic shift of the vector of variables to the left by 1, is invertible. Let $\mathcal{SF}(n)$ be the set of all suitable functions in $n$ variables. The properties of functions in $\mathcal{SF}(n)$ have been investigated (theoretically and experimentally). It is proven that the ANF of a suitable function contains an odd number of positive degree monomials, among which there is at least one monomial of degree 1. Some affine functions in $\mathcal{SF}(n)$ have been described; the upper bounds of some cryptographic characteristics have been obtained, in particular, $\max_{f\in\mathcal{SF}(n)}\text{cor}(f)=n-2$ and $\max_{f\in\mathcal{SF}(n)}\text{PC}(f)\leq n-2$, if $n$ is even, and $\max_{f\in\mathcal{SF}(n)}\text{cor}(f)=n-3$ and $\max_{f\in\mathcal{SF}(n)}\text{PC}(f)\leq n-1$, if $n$ is odd.

Keywords: vector Boolean functions, cyclic shift, cryptographic properties of Boolean functions.

UDC: 519.7

DOI: 10.17223/2226308X/18/21