О разложении векторной булевой функции в композицию двух векторных функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/8

О разложении векторной булевой функции в композицию двух векторных функций

Исследуется возможность представления векторной булевой функции в виде композиции двух векторных булевых функций меньшей алгебраической степени. Вводится понятие разложимости векторной булевой функции. Изучен вопрос сохранения разложимости при расширенном аффинном преобразовании. Представлена конструкция векторной булевой функции третьей степени от произвольного числа переменных, являющейся разложимой. Проведён вычислительный экперимент, в результате которого показано, что все кубические векторные булевы функции от трёх переменных являются разложимыми.

On the decomposition of a vectorial boolean function into a composition of two functions.pdf Атаки по сторонним каналам [1] -вид атак, целью которых является нахождение уязвимостей в реализации криптографической системы. На данный момент эти атаки являются одними из наиболее эффективных среди всех видов криптоаназиза. В атаках по сторонним каналам используется информация, полученная при отслеживании перепадов напряжений, времени выполнения процессов, электромагнитного излучения или звуков при проводимых алгоритмом вычислениях. Пороговая реализация [2] является контрмерой по отношению к атакам по сторонним каналам, она разделяет наборы входных данных и используемые векторные булевы функции на части, позволяя скрыть различия между операциями. Таким образом, если разбиение удовлетворяет ряду условий, при работе алгоритма не происходит утечки информации, которая может быть использована в атаке по сторонним каналам. В данном методе необходимо построить разбиение для векторной булевой функции определённым образом, что не всегда удаётся сделать. Однако придуман способ решения проблемы, использующий построение разбиения для более простых функций, композицией которых является исходная векторная булева функция. В настоящей работе анализируется возможность представления векторных булевых функций в виде композиции векторных булевых функций меньших степеней. Рассмотрены векторные булевы функции от трёх переменных с алгебраической степенью равной трём и возможность их представления в виде композии двух векторных булевых функций алгебраической степени два. Так как важно сохранение свойств при преобразованиях, а одним из наиболее распространённых является расширенное аффинное преобразование, мы исследуем вопрос сохранения разложимости векторной булевой функции при расширенной аффинной эквивалентности. Векторной булевой функцией ((n, т)-функцией) F называется произвольное отображение F : Fn ^ Fm. В случае m =1 говорят, что F - булева функция от n переменных; (n, т)-функция F может быть задана набором из m координатных булевых функций от n переменных: F(x) = (f1(x), f2(x),... , fm(x)), x е Fn. Любую (n,m)-функцию можно единственным образом записать в виде полинома Жегалкина, или алгебраической нормальной формы (АНФ): n F(x1,...,xn) = ( 0 0 a. ^ k=1 ii.....ik ф ao, ii ,...,ik xii . . . x ik где для каждого k индексы i1,... , ik попарно различны и множества {i1,... , ik} являются всеми различными непустыми подмножествами множества {1,...,n}; коэффициенты aii,...,ik, a0 принимают значения из Fm. Алгебраической степенью deg(F) функции F называется количество переменных в самом длинном слагаемом АНФ, коэффициент при котором не равен нулевому вектору. Функция степени не выше 1 называется аффинной, при этом в случае a0 = 0 функция линейна. Две (n, ^-функции F и G называются расширенно аффинно эквивалентными (EA-эквивалентными), если существуют две аффинные (n, n)-подстановки A, B на множестве Fn и аффинная (n, ^-функция C, такие, что G(x) = (B о F о A)(x) + C(x), x е Fn. Пусть F - такая (n, ^-функция, что существуют (n, ^-функции G, H, для которых max {deg(G), deg(H)} < deg(F) и F(x) = G(H(x)) для всех x е Fn. Функцию F степени d > 2, допускающую такую декомпозицию, будем называть разложимой. Теорема 1. Пусть (n, ^-функция F степени d > 2 разложима. Тогда (n, ^-функция F' = A2 о F о A1, где A1, A2 -произвольные аффинные (n, n)-подстановки, также разложима. Если F представима в виде композиции двух (n, ^-функций G, H степени меньше d, таких, что функция H обратима и deg(H-1) ^ max {deg(G), deg(H)}, то (n, ^-функция F = F + A0 разложима для любой аффинной (n, ^-функции A0. Получена конструкция, которая позволяет для любого n построить класс разложимых векторных булевых функций третьей степени. Теорема 2. Пусть i,j,p,q е {1,...,n}, i = j, p = q; {/k : k = 1,...,n} и {/Г : г = 1,...,n} - наборы произвольных линейных булевых функций от n переменных, такие, что deg(xpxq(/i(x) + /j(x))) = 3; Y(x) = (y1(x),... ,yn(x)), где yk(x) = = xpxq + /k(x) при k = 1,... , n, x е Fn. Тогда разложимой является векторная булева функция F(x), определённая следующим образом: F(x) ( A(x) \\ / xpxq(/i(x) + /j(x)) + xpxq + /i(x)/j(x) + /'(Y(x)) \\ f2(x) = xpxg (/i(x) + /j (x)) + xpxg + /i(x)/j (x) + /2 (Y (x)) \\ fn(x) J \\ xpxq(/i(x) + /j(x)) + xpxq + /i(x)/j(x) + /n(Y(x)) J

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

векторная булева функция, декомпозиция, пороговая реализация, vectorial Boolean function, decomposition, threshold implementation

Авторы

ФИООрганизацияДополнительноE-mail
Пинтус Георгий МихайловичНовосибирский государственный университетстудентg.pintus@g.nsu.ru
Всего: 1

Ссылки

Bhunia S. and Tehranipoor M. Hardware Security. A Hands-On Learning Approach. Elsevier Inc., 2019. 526p.
Nikova S., Rechberger C., and Rijmen V. Threshold implementations against side-channel attacks and glitches // Inform. Commun. Technol. 2006. No. 4307. P. 529-546.
 О разложении векторной булевой функции в композицию двух векторных функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/8

О разложении векторной булевой функции в композицию двух векторных функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/8