Оценка нелинейности сбалансированных булевых функций, порождённых обобщённой конструкцией Доббертина | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/9

Оценка нелинейности сбалансированных булевых функций, порождённых обобщённой конструкцией Доббертина

Предложено обобщение конструкции Доббертина для высоконелинейных сбалансированных булевых функций. Исследован спектр Уолша - Адамара и получены оценки спектрального радиуса предложенных функций. Доказана точная верхняя оценка на спектральный радиус (нижняя оценка нелинейности) и предложен способ построить сбалансированную функцию В от 2n переменных при помощи сбалансированной в от n - k переменных со спектральным радиусом R© = 2n + 2kR@, где R© и К$ - спектральные радиусы В и в соответственно.

An estimation of the nonlinearity of balanced boolean functions generated by generalized dob-bertin's construction.pdf В различных криптографических алгоритмах часто используются булевы функции. Нелинейность - одно из основных для них свойств, оно показывает, насколько хорошо функцию можно приблизить некоторой линейной функцией, работать с которой значительно проще. Шифр может стать уязвимым к линейному криптоанализу при низкой нелинейности даже одной его части. Примером криптографического алгоритма, скомпрометированного своими компонентами с низкой нелинейностью, может послужить старый стандарт шифрования США - DES. Введём необходимые определения. Преобразование Уолша - Адамара булевой функции f определяется как Wf (a) = (- 1)fa G Fn; спектральный радиус xeF? Rf = max |Wf(a)| и нелиненость Nf = 2n-1 - Rf/2. Бент-функциями называются функции от чётного числа переменных с максимальной возможной нелинейностью. Они впервые описаны в [1]. Подробную информацию об этом классе функций можно найти в [2, 3]. Булевы функции f и g от n переменных аффинно эквивалентны, если для всех x выполнено g(x) = f (Ax + b), где A - невырожденная матрица размера n х n; b - вектор длины n. В практических целях часто требуется чтобы функция была сбалансированной - принимала значения 0 и 1 на одном и том же числе аргументов. Но максимальное значение нелинейности сбалансированных функций неизвестно, начиная уже с восьми переменных. Лучшие оценки получаются как следствие конкретных конструкций сбалансированных функций. Конструкция, описанная Доббертином в [4], основана на модификации нормальных бент функций - функций от 2n переменных, постоянных на некотором аффинном подпространстве L размерности n. Суть конструкции заключается в замене значений бент-функции на подпространстве L значениями сбалансированной функции 9 от n переменных. При этом спектральный радиус получившейся сбалансированной функции в равен R© = 2n + Re, а её нелинейность - N© = 22n-1 - 2n-1 - Re/2. В [4] сформулирована не опровергнутая до сих пор гипотеза о несуществовании сбалансированных функций с нелинейностью выше, чем можно получить при помощи этой конструкции. Рассмотрим обобщение конструкции Доббертина, использующее бент-функции с близкими к нормальности свойствами, а именно бент-функции от 2n переменных, принимающие постоянное значение на нескольких сдвигах некоторого подпространства L размерности n - k, 0 ^ k ^ n - 2. Так как аффинная эквивалентность сохраняет нелинейность и сбалансированность, можно без ограничения общности рассматривать такие бент-функции в виде f : Fn-k х Fn+k ^ F2, для которой существуют подмножества /0,/1 С Fn+k мощностей |10| = 22k-1 + 2k-1, |/1| = 22k-1 - 2k-1, для которых справедливо f (x,y) = 0 пРи y G ^ f (x,y) = 1 пРи y G A. Такое представление прямо связано с конструкцией вида f + Ind^±, подробную информацию о которой можно найти в [5 - 7]. Здесь f - дуальная к f функция [3]. При помощи бент-функции такого вида и набора 9y, y G 10 U /1, сбалансированных функций от n - k переменных строится обобщающая конструкцию Доббертина функция в: e(x,y) Л ff> приУ£ 10 U ^ (1) f(x, y) иначе. При k = 0 описанная конструкция полностью совпадает с конструкцией Доббертина, при k = 1 она также эквивалентна конструкции Доббертина. Теорема 1. Функция в вида (1) является сбалансированной функцией и её коэффициенты Уолша - Адамара вычисляются по формуле fW/(a,b) + Е (-1)W0y(а), если а = 0, W©(a,b) = < ye^o u/i I 0 иначе. Следствие 1. Спектральный радиус в не превосходит 2n + Е R#y, причём ye/ou/i всегда можно выбрать 9y, при которых оценка достигается. Теорема 2. Пусть 9 - сбалансированная функция n - k переменных, 9y = 9 при y G 10 и 9y = 9 ф 1 при y G 11. Тогда R© = 2n + 2k . Получившееся R© зависит от , k и n. Несмотря на то, что 9 является функцией от n - k переменных, наилучший результат достигается при k = 0, то есть в случае, описанном Доббертином.

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

булевы функции, бент-функции, сбалансированность, нелинейность, спектральный радиус, boolean functions, bent functions, balancedness, nonlinearity, spectral radius

Авторы

ФИООрганизацияДополнительноE-mail
Сутормин Иван АлександровичИнститут математики им. С. Л. Соболева СО РАН; Новосибирский государственный университетмладший научный сотрудник; студентivan.sutormin@gmail.com
Всего: 1

Ссылки

Rothaus O. On "bent" functions // J. Combin. Theory. Ser.A. 1976. V.20. No.3. P. 300-305.
Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
Tokareva N. N. Bent Functions. Results and Applications to Cryptography. Acad. Press. Elsevier, 2015.
Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // LNCS. 1994. V. 1008. P. 61-74.
Kolomeec N. On properties of a bent function secondary construction // Proc. BFA'2020. https://boolean.w.uib.no/bfa-2020.
Коломеец Н. А. О некоторых свойствах конструкции бент-функций с помощью подпространств произвольной размерности // Прикладная дискретная математика. Приложение. 2018. №11. С. 41-43.
Carlet C. Two new classes of bent functions // LNCS. 1994. V. 765. P. 77-101.
 Оценка нелинейности сбалансированных булевых функций, порождённых обобщённой конструкцией Доббертина | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/9

Оценка нелинейности сбалансированных булевых функций, порождённых обобщённой конструкцией Доббертина | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/9