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.
Введение. Булевы функции нескольких переменных играют важную роль в криптографии и теории кодирования. Композиции этих функций используются в ряде симметрических криптосистем; с их помощью могут быть определены некоторые помехоустойчивые коды, например, коды Рида-Маллера, коды Кердока, а также построены новые декодеры, работающие за пределом половины кодового расстояния. В работе рассматривается задача восстановления булевой функции по ее производной, названная задачей интегрирования булевых функций. При восстановлении булевой функции вектор, в направлении которого вычислена производная, полагается неизвестным. Материалы и методы. Результаты получены на базе следующей методологии: теория булевых функций, теория конечных полей и полиномиальных колец, линейная алгебра. Пространство булевых функций рассмотрено как некоторое изоморфное факторкольцо, что позволило свести поставленную задачу к поиску решения полиномиальной системы уравнений специального вида. Построенный изоморфизм позволяет проверить, разрешима ли задача об интегрировании, а также предложить новый способ ее решения. Результаты исследования . Формально построен алгоритм поиска прообраза методом полного перебора, вычислена его алгоритмическая сложность. Доказана теорема о необходимых и достаточных условиях существования прообраза для произвольной булевой функции, которая рассматривается как значение производной по направлению. Приводимые доказательства носят конструктивный характер. На основе доказанных фактов построены алгоритмы проверки существования прообраза для заданной булевой функции и построения прообраза. В предложенном варианте алгоритм строит только один из возможных прообразов, при условии его существования. Предложенный алгоритм построения прообраза обладает с точки зрения алгоритмической сложности значительной эффективностью по сравнению с методом полного перебора. Приводятся временные оценки сложности основных формальных алгоритмов, разработанных для решения поставленных задач, описано сравнение сложности их работы со сложностью алгоритма интегрирования булевых функций методом полного перебора. Обсуждение и заключения. Выполненная работа может быть полезна для специальных разделов криптографии и теории кодирования, в которых используются булевы функции нескольких переменных.
The authors declare that there are no conflicts of interest present.