Криптографические свойства некоторых композиций векторных булевых функций | Прикладная дискретная математика. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/6

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

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

Cryptographic properties of some vectorial boolean functions compositions.pdf Обозначим через Fn множество всех подстановок на F^ и будем рассматривать следующие подклассы функций из Fn: 1) Kn - функции, полученные из тождественной подстановки с помощью n независимых транспозиций [1]; 2) Sn,k - функции вида F = (fi,... , fn), где (fi,... , fk) е Kk и fi(xi,... , Xn) = Xi 0 0 gi(xi,... ,xi-i), gi - произвольные булевы функции, существенно зависящие от k - 1 переменных, i = k + 1,..., n, k ^ n [2, 3]; 3) пусть k|n; s = n/k; Pn,k - функции F = (fi,...,fn), где ftk+i(xi,... , Xn) = = gi(t+i)(xtk+i,...,X(t+i)k), t = 0,...,s - 1 и i = 1,...,k; (gjj),..., gkj)) е Kk, j = 1,...,s. Приведём определения некоторых криптографических характеристик функций F =(fi ...fn): Fn ^ Fn [4-6]. Компонентой функции F называется булева функция vF = vifi 0 ... 0 vnfn, где v = vi... vn е Fn \\ {0n}; 0n - нулевой вектор длины n. Нелинейностью N(F) и компонентной алгебраической иммунностью AIcomp(F) функции F называются минимальные нелинейность и алгебраическая иммунность её компонент соответственно: N (F) = min N (vF), AIcomp (F) = min AI(vF). Для векторов a,b е Fn обозначим (a,b) = |{x е Fn : F(x) 0 F(x 0 a) = b}|. Показателем дифференциальной равномерности функции F называется = max (a, b). a=0n ,b Проведено экспериментальное исследование этих характеристик, а также алгебраической степени для некоторых композиций функций от 3-10 переменных. Нелинейность, алгебраическая иммунность, дифференциальная равномерность вычислялись по алгоритмам, описанным в [7]; алгебраическая степень - с помощью преобразования Мёбиуса. В ходе экспериментов получены следующие результаты: 1) Если в композиции участвует случайная подстановка F е Fn, то характеристики композиции в среднем совпадают с характеристиками функции F. Это можно объяснить тем, что при композиции любой подстановки со случайной равновероятно выбранной равномерное распределение сохраняется [8]. 2) Композиция H функции F е Kn с функцией G е Sn,k UPn,k (в любом порядке), можно сказать, берёт наилучшие свойства обоих классов: а) deg H и AIcomp(H) сохраняются, как у функции F; б) принимает значения, приблизительно равные , если G е Sn,k, и если G е Pn,k; в) N(H) « N(G). 3) При композиции функций F и G из одного класса, Kn или Pn,k, все рассмотренные свойства в общем ухудшаются: а) принимает худшее значение 2n, а нелинейность - значение 0 (хотя очень редко получаются значения лучше, чем у исходных функций); б) AIcomp(H) принимает значения 1 или 2 (у исходных функций всегда 2); в) deg H часто равна 1 (редко - как у исходных функций). 4) Про композиции функций из разных классов Sn,k и Pn,k и композиции функций одного класса Sn,k нельзя однозначно сказать о поведении свойств функций: а) deg H часто улучшается; б) AIcomp(H) принимает значения 1 или 2 (те же значения, что и у функций класса Sn,k); в) бы в первом случае принимает значения, приблизительно равные 8 функций классов Vn,k (очень редко получаются значения лучше или хуже), а во втором случае сохраняется значение 2n (как у функций класса Sn,k); г) N(H) в обоих случаях может принимать разные значения, в основном они лучше, чем наихудшие значения у функций, используемых в композициях.

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

векторная булева функция, нелинейность, алгебраическая иммунность, дифференциальная равномерность, vectorial Boolean functions, nonlinearity, algebraic immunity, differential uniformity

Авторы

ФИООрганизацияДополнительноE-mail
Липатова Екатерина СергеевнаНациональный исследовательский Томский государственный университетстуденткаkatrinelipatova@gmail.com
Всего: 1

Ссылки

Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables // Материалы Междунар. науч. конгресса по информатике: Информационные системы и технологии. Республика Беларусь, Минск, 24-27 окт. 2016. Минск: БГУ, 2016. С. 519-521.
Agibalov G. P. Substitution block ciphers with functional keys // Прикладная дискретная математика. 2017. №38. С. 57-65.
Панкратова И. А. Об обратимости векторных булевых функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 35-37.
Carlet C. Vectorial Boolean Functions for Cryptography. Cambridge: Cambridge University Press, 2010. 93 p.
Canteaut A. Lecture Notes on Cryptographic Boolean Functions. Paris: Inria, 2016. 48 p.
Nyberg K. Differentially uniform mappings for cryptography // LNCS. 1994. V. 765. P. 55-64.
Киселева Н. М., Липатова Е. С., Панкратова И. А., Трифонова E. E. Алгоритмы вычисления криптографических характеристик векторных булевых функций // Прикладная дискретная математика. 2019. №46. С. 78-87.
Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. М.: Вильямс, 2007. 832 с.
 Криптографические свойства некоторых композиций векторных булевых функций | Прикладная дискретная математика. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/6

Криптографические свойства некоторых композиций векторных булевых функций | Прикладная дискретная математика. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/6