О связи нелинейных и дифференциальных свойств векторных булевых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/18

О связи нелинейных и дифференциальных свойств векторных булевых функций

Исследуются связи таблиц линейного приближения (LAT) и распределения разностей (DDT) векторных булевых функции. Доказано, что наличие совпадающих строк в DDT и LAT является инвариантом относительно аффинной эквивалентности, а также относительно EA-эквивалентности для нормированных DDT- и LAT-таблиц. Выдвинута гипотеза о том, что если в LAT (DD^-таблице векторной булевой функции F все строки попарно различны, то в её DDT (LA^-таблице все строки также попарно различны. Данная гипотеза проверена для функций от малого числа переменных и для известных APN-функций от не более чем 10 переменных.

On the relationship between nonlinear and differential properties of vectorial boolean functions.pdf При создании и использовании какого-либо шифра необходимо, чтобы он был устойчив к различным видам криптоанализа. Один из таких методов криптоанализа - дифференциальный [1]. Шифр устойчив к данному методу криптоанализа, если для функции F, лежащей в его основе, уравнение F(x)®F^фа) = b для любых а = 0, b имеет как можно меньше решений. Число решений данного уравнения при различных парах (а,Ь) формулируют таблицу распределения разностей (DDT) размера 2n х 2n. Если в данной таблице при а = 0 для функции F все элементы равны 0 или 2, то такая функция называется почтил совершенно нелинейной функцией (APN-функцией). Для функции можно рассмотреть также таблицу линейного приближения (LAT) размера 2n х 2n, в ячейке (v, u) которой хранится квадрат коэффициента Уолша - Ада-мара (u, v) = ^ (-1)(v,F(ж)>®(и,ж>. Данная таблица рассматривается при исследовании шифра на устойчивость к линейному криптоанализу [2]. LAT-таблица отражает нелинейность функции F. Если каждый коэффициент Уолша - Адамара функции F при v = 0 лежит в множестве {0, ±2(n+1)/2}, то такая функция называется почти бент-функцией (AB-функцией). Известно, что AB-функции и APN-функции тесно связаны. Теорема 1 [3]. Каждая AB-функция является APN-функцией. Интересно рассмотреть связи данных таблиц. Выдвинута следующая Гипотеза 1. Если в LAT (DD^-таблице векторной булевой функции F все строки попарно различны, то в её DDT (LA^-таблице все строки попарно различны. Гипотеза 1 подтверждена для всех векторных булевых функций от 3 переменных и для известных APN-функций от не более чем 10 переменных. Гипотеза 1 верна для квадратичных APN-функций от чётного числа переменных. Утверждение 1. Для любой квадратичной APN-функции от чётного числа переменных в LAT- и DDT-таблицах есть совпадающие строки. Интересно понять, при каких преобразованиях наличие совпадающих строк LAT-и DDT-таблиц является инвариантом. Векторные булевы функции F : F^ - F^ и G : F^ - F^ называются расширенно аффинно эквивалентными (EA-эквивалентными), если F = A1 о G о A2 ф A, где A1, A2 : Fn - Fn - взаимно-однозначные аффинные функции и A : Fn - Fn - аффинная функция. Если A = 0, то функции называются аффинно эквивалентными. Теорема 2. Если функции F и G аффинно эквивалентны и в DDT (LA^-таблице функции F есть совпадающие строки, то в DDT (LA^-таблице функции G также есть совпадающие строки. Аналогичную теорему можно сформулировать и для EA-эквивалентности, но для этого нужно рассматривать немного модифицированные DDT- и LAT-таблицы. Нормированной DDT-таблицей функции F будем называть таблицу, в ячейке (а, b) которой записано количество решений уравнения F(x) 0 F(x 0 а) 0 F(а) 0 F(0) = b. Нор>мир>ованной LAT-таблицей функции F будем называть LAT-таблицу функции F без линейной части. Теорема 3. Если функции F и G EA-эквивалентны и в нормированной DDT (LA^-таблице функции F есть совпадающие строки, то в нормированной DDT (LAT)-таблице функции G также есть совпадающие строки.

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

APN-функция, AB-функция, дифференциальная равномерность, нелинейность, APN function, AB function, differential uniformity, nonlinearity

Авторы

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

Ссылки

Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V.4. Iss. 1. P. 3-72.
Matsui M. and Yamagishi A. A new method for known plaintext attack of FEAL cipher // EUROCRYPT'1992. LNCS. 1992. V.658. P. 81-91.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering / eds. Y. Crama and P. Hammer. Cambridge: Cambridge University Press, 2010. P. 398-470.
 О связи нелинейных и дифференциальных свойств векторных булевых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/18

О связи нелинейных и дифференциальных свойств векторных булевых функций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/18