sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical Universitysapi-92Research ArticleЗащита информацииInformation securityМЕТОДЫ СИНТЕЗА АЛГЕБРАИЧЕСКОЙ НОРМАЛЬНОЙ ФОРМЫ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИSYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONSСоколовА. В.SokolovA. V.

Doctor of Engineering, Senior Lecturer

CA_PI@bntu.byЖдановО. Н.ZhdanovO. N.

Associate Professor, PhD in Engineering

CA_PI@bntu.byАйвазянО. А.AyvazianO. A.

Graduate student

CA_PI@bntu.byОдесский национальный политехнический университетУкраинаOdessa National Polytechnic UniversityUkraineСибирский государственный аэрокосмический университет им. М. Ф. РешетнёваРоссияSiberian State Aerospace UniversityRussian Federation201628032016016976Copyright © Соколов А.В., Жданов О.Н., Айвазян О.А., 20162016Соколов А.В., Жданов О.Н., Айвазян О.А.Sokolov A.V., Zhdanov O.N., Ayvazian O.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/92

Стремительное развитие методов помехоустойчивого кодирования, криптографии, теории синтеза сигналов, основанных на принципах многозначной логики, диктуют необходимость более полного изучения форм представления функций многозначной логики. В частности, для булевых функций широкое распространение получила алгебраическая нормальная форма, известная также как полином Жегалкина, которая хорошо описывает многие криптографические свойства булевых функций. В настоящей статье формализуется понятие алгебраической нормальной формы функции многозначной логики. Предложены методы синтеза алгебраической нормальной формы 3-функций и 5-функций, которые работают по аналогии с преобразованием Рида-Маллера для булевых функций: на основе рекуррентно синтезируемых матриц преобразования. Выдвинута гипотеза, определяющая правила синтеза матриц как для перехода от таблицы истинности к коэффициентам алгебраической нормальной формы, так и обратного преобразования для любого, наперед заданного количества переменных 3-функции либо 5-функции. В статье также введено определение алгебраической степени нелинейности функций многозначной логики и S-блока подстановки, основанных на принципах многозначной логики. Так, разработанный метод синтеза алгебраической нормальной формы 3-функций применен к известной конструкции рекуррентного синтеза S-блоков длины N = 3k, в результате чего вычислены их алгебраические степени нелинейности. Полученные результаты могут стать основой как для дальнейших теоретических исследований, так и для практического применения: разработки новых криптографических примитивов, корректирующих кодов, алгоритмов сжатия информации, сигнальных конструкций, алгоритмов блочного и поточного шифрования, основанных на перспективных принципах многозначной логики. Кроме того, методы синтеза алгебраической нормальной формы функций многозначной логики являются основой для их программной и аппаратной имплементации.

The rapid development of methods of error-correcting coding, cryptography, and signal synthesis theory based on the principles of many-valued logic determines the need for a more detailed study of the forms of representation of functions of many-valued logic. In particular the algebraic normal form of Boolean functions, also known as Zhegalkin polynomial, that well describe many of the cryptographic properties of Boolean functions is widely used. In this article, we formalized the notion of algebraic normal form for many-valued logic functions. We developed a fast method of synthesis of algebraic normal form of 3-functions and 5-functions that work similarly to the Reed-Muller transform for Boolean functions: on the basis of recurrently synthesized transform matrices. We propose the hypothesis, which determines the rules of the synthesis of these matrices for the transformation from the truth table to the coefficients of the algebraic normal form and the inverse transform for any given number of variables of 3-functions or 5-functions. The article also introduces the definition of algebraic degree of nonlinearity of the functions of many-valued logic and the S-box, based on the principles of many-valued logic. Thus, the methods of synthesis of algebraic normal form of 3-functions applied to the known construction of recurrent synthesis of S-boxes of length N = 3k, whereby their algebraic degrees of nonlinearity are computed. The results could be the basis for further theoretical research and practical applications such as: the development of new cryptographic primitives, error-correcting codes, algorithms of data compression, signal structures, and algorithms of block and stream encryption, all based on the perspective principles of many-valued logic. In addition, the fast method of synthesis of algebraic normal form of many-valued logic functions is the basis for their software and hardware implementation.

