О кубической части алгебраической нормальной формы произвольной бент-функции | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/15

О кубической части алгебраической нормальной формы произвольной бент-функции

Доказано, что кубическая часть бент-функции от n переменных не может быть произвольной при n = 6, 8.

About the cubic part of the algebraic normal form of arbitrary bent functions.pdf Булевы функции, максимально удалённые в метрике Хэмминга от множества всех аффинных функций, называются бент-функциями. Известно, что каждая булева функция может быть единственным образом представлена в её алгебраической нормальной форме (АНФ). Одна из проблем в области бент-функций: верно ли, что произвольная однородная булева функция степени k от n переменных (n чётное) является частью АНФ некоторой бент-функции от n переменных? Известно, что линейная часть в АНФ бент-функции может быть произвольной [1]. Доказано, что любая однородная квадратичная булева функция является квадратичной частью некоторой бент-функции [2]. В данной работе доказано, что при n = 6, 8 не каждую однородную кубическую булеву функцию можно достроить до бент-функции от n переменных. Для случая n = 8 лишь часть однородных кубических булевых функций может быть достроена до бент-функций от восьми переменных с помощью добавления однородных функций второй и/или четвёртой степеней. Далее будем использовать индексные обозначения АНФ функции; например, 12+34 означает булеву функцию ж1ж2 ф ж3ж4. Всего существует пять неэквивалентных кубических булевых форм от шести переменных [3], а именно: 123; 123 + 145; 123 + 456; 124+135 + 236; 123 + 124+135 + 236 + 456. Теорема 1. Для n = 6 функции 123; 123 + 145; 124 + 135 + 236 можно дополнить до бент-функций с помощью добавления однородных квадратичных булевых функций от шести переменных; функции 123 + 456; 123 + 124 + 135 + 236 + 456 нельзя дополнить до бент-функций от шести переменных. Существует 31 неэквивалентных кубических форм от восьми переменных [3]. В [4] приведена классификация форм четвёртой степени от восьми переменных, которые можно достроить до бент-функций [4], всего таких форм 536. В таблице приведены результаты для кубических форм от восьми переменных. Во втором столбце представлена однородная кубическая форма, в третьем указано, можно ли достроить её до бент-функции, в четвёртом столбце - число k, показывающее, с помощью скольких форм четвёртой степени можно достроить кубические формы в том случае, если они достраиваются. № Однородная кубическая форма Бент-функция k fi 123 Достраивается 60 f2 123+145 Достраивается 58 f3 123+456 Не достраивается f4 124+135+236 Достраивается 38 f5 123+124+135+236+456 Не достраивается f6 123+145+167 Достраивается 53 f7 123+246+357 Достраивается 25 f8 123+145+167+246 Достраивается 44 f9 123+145+246+357 Не достраивается f10 123+124+135+236+456+167 Достраивается 42 fii 123+145+167+246+357 Не достраивается fi2 123+476+568 Не достраивается f13 123+145+167+568 Достраивается 17 fi4 123+246+357+568 Достраивается 24 f15 123+246+357+128+138 Не достраивается fi6 123+145+167+357+568 Не достраивается fi7 123+145+478+568 Достраивается 46 fi8 123+124+135+236+456+167+258 Не достраивается fi9 123+124+135+236+456+178 Не достраивается f20 123+145+246+357+568 Достраивается 12 f2i 123+145+246+467+578 Достраивается 11 f22 123+145+357+478+568 Достраивается 43 f23 123+246+357+478+568 Не достраивается f24 123+246+357+148+178+258 Не достраивается f25 123+145+167+246+357+568 Не достраивается f26 123+145+167+246+238+258+348 Не достраивается f27 123+145+167+258+268+378+468 Достраивается 34 f28 123+145+246+357+238+678 Достраивается 29 f29 123+145+246+357+478+568 Не достраивается f30 123+124+135+236+456+167+258+378 Не достраивается f3i 123+156+246+256+147+157+357+348+258+458 Не достраивается - Теорема 2. Функции /1, /2, /4, /б, /8 от восьми переменных можно дополнить до бент-функций с помощью добавления булевых функций второй степени от восьми переменных; остальные функции /3, /5, /7, /э, /1о, • • • , /31 нельзя дополнить до бент-функ-ций таким образом. Теорема 3. Функции /1, /2, /4, /б, /7, /s, /10, /13, /14, /17, /20, /21, /22, /27, /2s от восьми переменных можно дополнить до бент-функций с помощью добавления слагаемых второй и четвёртой степеней от восьми переменных; остальные функции /3, /5, /э, /11, /12, /15, /1б, /1s, /19, /23, /24, /25, /26,/29,/30,/31 нельзя дополнить до бент-функций таким способом.

Ключевые слова

булева функция, бент-функция, линейная функция, квадратичная функция, кубическая функция, однородная функция, Boolean function, bent function, linear function, quadratic function, cubic function, homogeneous function

Авторы

ФИООрганизацияДополнительноE-mail
Кузьмина Татьяна АндреевнаНовосибирский государственный университетстудентка механико-математического факультетаtanya11_95@mail.ru
Всего: 1

Ссылки

Tokareva N. Bent Functions: Results and Applications to Cryptography. Acad. Press. Elsevier, 2015.
Tokareva N. Algebraic Normal Form of a Bent Function: Properties and Restrictions. IACR Cryptology ePrint Archive. https://eprint.iacr.org/2018/1160.
Черемушкин А. В. Методы аффинной и линейной классификации булевых функций // Труды по дискретной математике. М.: Физматлит, 2001. Т. 4. С. 273-314.
Langevin P. Classification of Boolean Quartics Forms in Eight Variables. http://langevin. univ-tln.fr/project/quartics/quartics.html.
 О кубической части алгебраической нормальной формы произвольной бент-функции | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/15

О кубической части алгебраической нормальной формы произвольной бент-функции | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/15