Обзорные лекции по моделям безопасности компьютерных систем // ПДМ. <...> См. также пример использования бент-функций в поточном шифре Grain. <...> Будем считать, что аргументы функции 2 →Z2 — булева функция от n переменных; (т. е. векторы длины n) перебираются в лексикографическом порядке; dist(f, g) — расстояние Хэмминга между функциями f и g, т. е. число позиций, в которых различаются векторы f и g; АНФ — алгебраическая нормальная форма функции; deg(f)—степень нелинейности булевой функции f, т. е. число переменных в самом длинном слагаемом ее АНФ; Wf (y) = x∈Zn 2 Nf — нелинейность булевой функции f, т. е. расстояние Хэмминга от данной функции до множества всех аффинных функций; максимально нелинейная функция — булева функция с максимально возможным значением Nf ; бент-функция (n чётное) — булева функция, такая, что все её коэффициенты Уолша—Адамара равны ±2n/2; Bn — класс бент-функций от n переменных; аффинно эквивалентные функции f и g от n переменных: существуют невырожденная n Ч n-матрица A, векторы b, c длины n и константа λ ∈ Z2, такие, что g(x) = f(Ax+b)+c, x+λ. <...> Любая квадратичная бент-функция от n переменных аффинно эквивалентна функции f(x1, . . . ,xn) = x1x2 +x3x4 +. . .+xn−1xn. <...> Определим gx бент-функция, если и только если gx новка на Zn/2 2 соответственно. <...> Расширяя класс линейных функций, естественно рассматривать для приближения булевы функции степени не выше r, где 2 r n−1. <...> №2 УДК 519.728 ЭЛЕМЕНТЫ ТЕОРИИ НЕДООПРЕДЕЛЕННОЙ ИНФОРМАЦИИ1 Л. А. Шоломов Институт системного анализа РАН, г. Москва, Россия E-mail: sholomov@isa.ru Изложены результаты, относящиеся к информационным свойствам недоопределенных данных. <...> Введены и изучены их информационные характеристики, для них получено обобщение ряда результатов классической теории информации, рассмотрены некоторые свойства, специфичные только для недоопределенных данных. <...> Ключевые слова: недоопределенный источник, доопределение, энтропия,W-энтропия, принцип Шеннона, теорема кодирования, эффект Нечипорука, правило сложения <...>
Прикладная_дискретная_математика._Приложение_№2_2009.pdf
ПДМ. Приложение. 2009. № 2.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ
ДИСКРЕТНОЙ МАТЕМАТИКИ
5–17
Токарева Н. Н. Бент-функции и их обобщения // ПДМ. Приложение. 2009. № 2. C. 5–17.
18–42
Шоломов Л. А. Элементы теории недоопределенной информации // ПДМ. Приложение. 2009. № 2. C. 18–42.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ
43–73
Агибалов Г. П. Конечные автоматы в криптографии // ПДМ. Приложение. 2009. № 2. C. 43–73.
74–114
Скобелев В. Г. Комбинаторно-алгебраические модели в криптографии // ПДМ. Приложение. 2009. № 2. C.
74–114.
115–150
Черемушкин А. В. Криптографические протоколы: основные свойства и уязвимости // ПДМ. Приложение.
2009. № 2. C. 115–150.
МАТЕМАТИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРНОЙ
БЕЗОПАСНОСТИ
151–190
Девянин П. Н. Обзорные лекции по моделям безопасности компьютерных систем // ПДМ. Приложение.
2009. № 2. C. 151–190.
Стр.1
№2
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
ПРИЛОЖЕНИЕ
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 519.7
БЕНТ-ФУНКЦИИ И ИХ ОБОБЩЕНИЯ1
Н. Н. Токарева
Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия
E-mail: tokareva@math.nsc.ru
Лекция посвящена бент-функциям — булевым функциям, максимально удаленным
в метрике Хэмминга от множества всех аффинных функций. Это экстремальное
свойство определяет большое число приложений бент-функций в самых
разных областях. Рассматриваются также обобщения бент-функций.
Ключевые слова: бент-функция, обобщения бент-функций.
Введение
Бент-функции впервые были введены О. Ротхаусом в 60-х годах XX века. Выве
бент-функций, имеют предельно низкие значения как взаимной корреляции, так и
автокорреляции (достигают нижней границы Велча). Такие семейства успешно применяются
в коммуникационных системах коллективного доступа, а также в работе со
стандартом CDMA. Технология цифровой сотовой связи CDMA (Сode Division Multiple
Access — множественный доступ с кодовым разделением каналов) была стандартизована
в 1993 г. американской телекоммуникационной промышленной ассоциацией
(US TIA) в виде стандарта IS–95. В настоящее время технология используется большинством
поставщиков беспроводного оборудования во всем мире согласно стандартам
IMT–2000 мобильной связи третьего поколения (в России — стандарты IMT–MC 450
или CDMA–450). В системах CDMA для предельного снижения отношения пиковой и
пускник Принстонского университета Оскар Ротхаус (1927–2003) после службы во
время Корейской войны в войсках связи поступил на работу математиком в Агентство
Национальной Безопасности США. С 1960 по 1966 г. он работал в Институте
оборонного анализа (IDA). Его криптографические работы того времени оценивались
руководством IDA достаточно высоко. Как и его преподавательская деятельность:
«he was one of the most important teachers of cryptology to mathematicians and
mathematics to cryptologists» [8]. На это же время приходится и его первая работа о
бент-функциях [36]. В открытой печати она появилась только в 1976 г. [37]. В ней были
установлены базовые свойства бент-функций, предложены их простейшие конструкции
и намечена классификация бент-функций от шести переменных.
В настоящее время бент-функции и их приложения изучаются очень активно.
Семейства бент-последовательностей из элементов +1 и −1, построенные на осно1Работа
выполнена при финансовой поддержке гранта Президента РФ для молодых российских
ученых (МК-1250.2009.1), Российского фонда фундаментальных исследований (проекты 07-0100248,
08-01-00671, 09-01-00528), Фонда содействия отечественной науке, ФЦП «Научные и научнопедагогические
кадры инновационной России» на 2009-2013 гг. (гос. контракт 02.740.11.0429).
Ноябрь 2009
Стр.2
6
Н. Н. Токарева
средней мощностей сигнала (peak-to-average power ratio) используются коды постоянной
амплитуды. Их построение напрямую связано с выбором специального подмножества
бент-функций.
В блочных и поточных шифрах бент-функции и их векторные аналоги способствуют
предельному повышению стойкости этих шифров к линейному и дифференциальному
методам криптоанализа. Стойкость достигается за счет использования сильно
нелинейных булевых функций в S-блоках (см., например, шифр CAST). Бентфункции
и их обобщения находят свое применение также в схемах аутентификации,
хэш-функциях (см. HAVAL) и псевдослучайных генераторах. См. также пример использования
бент-функций в поточном шифре Grain.
Несмотря на высокий интерес к бент-функциям, прогресс в их изучении самый
минимальный. Для мощности класса бент-функций не найдена асимптотика, не установлено
приемлемых нижних и верхних оценок. Мало изучены и их обобщения, возникающие
из новых постановок прикладных задач.
Данная лекция построена на основе двух обзоров автора [5, 6] и по сути является
их кратким конспектом. Приводятся основные свойства, конструкции, эквивалентные
представления бент-функций. Значительное внимание уделяется обобщениям
бент-функций. В конце статьи приводятся открытые вопросы в этой области.
Нам потребуются следующие определения и обозначения:
q, n — натуральные числа;
+ — сложение по модулю q;
x = (x1, . . . ,xn) — q-значный вектор;
Zn
q — множество всех q-значных векторов длины n;
Fqn — поле Галуа порядка qn;
x, y = x1y1 +. . .+xnyn — скалярное произведение векторов;
f : Zn
f — вектор значений длины 2n функции f. Будем считать, что аргументы функции
2 →Z2 — булева функция от n переменных;
(т. е. векторы длины n) перебираются в лексикографическом порядке;
dist(f, g) — расстояние Хэмминга между функциями f и g, т. е. число позиций,
в которых различаются векторы f и g;
АНФ — алгебраическая нормальная форма функции;
deg(f)—степень нелинейности булевой функции f, т. е. число переменных в самом
длинном слагаемом ее АНФ;
Wf (y) =
x∈Zn
2
Nf — нелинейность булевой функции f, т. е. расстояние Хэмминга от данной функции
до множества всех аффинных функций;
максимально нелинейная функция — булева функция с максимально возможным
значением Nf ;
бент-функция (n чётное) — булева функция, такая, что все её коэффициенты
Уолша—Адамара равны ±2n/2;
Bn — класс бент-функций от n переменных;
аффинно эквивалентные функции f и g от n переменных: существуют невырожденная
n Ч n-матрица A, векторы b, c длины n и константа λ ∈ Z2, такие, что
g(x) = f(Ax+b)+c, x+λ.
(−1)x,y+f(x) — преобразование Уолша—Адамара булевой функции f;
Стр.3