алгебраическая нормальная формамногозначная логикапреобразование Рида-Маллераalgebraic normal formmany-valued logicReed-Muller transformReferencesМазурков, М. И. О влиянии вида ортогонального преобразования на пик-фактор спектра в системах с CDMA / М. И. Мазурков, А. В. Соколов, Н. А. Барабанов. – Інформатика та математичні методи в моделюванні, 2015. – Т .5, № 1. – С. 28–37.Mazurkov, M. I. On the effect of the type of orthogonal transform on PAPR of signal spectrum in CDMA systems /M. I. Mazurkov, A. V. Sokolov, N. A. Barabanov. – Іnformatika ta matematichnі metodi v modeljuvannі, 2015. – Vol. 5, № 1. – P. 28–37.Falkowski, B. J. Application of Sign Hadamard¬Haar Transform in Ternary Communication System / B. J. Falkowski, S. Yan. – International Journal of Electronics, 1995. – Vol. 79(5). – P. 551–559.Falkowski, B. J. Application of Sign Hadamard¬Haar Transform in Ternary Communication System / B. J. Falkowski, S. Yan. – International Journal of Electronics, 1995. – Vol. 79(5). – P. 551–559.Кузнецов, В. С. Троичные каскадные коды с модуляцией КАМ-9 и их возможности / В. С. Кузнецов. – «ИнфоЭлектросвязь», 2009. – С. 30–33.Kuznecov, V. S. Trinity concatenated codes with QAM¬9 and their capabilities / V. S. Kuznecov. – «Info¬Jelektrosvjaz», 2009. – P. 30–33.Мазурков, М. И. Системы широкополосной радиосвязи / М. И. Мазурков – Одесса: Наука и Техника, 2010, с. 340. – ISBN 978-966-8335-95-2.Mazurkov, M. I. Broadband radio systems / M. I. Mazurkov. – Odessa: Nauka i Tehnika, 2010, p. 340. – ISBN 978¬ 966¬8335¬95¬2.Петелин, Ю. В. Перспективы использования сигнально-кодовых конструкций типа троичных М-последовательностей в спутниковых каналах связи / Ю. В. Петелин, М. А. Ковалев, А. А. Макаров // Информацион¬ но-управляющие системы. – 2006. – №. 5. – С. 32–35.Petelin, Ju. V. Perspectives of using of signal¬code structures such as ternary M¬sequences in the satellite communication channels / Ju. V. Petelin, M. A. Kovalev, A. A. Makarov // Informacionno¬upravljajushhie sistemy. – 2006. – №. 5. – P. 32–35.Жданов, О. Н. Алгоритм построения оптимальных по критерию нулевой корреляции недвоичных блоков за¬ мен / О. Н. Жданов, А. В. Соколов. – Проблемы физики, математики и техники, 2015. – № 3(24). – С. 94–97.Zhdanov, O. N. Algorithm of construction of optimal according to criterion of zero correlation nonbinary S¬boxes / N. Zhdanov, A. V. Sokolov. – Problems of physics, mathematics and technics, 2015. – № 3(24). – P. 94–97.Логачев, О. А. Булевы функции в теории кодирования и криптологии / О. А. Логачев, А. А. Сальников, В. В. Ящен¬ ко. – М: Издательство МЦНМО. – 2004. – 472 с.Logachev, O. A. Boolean functions in coding theory and cryptology / O. A. Logachev, A. A. Sal’nikov, V. V. Jashhen¬ ko. – M: Izdatel’stvo MCNMO. – 2004. – 472 p.Qingshu, Meng A novel algorithm enumerating bent functions / Qingshu Meng, Min Yang, Huanguo Zhang, Jingsong Cui // Discrete Mathematics, 2008. – Volume 308, Issue 23, 2008. – P. 5576–5584.Qingshu, Meng A novel algorithm enumerating bent functions / Qingshu Meng, Min Yang, Huanguo Zhang, Jingsong Cui // Discrete Mathematics, 2008. – Volume 308, Issue 23. – P. 5576–5584.Мак-Вильямс, Ф. Дж. Теория кодов исправляющих ошибки / Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн. – М.: Связь, 1979. – с. 745.MacWilliams, F. J. Theory of Error-Correcting Codes / F. J. MacWilliams, N. J. A. Sloane. – M.: Svjaz’, 1979. – p. 745.Мазурков, М. И. Генератор ключевых последовательностей на основе дуальных пар бент-функций / М. И. Ма¬ зурков, Н. А. Барабанов, А. В. Соколов. – Труды Одесского политехнического университета, 2013. – Вып. 3 (42). – С. 150–156.Mazurkov, M. I. The key sequences generator based on bent functions dual couples / M. I. Mazurkov, N. A. Barabanov, A. V. Sokolov. – Works of the Odessa polytechnic university. – Vol. 3 (42). – P. 150–156.Жегалкин, И. И. Арифметизация символической логики / И. И. Жегалкин. – Матем. сб., 1929. – 305–338.Zhegalkin, I. I. Arithmetization of symbolic logic / I. I. Zhegalkin. – Matem. sb., 1929. – P. 305–338.Ростовцев, А. Г. Криптография и защита информации / А. Г. Ростовцев. – СПб.: Мир и Семья. – 2002.Rostovcev, A. G. Cryptography and Data Protection / A. G. Rostovcev. – SPb.: Mir i Sem’ja. – 2002.Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, – М.: Вильямс, 2006. – с. 1328.Kormen, T. Construction and analysis of algorithms / T. Kormen, Ch. Lejzerson, R. Rivest, K. Shtajn, – M.: Vil’jams, 2006. – p. 1328.Соколов, А. В. Новые методы синтеза нелинейных преобразований современных шифров / А. В. Соколов. – Lap Lambert Academic Publishing, Germany, 2015. – 100 с.Sokolov, A. V. New methods of the synthesis of non-linear transforms of modern ciphers / A. V. Sokolov. – Lap Lambert Academic Publishing, Germany, 2015. – p. 100.

The authors declare that there are no conflicts of interest present.