On construction of correlation-immune functions via minimal functions

The use of correlation-immune functions in a cryptographic primitive may provide resistance against some key compromising methods. Designing of modern cryptographic primitives poses the challenge of constructing correlationimmune functions of a relatively large number of arguments. This paper proposes a method combining two basic approaches of solving this problem: iterative and a direct-search ones. Proposed method is based on minimal correlation-immune functions. The functions constructed by this method have no obvious structural characteristics that may be used to distinguish them from a random function.
The first stage of the proposed method is an easily implemented iteration procedure, which allows to construct many special functions that depend on the desired number of variables. At the second stage the constructed functions are used by some search procedure to find functions with given cryptographic properties. For the second stage the paper presents the reduction of the problem of searching for a resilient function with a preassigned order to the problem of solving a system of linear pseudo-Boolean equations. We also study how to apply a modification of the proposed method in order to improve the cryptographic parameters of the known “good” functions by means of small changes. Examples of successful applications of the methods described are given.