Том 27, номер 1, 2020 г., Стр. 88–109

УДК 519.16
Леонтьев В. К., Гордеев Э. Н.
Об аннигиляторах булевых полиномов

Аннотация:
Булевы функции вообще и булевы полиномы (полиномы Жегалкина, алгебраические нормальные формы (АНФ)), в частности, — предмет теоретических и прикладных исследований в различных областях информатики. В работе рассматриваются линейные преобразования пространства булевых полиномов от n переменных, одним из следствий которых является получение результатов, касающихся проблемы нахождения минимальной степени аннигилятора для заданного булева полинома. Эта задача является актуальной в различных аналитических и алгоритмических аспектах криптографии. Булевы полиномы и их комбинаторные свойства изучаются в дискретном анализе. Теоретические основы информационной безопасности включают изучение свойств булевых полиномов в связи с вопросами криптографии. В работе доказана теорема о минимальной степени аннигилятора. Описан класс булевых полиномов, для которых степень аннигилятора не превосходит единицы. Приведён ряд комбинаторных характеристик, связанных со свойствами пространства булевых полиномов. Даны оценки минимальной степени аннигилятора. Рассмотрен случай симметрических полиномов.
Библиогр. 26.

Ключевые слова: булев полином, симметрический полином, аннигилятор, линейное преобразование, криптосистема

DOI: 10.33048/daio.2020.27.646

Леонтьев Владимир Константинович ^1,2
Гордеев Эдуард Николаевич ²
1. Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН,
ул. Вавилова, 42, 119991 Москва, Россия
2. Московский государственный технический университет им. Н. Э. Баумана,
2-я Бауманская ул., 5, 105005 Москва, Россия
е-mail: vkleontiev@yandex.ru, werhorn@yandex.ru

Статья поступила 24 января 2019 г.
После доработки — 10 сентября 2019 г.
Принята к публикации 25 сентября 2019 г.

Литература

[1] Панкратова И. А. Булевы функции в криптографии: учебное пособие. Томск: Томск. ун-т, 2014. 88 с.

[2] Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback // Advances in Cryptology – EUROCRYPT 2003 (Proc. Int. Conf. Theory Appl. Cryptogr. Tech., Warsaw, Poland, May 4–8, 2003). Heidelberg: Springer, 2003. P. 345–359. (Lect. Notes Comput. Sci.; Vol. 2656).

[3] Didier F. A new upper bound of the block error probability after decoding over the erasure channel // IEEE Trans. Inform. Theory. 2006. Vol. 52, No. 10. P. 4496–4503.

[4] Feng K., Liao Q., Yang J. Maximal values of generalized algebraic immunity // Des. Codes Cryptogr. 2009. Vol. 50. P. 243–252.

[5] Carlet C., Merabet B. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions // Adv. Math. Commun. 2013. Vol. 7, No. 2. P. 197–217.

[6] Лобанов М. С. Точные соотношения между нелинейностью и алгебраической иммунностью // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 6. C. 34–47.

[7] Лобанов М. С. Об одном методе получения нижних оценок на нелинейность булевой функции // Мат. заметки. 2013. Т. 93, № 5. C. 741–745.

[8] Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискрет. математика 2006. Т. 18, № 3. C. 152–159.

[9] Леонтьев В. К. Булевы полиномы и линейные преобразования // Докл. РАН. 2009. Т. 425, № 3. С. 320–322.

[10] Тужилин М. Э. Алгебраический иммунитет булевых функций // Прикл. дискрет. математика. 2008. № 2. С. 18–22.

[11] Rizomiliotis P. Improving the high order nonlinearity of Boolean functions with prescribed algebraic immunity // Discrete Appl. Math. 2010. Vol. 158, No. 18. P. 2049–2055.

[12] Mesnager S. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity // IEEE Trans. Inf. Theory. 2008. Vol. 54, No. 8. P. 3656–3662.

[13] Mesnager S., Gohen G. Fast algebraic immunity of Boolean functions // Adv. Math. Commun. 2017. Vol. 11, No. 2. P. 373–377.

[14] Wang Q., Johansson T. On equivalence classes of Boolean functions // Information Security and Cryptology (Rev. Sel. Pap. 13th Int. Conf., Seoul, Korea, Dec. 1–3, 2010). Heidelberg: Springer, 2011. P. 311–324. (Lect. Notes Comput. Sci.; Vol. 6829).

[15] Peng J., Kan H. Constructing rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables // IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2012. Vol. E95-A, No. 6. P. 1056–1064.

[16] Sun L., Fu F.-W. Constructions of balanced odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity // Theor. Comput. Sci. 2018. Vol. 738. P. 13–24.

[17] Sun L., Fu F.-W. Constructions of even-variable RSBFs with optimal algebraic immunity and high nonlinearity // J. Appl. Math. Comput. 2018. Vol. 56, No. 1–2. P. 593–610.

[18] Shaojing F. U., Jiao D. U., Longjiang Q. U., Chao L. I. Construction of odd-variable rotation symmetric Boolean functions with maximum algebraic immunity // IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2016. Vol. E99-A, No. 4. P. 853–855.

[19] Wang Q., Tan C. H., Stanica P. Concatenations of the hidden weighted bit function and their cryptographic properties // Adv. Math. Commun. 2014. Vol. 8, No. 2. P. 153–165.

[20] Леонтьев В. К. Симметрические булевы полиномы // Журн. вычисл. математики и мат. физики. 2010. Т. 50, № 8. С. 1520–1531.

[21] Carlet C., Gao G., Liu W. A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions // J. Comb. Theory, A. 2014. Vol. 127. P. 161–175.

[22] Su S., Tang X. Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity // Des. Codes Cryptogr. 2014. Vol. 71. P. 1567–1580.

[23] Леонтьев В. К. Комбинаторика и информация. Ч. 1. Комбинаторный анализ. М.: МФТИ, 2015. 174 с.

[24] Леонтьев В. К., Морено О. О нулях булевых полиномов // Журн. вычисл. математики и мат. физики. 1998. Т. 38, № 9. С. 1608–1615.

[25] Леонтьев В. К., Гордеев Э. Н. О числе нулей булевых полиномов // Журн. вычисл. математики и мат. физики. 2018. Т. 68, № 7. С. 1235–1245.

[26] Гордеев Э. Н., Леонтьев В. К., Медведев Н. В. О свойствах булевых полиномов, актуальных для криптосистем // Вопросы кибербезопасности. 2017. № 3. С. 63–69.