Discrete Functions

Constructing vector Boolean functions with non-degenerate coordinate functions

I. A. Pankratova, E. A. Ruban, S. V. Chikalova

Tomsk State University

Abstract: An algorithm for constructing a bijection on $\mathbb{Z}_2^n$ with coordinate functions depending essentially on all variables is proposed. The algorithm consists of three steps: generation of a random bijection $F:\mathbb{Z}_2^n\to\mathbb{Z}_2^n$, analysis of the degeneracy of its coordinates, and one transposition of the values of $F(x)$ and $F(y)$ such that they differ only in the positions corresponding to the degenerate coordinate functions.

Keywords: vector Boolean function, bijection, essential dependence of a function on a variable.

UDC: 519.7

DOI: 10.17223/2226308X/15/8