Способ восстановления булевой функции нескольких переменных по ее производной

Введение. Булевы функции нескольких переменных играют важную роль в криптографии и теории кодирования. Композиции этих функций используются в ряде симметрических криптосистем; с их помощью могут быть определены некоторые помехоустойчивые коды, например, коды Рида-Маллера, коды Кердока, а также построены новые декодеры, работающие за пределом половины кодового расстояния. В работе рассматривается задача восстановления булевой функции по ее производной, названная задачей интегрирования булевых функций. При восстановлении булевой функции вектор, в направлении которого вычислена производная, полагается неизвестным. Материалы и методы. Результаты получены на базе следующей методологии: теория булевых функций, теория конечных полей и полиномиальных колец, линейная алгебра. Пространство булевых функций рассмотрено как некоторое изоморфное факторкольцо, что позволило свести поставленную задачу к поиску решения полиномиальной системы уравнений специального вида. Построенный изоморфизм позволяет проверить, разрешима ли задача об интегрировании, а также предложить новый способ ее решения. Результаты исследования . Формально построен алгоритм поиска прообраза методом полного перебора, вычислена его алгоритмическая сложность. Доказана теорема о необходимых и достаточных условиях существования прообраза для произвольной булевой функции, которая рассматривается как значение производной по направлению. Приводимые доказательства носят конструктивный характер. На основе доказанных фактов построены алгоритмы проверки существования прообраза для заданной булевой функции и построения прообраза. В предложенном варианте алгоритм строит только один из возможных прообразов, при условии его существования. Предложенный алгоритм построения прообраза обладает с точки зрения алгоритмической сложности значительной эффективностью по сравнению с методом полного перебора. Приводятся временные оценки сложности основных формальных алгоритмов, разработанных для решения поставленных задач, описано сравнение сложности их работы со сложностью алгоритма интегрирования булевых функций методом полного перебора. Обсуждение и заключения. Выполненная работа может быть полезна для специальных разделов криптографии и теории кодирования, в которых используются булевы функции нескольких переменных.

булева функция, производная булевой функции по направлению, алгоритм проверки возможности восстановления булевой функции, оценка сложности, пространство булевых функций, кольцо многочленов, конечные поля, кольцевой изоморфизм, теория кодирования, поиск прообраза, 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. Логачев, О. А. Булевы функции в теории кодирования и криптологии / О. А. Логачев, А. А. Сальников, В. В. Ященко. - Москва: МЦНМО, 2004. - 470 с.

2. Мак-Вильямс, Ф. Дж. Теория кодов, исправляющих ошибки. / Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн. - Москва : Связь, 1979. - 744 с.

3. Сидельников, В. М. Теория кодирования / В. М. Сидельников. - Москва : ФИЗМАТЛИТ. - 2008. - 324 с.

4. Деундяк В. М. Модель троичного канала передачи данных с использованием декодера мягких решений кодов Рида-Маллера второго порядка / В. М. Деундяк, Н. С. Могилевская // Известия вузов. Сев.-Кав. регион. Техн. науки. - 2015.- №1(182). - С.3-10.

5. Могилевская, Н. С. Экспериментальное исследование декодеров кодов Рида-Маллера второго порядка / Н. С. Могилевская, В. Р. Скоробогат, В. С. Чудаков // Вестник Донского гос. тех. ун-та. - 2008. - Т.8, № 3. - С.231-237.

6. Могилевская, Н. С. Корректирующая способность декодера мягких решений троичных кодов Рида-Маллера второго порядка при большом числе ошибок / Н. С. Могилевская // Вестник Донского гос. тех. ун-та. - 2015. - № 1. - С.121-130.

7. Бохманн, Д. Двоичные динамические системы / Д. Бохманн, Х. Постхоф. - Москва : Энергоатомиздат, 1986. - 400 с.

8. Деундяк, В. М. Интегрируемость систем полиномов нескольких переменных первой и второй степени над простыми полями Галуа / В. М Деундяк, А. В. Кнутова // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. - 2016. - №2. - С.41-46.

9. Алгоритм восстановления булевой функции по ее производной по направлению (электронный ресурс) / А. Мазуренко, Н. С. Могилевская // Системный анализ, управление и обработка информации: сб. трудов VI международного семинара. - Ростов-на-Дону, 2015. - Т. 1. - С.256-262. - Режим доступа: http://ntb.donstu.ru/content/2015421/ (дата обращения: 13.11.2016).

10. Глухов, М. М. Алгебра. Т. 1. / М. М. Глухов, В. П. Елизаров, А. А. Нечаев. - Москва : Гелиос АРВ, 2003. - 336 с.

11. 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).

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

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

14. 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).

15. 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).

16. 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 second-order codes with a large number of errors.] Vestnik of DSTU, 2015, no. 1, pp. 121-130 (in Russian).

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

18. 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).

19. Mazurenko, A., 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).

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