Method of restoring multivariable Boolean function from its derivative

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.

булева функция, производная булевой функции по направлению, алгоритм проверки возможности восстановления булевой функции, оценка сложности, пространство булевых функций, кольцо многочленов, конечные поля, кольцевой изоморфизм, теория кодирования, поиск прообраза, Boolean function, directional derivative of Boolean function, algorithm of checking recoverability of Boolean function, complexity estimation, space of Boolean functions, polynomial ring, finite fields, ring isomorphism, coding theory, preimage searching

1. Logachev, О.А., Salnikov, A.A., Yashchenko, V.V. Bulevy funktsii v teorii kodirovaniya i kriptologii. [Boolean functions in coding theory and cryptology.] Moscow: MTsNMO, 2004, 470 p. (in Russian).

2. McWilliams, F.J., Sloane, N.J.A. Teoriya kodov, ispravlyayushchikh oshibki. [The theory of error-correcting codes.] Moscow: Svyaz', 1979, 744 p. (in Russian).

3. Sidelnikov, V.M. Teoriya kodirovaniya. [Coding Theory.] Moscow: FIZMATLIT, 2008, 324 p. (in Russian).

4. Deundyak, V.M., Mogilevskaya, N.S. Model' troichnogo kanala peredachi dannykh s ispol'zovaniem dekodera myagkikh resheniy kodov Rida-Mallera vtorogo poryadka. [The model of the ternary communication channel with using the decoder of soft decision for Reed – Muller codes of the second order.] University News. North-Caucasian region. Technical Sciences Series, 2015, no. 1(182), pp. 3–10 (in Russian).

5. Mogilevskaya, N.S., Skorobogat, V.R., Chudakov, V.S. Eksperimental'noe issledovanie dekoderov kodov Rida-Mallera vtorogo poryadka. [Experimental research of second order Reed-Muller codes.] Vestnik of DSTU, 2008, vol. 8, no. 3, pp. 231–237 (in Russian).

6. Mogilevskaya, N.S. Korrektiruyushchaya sposobnost' dekodera myagkikh resheniy troichnykh kodov Rida-Mallera vtorogo poryadka pri bol'shom chisle oshibok. [Correcting capacity of soft-decision decoder of ternary Reed – Muller secondorder codes with a large number of errors.] Vestnik of DSTU, 2015, no. 1, pp. 121–130 (in Russian).

7. Bohmann, D., Posthoff, Kh. Dvoichnye dinamicheskie sistemy. [Binary dynamic systems.] Moscow: Energoatomizdat, 1986, 400 p. (in Russian).

8. Deundyak, V.M., Knutova, A.V. Integriruemost' sistem polinomov neskol'kikh peremennykh pervoy i vtoroy stepeni nad prostymi polyami Galua. [Integrability of Systems of the First and Second Degree Polynomials of Several Variables over Simple Galois Fields.] Izvestiya vuzov. Severo-Kavkazskiy region. Natural Sciences. 2016, no. 2, pp. 41–46 (in Russian).

9. Mazurenko, A.V., Mogilevskaya, N.S. Algoritm vosstanovleniya bulevoy funktsii po ee proizvodnoy po napravleniyu. [Algorithm of Boolean function recovery from its directional derivative.] Sistemnyy analiz, upravlenie i obrabotka informatsii: sb. trudov VI mezhdunarodnogo seminara. [System analysis, information control and processing: Proc.VI Int. Seminar.] Rostov-on-Don, 2015, vol. 1, pp. 256–262. Available at: http://ntb.donstu.ru/content/2015421/ (accessed: 13.11.2016) (in Russian).

10. Glukhov, М.М., Yelizarov, V.P., Nechaev, A.A. Algebra. Т. 1. [Algebra. Vol.1.] Moscow: Gelios ARV, 2003, 336 p. (in Russian).