Advanced Engineering Research (Mar 2017)
Method of restoring multivariable Boolean function from its derivative
Abstract
Introduction. Boolean functions of several variables are of paramount importance in the coding theory and cryptography. The compositions of these functions are used in a set of the symmetric cryptosystems; therewith, some error-control codes, such as Reed-Muller codes, Kerdock codes, can be defined; as well as some new decoders operating beyond half of the code distance can be constructed. The task of restoring a Boolean function from its derivative which is called a Boolean function integration problem is considered. A Boolean function being restored, the vector towards which the derivative is calculated is supposed unknown. Materials and Methods . The results are obtained on the basis of the following methodology: theory of Boolean functions, theory of finite fields and polynomial rings, linear algebra. The space of Boolean functions is considered a certain isomorphic factor-ring that allows reducing the task to finding solutions to a polynomial set of equations of a special form. The constructed isomorphism enables to check whether the integration problem is decidable, and also to offer a new method of its solution. Research Results . The algorithm of searching preimage by the full enumeration method is formally constructed; and its algorithmic complexity is calculated. The theorem of necessary and sufficient conditions for the existence of an arbitrary Boolean function preimage regarded as the directional derivative value is proved. The provided proofs are constructive. On the basis of the established facts, the algorithms of checking the preimage existence for the specified Boolean function and of building the preimage are developed. In the proposed version, the algorithm forms only one of the possible preimages under the condition of its existence. The proposed algorithm of the preimage generation is significantly efficient from the standpoint of the algorithmic complexity compared to the full enumeration method. Time estimates of the complexity of the basic formal algorithms developed for solving the formulated problems are given. The comparison of their operation complexity to the algorithm of Boolean functions integration complexity by the complete enumeration method is described. Discussion and Conclusions. The research performed can be useful for special sections of the coding theory and cryptography where Boolean functions of several variables are used.
Keywords
