Сильно нелинейные булевы функции: бент-функции и их обобщения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

ТОКАРЕВА Наталья Николаевна

СИЛЬНО НЕЛИНЕЙНЫЕ БУЛЕВЫ ФУНКЦИИ: БЕНТ-ФУНКЦИИ И ИХ ОБОБЩЕНИЯ

специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи УДК 519.1, 519.7

Новосибирск 2008

003451261

Работа выполнена и Институте математики имени С. Л. Соболева СО РАН

Научный руководитель: Официальные оппоненты:

Ведущая организация:

кандидат физ.-мат. наук, Ю. Л. Васильев, доктор физ.-мат. наук, Е. А. Окольнишникова, кандидат физ.-мат. наук, Ю. В. Тарашшков. Томский государственный университет

Защита состоится 12 ноября 2008 г. в 15 часов на заседании диссертационного совета Д.003.015.01 в Институте математики им. С. Л. Соболева СО РАН по адресу: пр. Академика Коптгога, 4, 630090, г. Новосибирск.

С диссертацией можно ознакомиться в библиотеке Института математики имени С. Л. Соболева СО РАН.

Автореферат разослан 12 октября 2008 г.

Ученый секретарь диссертационного совета Д.003.015.01 при Институте математики имени С. Л. Соболева СО РАН

доктор физ.-мат. паук //у/} Шамардин Ю. В.

Bent functions deserve our bent to study them..}

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Работа относится к такой области дискретной математики, как булевы функции и их приложения в комбинаторике, теории кодирования и криптографии. Исследуется важный класс булевых функций, обладающих сильными свойствами нелинейности: бепт-функции и их обобщения.

Мера нелинейности является важной характеристикой булевой функции. Линейность и близкие к ней свойства часто свидетельствуют о простой (в определенном смысле) структуре этой функции и, как правило, представляют собой богатый источник информации о многих других ее свойствах. Задача построения булевых функций, обладающих нелинейными свойствами, естественным образом возникает во многих областях дискретной математики. И часто (что является типичной ситуацией в математике) наибольший интерес вызывают те функции, для которых эти свойства экстремальны. Такие булевы функции называются максималъно-нелгтейными (или бент-) функциями2.

Приведем ряд определений.

Пусть u = (ui,..., ит), v = (t'i,..., vm) — двоичные векторы длины т. Обозначим через (u, v) их скалярное произведение по модулю 2,

(U, v) = U1V1 ф ... ф umvm,

где Ф означает сложение над Z2. Булевой функцией от т переменных называется произвольная функция из Z™ в Ъг- Булева функция / от переменных vi,...,vm называется аффинной, если она имеет вид

/(v) - (u, v) ф а

для некоторого вектора и 6 Щ1 и константы a € Ъъ Расстоянием. Хэмминга между векторами u, v называется число координат, в

'Игра слов: «Вент-фупкции заслуживают нашего стремления изучить их...» (англ.)

2В литературе встречается также термин совершенно нелинейные функции.

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

Максимально нелинейной называется булева функция от т переменных (т — любое натуральное число) такая, что расстояние Хэмминга от данной функции до множества всех аффинных функций является максимально возможным. В случае четного тп это максимально возможное расстояние равно 2m_1 — В слу-

чае нечетного т точное значение максимального расстояния неизвестно (поиск этого значения или его оценок представляет весьма любопытную и сложную комбинаторную задачу |15|). Термин «максимально нелинейная функция» принят в русскоязычной литературе, тогда как в англоязычной широкое распространение получил термин «бент-функция» (от англ. слова bent3 — изогнутый, наклоненный). Аналогия между терминами не полная. При четном числе переменных т бент-фуикции и максимально нелинейные функции совпадают, а при нечетном т бент-функции (в отличие от максимально нелинейных) не существуют.

Преобразованием Уолта—Адамара булевой функции / от т переменных называется целочисленная функция W/, заданная на множестве Z™ двоичных векторов длины тп равенством

Wf(v) = Y, (-1)<U'V>®/(U).

ueZ'2n

В литературе функцию W¡ также называют дискретным преобразованием Фурье или преобразованием Адамара функции /. Значения Wf(v), V £ Z™, называются коэффициентами Уолша—Адамара функции /. Для них справедливо равенство Парсеваля:

£ (W/(v))2 = 22"1. vez™

Поскольку число всех коэффициентов равно 2т, из равенства следует, что максимум модуля коэффициента Уолша—Адамара не может быть меньше величины 2т/2. Заметим, что расстояние Хэммин-

Английское слово bent очень многозначно; среди его значений: «изогнутый», «кривой», «натяжение», «напряженное состояние», «призвание», а еще и «соцветие подорожника».

га от произвольной булевой функции / до множества всех аффинных функций тесно связано с коэффициентами Уолша—Адамара этой функции. А именно, это расстояние равно величине 2т~1 — 5max|W/(v)|. Очевидно, что чем меньше максимум модуля коэффициента Уолша Адамара функции /, тем больше это расстояние.

Бент-функцией называется булева функция от т переменных (га четно) такая, что модуль каждого коэффициента Уолша—Адамара этой функции равен 2'"/2. Другими словами, функция / — бент-функция, если максимум модуля Wj(v) достигает своего минимального возможного значения. В силу равенства Парсеваля это имеет место, только если модули всех коэффициентов Уолша—Адамара этой функции совпадают и равны 2т/2. Таким образом, эквивалентность определению максимально нелинейной функции (при четном т) становится очевидной.

В геометрической (кодовой) интерпретации векторы значений всех аффинных булевых функций от т переменных образуют двоичный линейный код Адамара (или иначе его называют код Рида— Маллера первого порядка) длины 27", а векторы значений бент-функций удалены от этого кода на максимально возможное расстояние Хэмминга 2т-1 _ 2(т/2)-1 (при чеТНОМ Гп).

Вент-функции были введены О. Ротхаусом еще в 60-х годах XX века, хотя его работа (23] на эту тему была опубликована лишь в 1976 году. Дж. Диллон [10] и Р. Л. МакФарланд [20] рассматривали бент-функции в связи с разностными множествами. В настоящее время известно большое число конструкций бент-функций, см. обзоры [3, 12, 7]. Тем не менее класс всех бент-функций от т переменных до сих пор не описан, для мощности этого класса не найдена асимптотика и не установлено даже приемлемых нижних и верхних оценок (некоторые продвижения в этом направлении можно найти в [9]).

Масштабы исследования бент-функций и их приложений поистине впечатляют. В настоящее время несколько сотен математиков и инженеров по всему миру регулярно публикуют свои статьи по этой тематике. Результаты обсуждаются на таких международных конференциях как EUROCRYPT, CRYPTO, ASIACRYPT, INDOCRYPT,

SETA, FSE, AAECG, ISIT, ITW, BFCA, ACCT, SIBECRYPT, Ma-БИТ и многих других. А счет общего числа публикаций о бент-функциях (и близких вопросах) уже идет на тысячи. К сожалению, публикаций на русском языке (по крайней мере, в открытой печати) известно не так уж много - всего несколько десятков. Своей работой мне хотелось бы привлечь внимание, прежде всего, российских исследователей к этой активно развивающейся области.

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

Классическая комбинаторная задача построения матриц Адама-ра порядка п, известная с 1893 года, в случае п = 2т (т четно) при некоторых ограничениях сводится к задаче построения бент-функций от m переменных [23]. В теории конечных групп построение элементарных адамаровых разностных множеств специального вида эквивалентно построению максимально нелинейных булевых функций, см. [3]. В теории кодирования широко известна задача определения радиуса покрытия произвольного кода Рида—Ма.плера, которая эквивалентна (в случае кодов первого порядка) поиску наиболее нелинейных булевых функций. В теории оптимальных кодов специальные семейства квадратичных бент-функций определяют класс кодов Кердока [16], обладающих исключительным свойством: вместе с растущим кодовым расстоянием (при увеличении длины кода) каждый код Кердока имеет максимально возможную мощность. Этим свойством коды Кердока «обязаны» экстремальной нелинейности бент-функций. Отметим, что задача построения таких семейств бент-функций, задающих код Кердока, несложно переводится в задачу поиска ортогональных разветвлений (orthogonal spreads) в конечном векторном пространстве [14], что представляется элегантным примером связи бент-функций с экстремальными геометрическими объектами. Другим примером из теории кодирования служат так называемые бент-коды — линейные двоичные коды, каждый из которых определенным образом строится из некоторой бент-функции [7]. В принципе тем же способом можно строить ли-

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

Семейства бент-последователъпостей из элементов —1 и +1, построенные на основе бент-функций, имеют предельно низкие значения как взаимной корреляции, так и автокорреляции (достигают нижней границы Велча) [21]. Поэтому такие семейства успешно применяются в коммуникационных системах коллективного доступа. Генераторы бент-последовательностей легко инициализируются случайным образом и могут быстро перестраиваться с одной последовательности на другую. Этот факт используется в работе со стандартом CDMA - Code Division Multiple Access (множественный доступ с кодовым разделением каналов) - одним из двух стандартов для цифровых сетей сотовой связи в США. Отметим здесь же, что в системах CDMA для предельного снижения отношения пиковой и средней мощностей сигнала (peak-to-average power ratio) используются, так называемые, коды постоянной амплитуды (constant-amplitude codes). И например, четверичные такие коды можно построить с помощью обобщенных булевых бент-функций [24]. Не обходится без бент-функций или их аналогов и в квантовой теории информации, см. например, [22].

Бент-функцмю можно определить как функцию, которая крайне плохо аппроксимируется аффинными функциями. Это базовое свойство бент-функций используется в криптографии. В блочных и поточных шифрах бент-функции и их векторные аналоги способствуют предельному повышению стойкости этих шифров к основным методам криптоанализа — линейному [19] и дифференциальному [6]. Стойкость достигается за счет использования сильно нелинейных булевых функций в S-блоках (важнейших компонентах современных шифров). Бент-функции и их обобщения находят свое применение также в схемах аутентификации, хэш-функциях и псевдослучайных генераторах.

Широко исследуются различные обобщения, подклассы и надклас-сы бент-функций, такие как платовидные функции, частично бент-функции, частично определенные бент,-функции, q-значные бент-функции, обобщенные булевы бент-функции, полу-бент-функции,

ненормальные бент-функции, бепт-фупкции на конечной абелевой группе, однородные бент-функции, гипер-бепт--функции, Ъ-бент-функции, нега-бенгп-функции и др. С одной стороны эти исследования мотивированы высокой сложностью задачи описания бент-функций и являются попытками перехода к более общим (или более частным) ее постановкам — в надежде на частичное решение основной проблемы. С другой стороны интерес к обобщениям постоянно стимулируется новыми запросами со стороны приложений.

Обзоры некоторых результатов о беит-фупкциях можно найти в замечательной российской монографии [3] О. А. Логачева. А. А. Сальникова и В. В. Ященко (2004 год), статье [12] немецких криптографов X. Доббертина и Г. Леандера (2004 год), главах [7] и [8] французского математика и криптографа К. Карле, написанных для готовящейся к печати книги «Boolean Methods and Models» (2008 год). Однако, любой обзор в этой области очень быстро устаревает и а priori неполон.

Цель работы — предложить новое обобщение бент-функций ■ k-бент-функции, отражающее возможность поэтапного усиления (с ростом целого параметра к) нелинейных свойств булевой функции. Основная идея обобщения заключается в том, что принадлежность функции / классу бент-функций не исключает того, что / может оказаться достаточно хорошо аппроксимируемой функциями, являющимися нелинейными, но обладающими свойством «линейности в другом смысле». Опираясь на недавние результаты теории кодирования, связанные с исследованием альтернативной «линейности» кодов, мы выделим т/2 различных типов «линейности» булевой функции от т переменных, схожих с обычной линейностью. Для этого построим специальную серию из т/2 кодов типа Адама-ра, на каждом из которых возможно определение групповой операции, согласованной с метрикой Хэмминга. Кодовые слова этих кодов есть векторы значений булевых функций вида (u,v)* ® а, где операция (•,•)*■ для каждого к, 1 ^ к ^ т/2, является аналогом скалярного произведения векторов. Булеву функцию назовем к-бент-функцией, 1 ^ k ^ т/2, если она максимально нелинейна при к различных типах «линейности» одновременно. В таком определении 1-беит-фуикции совпадают с обычными бент-функциями,

— т. е. «линейность» номер 1 есть линейность в обычном смысле,

— а (т/2)-бент-функции могут считаться «наиболее нелинейными» в данной иерархии. Цель работы — исследовать свойства А-бент-функций, привести способы их построения, классифицировать такие функции от малого числа переменных и рассмотреть возможные приложения /с-бент-функций в криптографии. А именно, исследовать возможность квадратичного криптоанализа блочных шифров на основе квадратичных аппроксимаций специального вида и показать, что использование /с-бент-функций в качестве функций шифрования максимально повышает стойкость шифра к данным квадратичным аппроксимациям.

Методика исследований. В диссертации используются комбинаторные и алгебраические методы дискретного анализа, методы теории кодирования, теории графов и криптографии. Для построения примеров и проверки гипотез проводились компьютерные исследования (используемый язык программирования С++).

Научная новизна. Все результаты диссертации являются новыми и снабжены строгими доказательствами.

Апробация работы. Результаты докладывались на российских и международных конференциях: Шестой молодежной научной школе по дискретной математике и ее приложениям в 2007 году в Москве, ISIT'2007 — IEEE Международном Симпозиуме по Теории Информации в Ницце (Франция), Шестой школе-семинаре SIBECRYPT'07

— «Компьютерная безопасность и криптография» в Горно-Алтайске, международной конференции «Математика в современном мире» в Новосибирске в 2007 году, Четвертой международной конференции BFCA'2008 — «Булевы функции: криптография и приложения» в Копенгагене (Дания), 15-ой международной конференции «Проблемы теоретической кибернетики» в Казани в 2008 году, SIBIRCON-2008 — IEEE Международной Конференции «Вычислительные Технологии в Электрической и Электронной Инженерии» в Новосибирске, Седьмой школе-семинаре SIBECRYPT'08 — «Компьютерная безопасность и криптография» в Красноярске.

Результаты докладывались на семинарах «Дискретный анализ», «Теория кодирования», «Геометрия, топология и их приложения»

и общеинститутском семинаре Института Математики СО РАН; научных семинарах Института проблем передачи информации имени А. А. Харкевича в Москве; лаборатории информатики, сигналов и систем национального центра научных исследований (I3S CNRS) в Софии Антиполисе (Франция); кафедры защиты информации и криптографии Томского государственного университета. Результаты кандидатской диссертации отмечены премией школы «Компьютерная безопасность и криптография» — SIBECRYPT'07 — в 2007 году. Работа выполнена при поддержке интеграционного проекта СО РАН N 35 «Древовидный каталог математических Интернет-ресурсов mathtree.ru», Российского фонда фундаментальных исследований (проекты 07-01-00248, 08-01-00671), гранта «Лучшие аспиранты РАН» за 2008 год Фонда содействия отечественной науке, гранта «NUGET» (Agence Nationale de la Recherche, France), совета научной молодежи ИМ СО РАН и Новосибирского государственного университета.

Основные результаты диссертации.

1. На множестве двоичных векторов длины m введены новые бинарные операции (u, v)/;, являющиеся аналогами скалярного произведения. Исследованы их свойства. Определены новые понятия к-нелинейности и к-преобразования Уолгиа—Адамара булевой функции.

2. Введено новое обобщение понятия бепт-фуикции — к-бент-функ-ция, ■■■■ отражающее возможность поэтапного усиления нелинейности булевой функции с ростом целого параметра к. Бепт-функции и 1-бент-функции совпадают. Доказано, что класс ¿-бепт-функций строго вложен в класс £-бент-функций при к > I.

3. Предложены способы построения fc-бепт-функций и исследованы их свойства. Доказано существование &-бепт-функций от m переменных любой степени нелинейности d, где 2 ^ d ^ тах{2, (т/2) — к+ 1}.

4. Классифицированы fc-бент-функции от малого числа переменных.

5. Исследованы квадратичные аппроксимации вида (и, 7Г(v))k, где V — вектор переменных; перестановка п, целое к и вектор и — параметры. Показано, что использование fc-бонт-фупкций в качестве

функций шифрования максимально повышает стойкость блочного шифра к таким аппроксимациям.

6. Рассмотрены четырехразрядные подстановки, рекомендованные для S-блоков алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с линейными) квадратичные приближения функциями вида (и, тг(у))^.

7. Отмечена аналогия между проблемами нижних—верхних оценок числа бент-функций и двоичных кодов, таких как совершенные и равномерно упакованные. Для числа равномерно упакованных двоичных кодов установлена новая (лучшая на данный момент) верхняя оценка.

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

На защиту выносится совокупность результатов о /с-бент-функ-циях: их свойства, конструкции, связи с кодами, результаты по использованию /с-бент-фупкций для построения стойких блочных шифров.

Публикации. По теме диссертации опубликовано 13 работ, [26-38]. Из них 4 статьи в журналах, 9 работ в трудах и тезисах международных конференций. На web-странице uuw.math.nsc.ru/~tokareva работы и текст диссертации доступны в электронном виде.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, предметного указателя и списка литературы из 153-х наименований. Общий объем работы -- 120 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении обсуждается актуальность исследования бент-функций и их обобщений; дается обзор полученных результатов.

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

освещенным в обзорной литературе. Отдельный раздел главы посвящен векторным бент-функциям. Отмечается аналогия между проблемами нижних—верхних оценок для числа бент-функций и числа двоичных кодов, таких как совершенные и равномерно упакованные. Для числа равномерно упакованных двоичных кодов в Теореме 1 устанавливается новая (лучшая на данный момент) верхняя оценка (доказательство теоремы приведено в главе 5).

Во второй главе вводится специальная серия двоичных кодов типа Адамара, с помощью которой определяются бинарные операции (-,-)к на множестве двоичных векторов и изучаются их свойства; определяются к-преобразование Уолта—Адамара, к-нелинейност:ь булевой функции, и вводится понятие к-бент-фунщии. С 90-х годов в теории кодирования активно стали исследоваться нелинейные коды, образы которых под действием подходящих (как правило, взаимно-однозначных и изометричных) отображений в другие метрические пространства линейны. Так, ярким примером служат -линейные коды — двоичные коды, прообразы которых относительно отобраэюения Грея

<р : 0 —+ 00,1 —> 01,2 —> 11,3-* 10,

являются линейными кодами над кольцом Интересно, что многие нелинейные в обычном смысле двоичные коды (среди них коды Кердока, Препараты, Геталса и др.) оказались Z4-линeйными, см. работы 1989 года А. А. Нечаева [4] и П. Соле [25], работу 1994 года А. Р. Хэммонса и др. ¡13]. Можно сказать, что это явление альтернативной линейности, которое удалось обнаружить, послужило ключом к структуре таких кодов и впервые позволило перенести богатый аппарат линейных методов теории кодирования в нелинейную область. В данной диссертации альтернативный подход к линейности используется для изучения булевых функций. Рассмотрим и Йглинейные коды с параметрами кодов Адамара (дапее кратко коды типа Адамара). Известно, что 22-линейный (т. е. линейный в обычном смысле) двоичный код Адамара длины 2'" единствен с точностью до эквивалентности. Д. С. Кротовым [18] было показано, что существуют в точности [т/2} попарно неэквивалентных 24-линейных кодов типа Адамара длины 2т+1 при т > 2.

Опираясь на классификацию [18] всех таких кодов, рассмотрим специальную серию двоичных кодов типа Адамара Акт, 1 ^ к ^ т/2, длины 2т (т четно). В этой серии каждый код А,п получается из линейного над Ъ\ кода заменой элементов 0,1 на 0 и элементов 2,3 на 1 в каждой координате, где Л,п — подкод соответствующего линейного четверичного кода Адамара типа 4к2т~2к (см. [18]), состоящий из всех кодовых векторов, имеющих в первой координате только 0 или 2. Каждый код образует абелеву группу относительно операции •, индуцированной операцией покоординатного сложения над Z4, определенной на векторах кода

Теорема 2. При четном т, целом к, 1 ^ к ^ т/2, выполняются

(i) код А^п является кодом с параметрами кода Адамара;

(ii) код А)п линеен, коды А\п,..., А"1/2 попарно неэквивалентны;

(iii) операция заданная на А^, согласована с метрикой Хэмминга.

Множество 21*, булевых функций, векторами значений которых являются кодовые векторы кода А^, представляет собой аналог множества аффинных функций -•-- это функции вида (u, v)t ф а, где а е Z2 и операция (■, играет роль скалярного произведения. Такие функции далее названы к-аффиннымиА . Коды Л*, выбраны таким образом, чтобы операции (-,-)k обладали многими свойствами обычного скалярного произведения и на их основе оказались возможными конструктивные построения. Отметим, что каждая операция (■, -)k при к ^ 2 не является билинейной формой. Явный вид операции (u, v)fc следующий.

Теорема 3. Пусть т,к — целые, 1 < к ^ т/2. Для любого целого i, 1 < г < т/2, любых u,veZ™ пусть Yi = (u2i-x®u2i)(v2i-i®v2i)■ Тогда

к к

<u,v)* = (00^)®{u,v>.

¿=1 j=i

^Необходимо отметить, что термин «¿-аффинная функция» в другом значении уже использовался ранее М. Л. Буряковым и О. А. Логачевым |1]. Параметр к в их работе играет роль уровня аффинности булевой функции и не имеет ничего общего с параметром, определяемым здесь. К сожалению, такое совпадение терминов было замечено уже достаточно поздно.

Каждый класс функций 21^ состоит из 2т~к+1(к + 1) аффинных функций и 2т~к+1(2к — к — 1) квадратичных функций. С помощью операции {•, определяются к-преобразование Уолша— Адамара и к-нелинейностъ Л^' булевой функции /. Верна

Теорема 4 (равенство Парсеваля для IVДля любой булевой функции / от т переменных выполняется

£ «> м)а = й*».

уег™

Булеву функцию от четного числа переменных т назовем максимально к-нелинейной (к-бент-) функцией, 1 ^ к ^ т/2, если вектор значений этой функции удален на максимально возможное расстояние 2т~1 — 2(т/2'~1 от каждого кода типа Адамара А3т, j = 1,..., к (или, что эквивалентно, = ±2т!г для любого V б "Щ

и каждогоз — 1,... ,к). Другими словами, каждая &-бент-функция одинаково плохо аппроксимируется булевыми функциями из каждого класса Я1]т, ] = I,... ,к. Обычные бент-функции представляют собой класс 1-бент-функций. Через обозначим класс всех ?с-бент-функций от т переменных.

Результаты второй главы опубликованы в работах [26, 30, 31, 32].

В третьей главе изучаются способы построения ¿-бент-фуикций и их свойства. Известно, что задача описания бепт-функций для произвольного числа переменных т, или хотя бы нахождения хороших нижних и верхних оценок числа таких функций является очень сложной. Об этом свидетельствует, например, тот факт, что число 6 является максимальным значением для т, при котором еще известно точное значение числа бент-функций (равное 5 425 430 528 ~ 232,3, см. описание в [5]), несмотря на длительный срок их исследования и большой интерес к этим объектам. В первой части третьей главы дается простое описание класса 2-бент-функций от четырех переменных.

Теорема 5. Пусть параметры ц, 12,13 иг 4 принимают различные целые значения от 1 до 4. Тогда множество функций состоит из всех функций степени 2 с квадратичными частями вида:

у^у^ © и^уи (3 типа);

У),У-12 ф ф при {¿1, г2} - {!. 2} или {3,4} (4 типа)]

^^ф^^ф^^фц,-^ при {гьг2} — {1,2} или {3,4} (4 типа)] У\У2 Ф и^з Ф У1У.1 ф у2Уз ф У2У4 ф г>зг>4 (1 тип).

Тем самым, параметр т = б становится наименьшим, при котором &-бент-функции пока не описаны.

Во второй части главы приводится итеративная конструкция /с-бент-функций. Пусть --• множество булевых функций от т переменных, З2 ~ множество симметрических функций от двух неременных.

Теорема 6. Пуст,ь числа т, г ^ 0 четны, j ^ 0 — любое, к т,акое, что 1 ^ к ^ т/2, и пусть функция / € 3ц+т+г представима в виде

¡(аъа[,...,щ,а],и',и") = ^фЫ^а^ фр(и')ф?(и"),

где ¿1,..., € )Р ^ п Я € Зг ~ функции с непересекающимися множествами переменных. Тогда $ принадлежит классу если и только если ..., 6 05], р £ 93 и ц € 23*.

В качестве следствия устанавливается, что для к > С ^ I класс к-бент-функций является собственным подклассом класса £-бент-функций Ъ1т. Показывается, что существуют /с-бент-функции с любой степенью нелинейности й, где 2 ^ с/ ^ тах{2, (т/2)-к+1}. Напомним, что степенью нелинейности булевой функции называется число переменных в самом длинном слагаемом ее алгебраической нормальной формы (или многочлена Жегалкина). Пусть Зт<к - подгруппа группы Бт подстановок на т элементах, порожденная к транспозициями: (1,2), (3,4),..., {2к — 1,2к). Пусть обозначает множество всех функций / е постоянных на каждой орбите множества под действием группы Бт^] справед-

т-к 4

ливо = 22" 01!2:1. Доказана следующая теорема о связи к-бент-функций и бент-функций.

Теорема 7. При любом четном т ^ 2, цел,ом к, 1 ^ к ^ т/2, справедливо равенство П 93^ = П ЯЗ,1,,.

Результаты третьей главы опубликованы в работах [32, 33, 37).

В четвертой главе исследуется возможность квадратичного криптоанализа блочных шифров, в основу которого положены квадратичные аппроксимации специального вида, и роль /с-бент-функций при конструировании таких шифров. Квадратичный криптоанализ является нелинейной модификацией известного метода линейного криптоанализа блочных шифров, предложенного М. Мацуи [19] в 1993 году для шифров FEAL и DES и являющегося в настоящее время одним из наиболее эффективных.

Идея метода линейного криптоанализа заключается в следующем. Сначала для известного алгоритма шифрования определяется линейное соотношение L на биты открытого текста, шифротекста и ключа, выполняющееся с вероятностью р = 1/2+е, достаточно сильно отличающейся от 1/2. Число е называется преобладанием соотношения L. Затем при фиксированном неизвестном ключе К крип-тоаналитиком собирается статистика из N пар {открытый текст — соответствующий шифротекст}, и на ее основе с учетом знака е производится различение двух простых статистических гипотез: выполняется ли соотношение L для данного неизвестного ключа К или нет. В результате для битов ключа К устанавливается новое вероятностное соотношение. Для надежной работы этого метода мощность статистики N должна быть пропорциональна величине |е|-2. Общий подход к использованию в линейном криптоанализе нелинейных аппроксимаций предложили в 1996 году JI. Кпудсеп и М. Роб-шау [17|. Основная его идея: обогатить класс аппроксимирующих функций нелинейными функциями и за счет этого повысить качество аппроксимации. Но при этом криптоаналитику придется столкнуться со следующими трудностями. Как эффективно выбрать хорошую нелинейную аппроксимацию? В линейном случае возможно решение такой задачи перебором всех 2"1 линейных функций (от m переменных). В общем случае полный перебор 22"' булевых функций неосуществим даже при малых значениях т. Как объединить нелинейные аппроксимации отдельных раундов? В целом метод нелинейного криптоанализа не получил пока должного развития.

В данной работе предлагается аппроксимировать булевы функции от m переменных vi,...,vrn функциями вида (и,7г(у))ь где тг —

1С

любая перестановка на m переменных, параметры u € Z™, к (1 ^ к < т/2) произвольны. Класс Дт всех таких аппроксимирующих функций может быть описан следующим образом. Пусть АНФ(/) — алгебраическая нормальная форма функции /; пусть Act(/) — подмножество максимальной мощности множества {1,2,... ,ш/2} такое, что для любых различных элементов i,j из Act(/) одночлены V2i-\V2j-\, V2i-\V2j, VïiV2j-\, v2,v2j принадлежат множеству АНФ(/). Через р — p(f) обозначим любую перестановку m переменных такую, что jAct(yp)¡ = max |Act(/7r)|, где по определению

!*{■) = /М'))- Справедлива

Теорема 8. Булева функция f 6 3,п, степени не больше двух, такая что /(0) = 0, принадлежит классу Дт тогда и только тогда, когда / удовлетворяет условиям

1) для любых различных чисел (1 ^ г, j ^ т/2) одночлены

V2i-iV2j-l, V2i-iV2j, V2iV2j-l, V2iV2j

одновременно принадлежат / не принадлежат АНФ(/'');

2) множество АНФ(/Р) не содерэюит одночлены вида v2i-\v2i',

3) в точности одна из переменных i>2¿-i, V2¿ принадлежит АНФ(/Р) для каждого элемента i G Act (f).

Из теоремы 8 следует, что множество аппроксимирующих функций состоит из 2"1 (т. е. всех) линейных функций и не более чем 2'»(1+'»R2m) квадратичных функций, что не ограничивает криптоана-литнка в возможности их полного перебора.

Выбор таких функций для аппроксимации обусловлен наличием простых формул для вычисления расстояния Хэммннга от произвольной булевой функции / до класса 0(7г) функций (и, к(v))^ при фиксированных параметрах 7Г и /г:

dist(/,<0(7T)) = 2m_1 - 1тах^(тг(у)),

¿ veZJ' '

а также свойствами таких функций, близкими к линейным. Исследования носят теоретический характер. Предложены модификации алгоритмов 1 и 2 линейного криптоанализа Мацуи [19] для

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

Пусть F : Z™ х Z™^" —>- Z™ — функция шифрования блочного шифра; Р, С и К — открытый текст, шифротекст и ключ соответственно. Пусть вещественное число е(К) — преобладание равенства

(a,ir(P))i®(b,cr(C))j = (d,T(K)h,

при фиксированном ключе К, где a,b € 272", d € Z™tey, перестановки 7Г, a G Sm, т G Smkey, целые числа i,j,k — некоторым образом выбранные параметры. Упомянутую выше роль /с-бент-функций в блочном шифре отражает следующее утверждение.

Теорема 9. Пусть фиксирован 'ключ К. Если вектор Ь, перестановки я, а и параметр j, таковы чт.о функция

является (т/2)-бент-функцисй, то справедливо равенство max \е(К)\= min \е{К)\ = 2^т,2)-1.

i,/c,a,d,r i,k,a,d,r

Приведены свойства аппроксимирующих функций (u, 7r(v))fc, которые могут быть использованы при согласовании нелинейных ра-ундовых аппроксимаций в квадратичном криптоанализе. В заключение рассмотрены примеры четырехразрядных подстановок, рекомендованных для применения в узлах замены (S-блоках) алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с. линейными) квадратичные соотношения специального вида на входные и выходные биты этих подстановок. Результаты четвертой главы опубликованы в работах [35, 36, 38].

В пятой главе диссертации приводится доказательство Теоремы 1, формулировка которой дана в первой главе. Результаты главы опубликованы в работах [27, 28, 29].

Благодарности. Я искренне признательна своему научному руководителю Ю. JI. Васильеву (Институт математики им. С. JI. Соболева) за неизменную поддержку и постоянное внимание к данной работе. Моя самая глубокая благодарность А. А. Нечаеву (Московский государственный университет) и JI. А. Бассалыго (Институт проблем передачи информации им. А. А. Харкевича, Москва), проявившим неподдельный интерес к моей работе и высказавшим немало ценных замечаний и критики. Я очень благодарна сотрудникам института математики им. С. Л. Соболева: Д. С. Кротову — за ценные замечания, позволившие существенно расширить множество кодов, для которых справедлива Теорема 1, и В. Н. Потапову, взявшему на себя труд прочитать рукопись и указавшему па целый ряд неточностей. Мне очень приятно выразить признательность профессору Патрику Соле (Национальный Центр Научных Исследований — CNRS, — София Антиполис, Франция) за гостеприимство и увлекательную совместную работу в области бент-функций, благодаря которой удалось узнать много нового. С большим удовольствием я благодарю Лилию Будагян (Университет Бергена, Норвегия) за консультации по векторным бент-функциям, внимательное прочтение текста и замечания, которые трудно переоценить. Отдельную благодарность я приношу всем рецензентам печатных работ, обратившим мое внимание на многие существенные вопросы.

Список литературы

[1] Буряков М. Л., Логачев О. А. Об уровне аффинности булевых функций // Дискретная математика. 2005. Т. 17, N 4. С. 98-107.

[2] Кротов Д. С. ¿^-линейные совершенные коды // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N 4. С. 78-90 (translated at http://arxiv.org/abs/0710.0198).

f31 Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: Московский центр непрерывного математического образования, 2004.

[4] Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1, N 4. С. 123-139.

[5] Agievich S. V. On the representation of bent-functions by bent-rectangles // Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics (Petrozavodsk, Russia. June 1-6, 2000). Proc. Boston: VSP, 2000. P. 121-135.

[6] Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V. 4, N 1. P. 3-72.

[7] Carlet C. Boolean functions for cryptography and error correcting codes // Chapter of the monograph «Boolean Methods and Models», Cambridge Univ. Press (P. Hammer, Y. Crama eds.), to appear. Prelim, version is available at

www-rocq.inria.fr/secret/Claude.Carlet/chap-fcts-Bool.pdf.

[8] Carlet C. Vectorial Boolean functions for cryptography // Chapter of the monograph «Boolean Methods and Models», Cambridge Univ. Press (P. Hammer, Y. Crama eds.), to appear. Prelim, version is available at www-rocq.inria.fr/secret/Claude.Carlet/chap-vectorial-fcts .pdf.

[9] Carlet C., Klapper A. Upper bounds on the numbers of resilient functions and of bent functions // 23rd Symposium on Information Theory (Benelux, Belgium. May, 2002) Proc. 2002. P. 307-314. The full version will appear in Lecture Notes dedicated to Philippe Delsarte.

110] Dillon J. F. A survey of bent functions // The NSA Technical J. 1972. Special Issue. P. 191-215.

]11] Dillon J. F. Elementary Hadamard difference sets // Ph. D. Thesis, Univ. of Maryland, 1974.

[12] Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and their applications. - SETA 2004. Third Int. conference (Seul, Korea. October 24-28, 2004). Revised selected papers. Berlin: Springer, 2005. P. 1-29 (Lecture Notes in Comput. Sci. V. 3486).

[13] Hammons A. R., Kumar• P. V., Calderbank A. R., Sloane N. J. A., Solé P. The Z4-liiiearity of Kerdock, Preparata, Goethals, and related codes ,// IEEE Trans. Inform. Theory. 1994. V. 40, N 2. P. 301-319.

[14] Kantor W. M. Codes, quadratic forms and finite geometries // Proceedings of Symposia in Applied Math. 1995. V. 50. P. 153-177.

[15] Kavut S., Maitra S., Yucel M. D. Search for Boolean functions with excellent profiles in the rotation symmetric class // IEEE Trans. Inform. Theory. 2007. V. 53, N 5. P. 1743-1751.

[16] Kerdock A. M. A class of low-rate non-linear binary codes // Inform. Control. 1972. V. 20, N 2. P. 182-187.

[17] Knudsen L. R., Robshaw M. J. B. Non-linear approximation in linear cryptanalysis // Advances in Cryptology - EUROCRYPT'96. Workshop on the theory and application of cryptographic techniques (Saragossa, Spain. May 12 16, 1996). Proc. SpringerVerlag. 1996. P. 224- 236 (Lecture Notes in Comput, Sci. V. 1070).

[18] Krotov D. S. Z4-linear Hadamard and extended perfect codes // Proc. of the Int. Workshop on Coding and Cryptography (Paris, France. January 8 -12, 2001). P. 329 334.

[19] Matsui M. Linear cryptanalysis method for DES cipher // Advances in Cryptology - EUROCRYPT'93. Workshop on the theory and application of cryptographic techniques (Lofthus, Norway. May 2327, 1993). Proc. Berlin: Springer, 1994. P. 386-397 (Lecture Notes in Comput, Sci. V. 765).

[20] McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory. Ser. A. 1973. V. 15, N 1. P. 1-10.

[21] Olsen J. D., Scholtz R. A., Welch L. R. Bent-function sequences // IEEE Trans. Inform. Theory. 1982. V. 28, N 6. P. 858......864.

[22] Riera C., Parker M.G. Generalised bent criteria for Boolean functions (I) // IEEE Trans. Inform. Theory 2006. V. 52, N 9. P. 4142-4159.

123] Rothaus 0. On bent functions // J. Combin. Theory. Ser. A. 1976. V. 20, N 3. P. 300-305.

[24] Schmidt K-U. Quaternary constant-amplitude codes for multicode CDMA // Available at http://arxiv.org/abs/cs.IT/0611162.

[25] Solé P. A quaternary cyclic code, and a family of quadriphase sequences with low correlation properties // Third International Colloquium «Coding Theory and Applications» (Toulon, France. November 2-4, 1988). Proc. Springer. 1989. P. 193-201 (Lecture Notes in Comput. Sci. V. 388).

Публикации автора по теме диссертации (доступны по адресу www.math.nsc.ru/~tokareva)

[26] Токарева Н. Н. Иерархия классов беит-функций кратной нелинейности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16-21 апреля, 2007) Часть III, 2007. С. 5-11.

[27] Токарева Н. Н. О верхней оценке числа равномерно упакованных двоичных кодов // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16-21 апреля, 2007) Часть III, 2007. С. 11-16.

[28] Tokareva N. N. An upper bound for the number of uniformly packed codes // IEEE International Symposium on Information Theory — ISIT'2007. (Nice, France. June 24-29, 2007). Proc. 2007. P. 346-350.

[29] Токарева H. H. О верхней оценке числа равномерно упакованных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14, N 3. С. 90-97.

[30] Tokareva N. N. On fc-bent functions // Вестник Томского госуниверситета. Приложение. 2007. N 23. С. 74-76.

[31] Токарева Н. Н. Бент-функции кратной нелинейности: fc-бент-функции // Материалы российской конференции «Математика в современном мире» (Новосибирск, Россия. 17-21 сентября, 2007). С. 288 -289.

[32] Токарева Н. Н. Бент-функции с более сильными свойствами нелинейности: /с-бент-функции // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14, N 4. С. 76-102.

[33] Tokareva N. N. k-Bent functions and quadratic approximations in block ciphers // Proc. Fourth International Conference BFCA — Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). P. 132-148.

[34] Токарева H. H. ^-Преобразование Уолша-Адамара в теории кодирования и криптографии // Материалы XV Международной конференции «Проблемы теоретической кибернетики» (Казань, Россия, 2-7 июня, 2008). С. 113-114.

[35] Tokareva N. N. fc-Bent functions: from coding theory to cryptology // Proc. First IEEE International Conference SIBIRCON — Computational Technologies in Electrical and Electronics Engineering (Novosibirsk, Russia, July 21-25, 2008). P. 36-40.

[36] Токарева H. H. О квадратичных аппроксимациях в блочных шифрах // Пробл. передачи информ. 2008. Т. 44, Вып. 3. С. 105 127.

[37] Токарева Н. Н. Описание fc-бент-функций от четырех переменных // Дискр. анализ и исслед. операций. 2008. Т. 15, N 4. С. 74-83.

[38] Токарева Н. Н. Квадратичные аппроксимации специального вида для четырехразрядных подстановок в S-блоках // Прикладная дискретная математика. 2008. Т. 1, N 1. С. 50-54.

Токарева Наталья Николаевна

Сильно нелинейные булевы функции: бент-функции и их обобщения

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 2 октября 2008 г. Формат 60x84 1/16. Усл. печ. л. 1,4. Уч.-изд. л. 1,4. Тираж 140 экз. Заказ N 173.

Отпечатано в ООО "Омега Принт" 630090 Новосибирск, пр. Лаврентьева, 6.

Введение

1 Бент-функции и их обобщения

1.1 Определения и обозначения.

1.2 Конструкции и свойства.

1.3 О числе бент-функций и двоичных кодов.

1.4 Обобщения бент-функций.

1.4.1 Платовидные функции.

1.4.2 Частично бент-функции.

1.4.3 Частично определенные бент-функции.

1.4.4 g-Значные бент-функции

1.4.5 Обобщенные булевы бент-функции.

1.4.6 Полу-бент-функции (semi-bent functions)

1.4.7 Ненормальные бент-функции (nonnormal bent functions)

1.4.8 Бент-функции на конечной абелевой группе.

1.4.9 Однородные бент-функции (homogeneous bent functions)

1.4.10 Гипер-бент-функции (hyper-bent functions)

1.4.11 Z-бент-функции.

1.4.12 Нега-бент-функции, бент-функции, I-бент-функции

1.5 Векторные бент-функции.

1.6 Другие направления.

2 Понятие fc-бент-функции

2.1 Определения и обозначения.

2.2 Коды с параметрами кодов Адамара.

2.3 Бинарная операция (u, v)^

2.4 Понятие /г-аффинной функции.

2.5 Понятие fc-бент-функции

3 Построение fc-бент-функций и их свойства

3.1 /с-Бент-функции от малого числа переменных

3.1.1 Описание.

3.1.2 Замечания.

3.2 Индуктивный способ построения /г-бент-функций

3.3 Взаимосвязь А;-бент-функций с бент-функциями.

4 Квадратичные аппроксимации в блочных шифрах

4.1 Линейный криптоанализ и его модификации.

4.1.1 Линейный криптоанализ.

4.1.2 Проблемы нелинейного криптоанализа

4.1.3 Квадратичный криптоанализ.

4.2 Класс аппроксимирующих функций Ат.

4.3 Квадратичные аппроксимации в блочных шифрах.

4.4 Анализ четырехразрядных подстановок в S-блоках алгоритмов ГОСТ, DES, s3 DES.

4.5 Замечания и дополнения

Bent functions deserve our bent to study them.}

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

Мера нелинейности является важной характеристикой булевой функ- . ции. Линейность и близкие к ней свойства часто свидетельствуют о простой (в определенном смысле) структуре этой функции и, как правило, представляют собой богатый источник информации о многих других ее I свойствах. Задача построения булевых функций, обладающих нелинейными свойствами, естественным образом возникает во многих областях дискретной математики. И часто (что является типичной ситуацией в ма- t тематике) наибольший интерес вызывают те функции, для которых эти свойства экстремальны. Такие булевы функции называются максимально-нелинейными (или бент-) функциями2.

Приведем ряд определений.

Пусть и = (щ,., ит), v = (г»1,., vm) — двоичные векторы длины т. Обозначим через (u, v) их скалярное произведение по модулю 2, u, v) = mvi Ф . ф umvm, где ф означает сложение над Z2. Булевой функцией от т переменных называется произвольная функция из Z™ в Z2. Булева функция / от переменных -Ui,. ,г>т называется аффинной, если она имеет вид v) = (u,v)ea хИгра слов: «Бент-функции заслуживают нашего стремления изучить их.» (англ.)

2В литературе встречается также термин совершенно нелинейные функции. для некоторого вектора и 6 Щ1 и константы а Е Z2. Расстоянием Хэмминга между векторами u, v называется число координат, в которых они различаются. Под расстоянием между двумя булевыми функциями от т переменных понимается расстояние Хэмминга между их векторами значений длины 2т.

Максимально нелинейной называется булева функция от т переменных (га — любое натуральное число) такая, что расстояние Хэмминга от данной функции до множества всех .аффинных функций является максимально возможным. В случае четного га это максимально возможное расстояние равно 2т~1 — В случае нечетного га точное значение максимального расстояния неизвестно (поиск этого значения или его оценок представляет весьма любопытную и сложную комбинаторную задачу [99, 86]). Термин «максимально нелинейная функция» принят в русскоязычной литературе, тогда как в англоязычной широкое распространение получил термин «бент-функция» (от англ. слова bent3 — изогнутый, наклоненный). Аналогия между терминами не полная. При четном числе переменных га бент-функции и максимально нелинейные функции совпадают, а при нечетном га бент-функции (в отличие от максимально нелинейных) не существуют.

Преобразованием Уолша—Адамара булевой функции / от га переменных называется целочисленная функция Wf} заданная на множестве Z™ двоичных векторов длины га равенством

В литературе функцию также называют дискретным преобразованием Фурье или преобразованием Адамара функции /. Значения Wf(v), V е называются коэффициентами Уолша—Адамара функции /. Для них справедливо равенство Парсеваля: veZ^1

Поскольку число всех коэффициентов равно 2т, из равенства следует, что максимум модуля коэффициента Уолша—Адамара не может быть меньше

3Английское слово bent очень многозначно; среди его значений: «изогнутый», «кривой», «натяжение», «напряженное состояние», «призвание», а еще и «соцветие подорожника».

W)(v) = ]Г (-1)М©Ди) ueiz величины 2т/2. Заметим, что расстояние Хэмминга от произвольной булевой функции / до множества всех аффинных функций тесно связано с коэффициентами Уолша—Адамара этой функции. А именно, это расстояние равно величине 2т~1 — | шах Очевидно, что чем меньше максимум модуля коэффициента Уолша—Адамара функции /, тем больше это расстояние.

Бент-функцией называется булева функция от га переменных (га четно) такая, что модуль каждого коэффициента Уолша—Адамара этой функции равен 2го/2. Другими словами, функция / — бент-функция, если макси мум модуля достигает своего минимального возможного значения. В силу равенства Парсеваля это имеет место, только если модули всех коэффициентов Уолша—Адамара этой функции совпадают и равны 2т¡2. Таким образом, эквивалентность определению максимально нелинейной функции (при четном т) становится очевидной.

В геометрической (кодовой) интерпретации векторы значений всех аффинных булевых функций от т переменных образуют двоичный линейный код Адамара (или иначе его называют код Рида—Маллера первого порядка) длины 2т, а векторы значений бент-функций удалены от этого кода на максимально возможное расстояние Хэмминга 2т~1 — (при четном т).

Бент-функции были введены О. Ротхаусом еще в 60-х годах XX века, хотя его работа [121] на эту тему была опубликована лишь в 1976 году. Дж. Диллон [70] и Р. Л. МакФарланд [104] рассматривали бент-функции в связи с разностными множествами. В настоящее время известно большое число конструкций бент-функций, см. обзоры [15, 76, 52]. Тем не менее класс всех бент-функций от т переменных до сих пор не описан, для мощности этого класса не найдена асимптотика и не установлено даже приемлемых нижних и верхних оценок (некоторые продвижения в этом направлении можно найти в работе [60]).

Масштабы исследования бент-функций и их приложений поистине впечатляют. В настоящее время несколько сотен математиков и инженеров по всему миру регулярно публикуют свои статьи по этой тематике. Результаты обсуждаются на таких международных конференциях как ЕХЛЮСКУРТ,

CRYPTO, ASIACRYPT, INDOCRYPT, SETA, FSE, AAECC, ISIT, ITW, BFCA, ACCT, SIBECRYPT, МаБИТ и многих других. А счет общего числа публикаций о бент-функциях (и близких вопросах) уже идет на тысячи. К сожалению, публикаций на русском языке (по крайней мере, в открытой печати) известно не так уж много — всего несколько десятков. Своей работой мне хотелось бы привлечь внимание, прежде всего, российских исследователей к этой активно развивающейся области.

Так почему же бент-функции столь популярны? В качестве ответа приведем (далеко не полную) серию примеров теоретических и практических приложений бент-функций в комбинаторике, алгебре, теории кодирования, теории информации, теории символьных последовательностей, криптографии и криптоанализе.

Классическая комбинаторная задача построения матриц Адамара порядка п, известная с 1893 года, в случае п = 2т (т четно) при некоторых ограничениях сводится к задаче построения бент-функций от m переменных [121]. В теории конечных групп построение элементарных адамаро-вых разностных множеств специального вида эквивалентно построению максимально нелинейных булевых функций, см. [15]. В теории кодирования широко известна задача определения радиуса покрытия произвольного кода Рида—Маллера, которая эквивалентна (в случае кодов первого порядка) поиску наиболее нелинейных булевых функций [99, 86]. В теории оптимальных кодов специальные семейства квадратичных бент-функций определяют класс кодов Кердока [87], обладающих исключительным свойством: вместе с растущим кодовым расстоянием (при увеличении длины кода) каждый код Кердока имеет максимально возможную мощность, см. [69, 25]. Этим свойством коды Кердока «обязаны» экстремальной нелинейности бент-функций. Отметим, что задача построения таких семейств бент-функций, задающих код Кердока, несложно переводится в задачу поиска ортогональных разветвлений (orthogonal spreads) в конечном векторном пространстве [85], что представляется элегантным примером связи бент-функций с экстремальными геометрическими объектами. Другим примером из теории кодирования служат так называемые бент-коды — линейные двоичные коды, каждый из которых определенным образом строится из некоторой бент-функции [52]. В принципе тем же способом можно строить линейные коды из любых булевых функций, но только бент-коды будут иметь всего два ненулевых значения для весов кодовых слов и при этом максимально возможные кодовые размерности.

Семейства бент-последователъностей из элементов —1 и +1, построенные на основе бент-функций, имеют предельно низкие значения как взаимной корреляции, так и автокорреляции (достигают нижней границы Велча) [112]. Поэтому такие семейства успешно применяются в коммуникационных системах коллективного доступа. Генераторы бент-последовательностей легко инициализируются случайным образом и могут быстро перестраиваться с одной последовательности на другую. Этот факт используется в работе со стандартом CDMA — Code Division Multiple Access (множественный доступ с кодовым разделением каналов) — одним из двух стандартов для цифровых сетей сотовой связи в США. Отметим здесь же, что в системах CDMA для предельного снижения отношения пиковой и средней мощностей сигнала (peak-to-average power ratio) используются, так называемые, коды постоянной амплитуды (constant-amplitude codes). И например, четверичные такие коды можно построить с помощью обобщенных булевых бент-функций [123]. Не обходится без бент-функций или их аналогов и в квантовой теории информации, см. например, [118].

Бент-функцию можно определить как функцию, которая крайне плохо аппроксимируется аффинными функциями. Это базовое свойство бент-функций используется в криптографии. В блочных и поточных шифрах бент-функции и их векторные аналоги способствуют предельному повышению стойкости этих шифров к основным методам криптоанализа — линейному [102] и дифференциальному [36], см. подробнее [17]. Стойкость достигается за счет использования сильно нелинейных булевых функций в S-блоках (важнейших компонентах современных шифров) [110, 28], см., например, шифр CAST. Бент-функции и их обобщения находят свое применение также в схемах аутентификации [58], хэш-функциях и псевдослучайных генераторах [18].

Широко исследуются различные обобщения, подклассы и надклассы бент-функций, такие как платовидные функции [15], частично бент-функ-ции [15], частично определенные бент-функции [15], q-значные бегт-функ-ции [93, 2], обобщетше булевы бент-функции [123], полу-бент-функции

64], ненормальные бент-функции [48], бент-функции на конечной абеле-вой группе [13], однородные бент-функции [117], гипер-бент-функции [135], Z—бент-функции [77], нега-бент-функции [114] и др. С одной стороны эти исследования мотивированы высокой сложностью задачи описания бент-функций и являются попытками перехода к более общим (или более частным) ее постановкам — в надежде на частичное решение основной проблемы. С другой стороны интерес к обобщениям постоянно стимулируется новыми запросами со стороны приложений.

Обзоры некоторых результатов о бент-функциях можно найти в замечательной российской монографии 2004 года О. А. Логачева, А. А. Сальникова и В. В. Ященко [15], статье немецких криптографов X. Доббертина и Г. Леандера [76] 2004 года, главах [52] и [53] французского математика и криптографа К. Карле, написанных для готовящейся к печати кршги «Boolean Methods and Models» (2008 год). Однако, любой обзор в этой области очень быстро устаревает и a priori неполон.

В данной диссертации в рамках теоретико-кодового подхода вводится новое обобщение бент-функций — k-бент-функции, — отражающее возможность поэтапного усиления (с ростом целого параметра к) нелинейных свойств булевой функции. Основная идея обобщения заключается в том, что принадлежность функции / классу бент-функций не исключает того, что / может оказаться достаточно хорошо аппроксимируемой функциями, являющимися нелинейными, но обладающими свойством «линейности в другом смысле». Опираясь на недавние результаты теории кодирования, связанные с исследованием альтернативной «линейности» кодов, мы выделяем т/2 различных типов «линейности» булевой функции от т переменных, схожих с обычной линейностью. Для этого строится специальная серия из т/2 кодов типа Адамара, на каждом из которых возможно определение групповой операции, согласованной с метрикой Хэмминга. Кодовые слова этих кодов есть векторы значений булевых функций вида (u, где операция (•, •)/„. для каждого 1 < к ^ т/2, является аналогом скалярного произведения векторов. Булеву функцию назовем к-бент-фунщией, 1 ^ k ^ т/2, если она максимально нелинейна при к различных типах «линейности» одновременно. В таком определении 1-бент-функции совпадают с обычными бент-функциями, — т. е. «линейность» номер 1 есть линейность в обычном смысле, — а (ш/2)-бент-функции могут считаться «наиболее нелинейными» в данной иерархии. В работе исследуются свойства &-бент-функций, приводятся способы их построения, классификация таких функций от малого числа переменных и возможные приложения к-бент-функций в криптографии. А именно, рассматривается возможность квадратичного криптоанализа блочных шифров на основе квадратичных аппроксимаций специального вида. Показано, что использование к-бент-функций в качестве функций шифрования предельно повышает стойкость шифра к данным квадратичным аппроксимациям.

Отметим, что наш подход предполагает дальнейшие обобщения: в частности, появление новых типов «линейности» приведет к вопросам существования соответствующих «бент»-функций и т. п. Возникает естественный вопрос: существует ли «самая нелинейная» булева функция? Полагаю, что задача в такой общей постановке лишена смысла. Во-первых, из-за невозможности дать строгое определение понятию «линейности». А во-вторых — из-за противоречивости тех свойств, которыми должна обладать искомая функция (в этом можно убедиться на простых примерах). Считаю, что исследовать «нелинейные» свойства функций имеет смысл лишь при конкретном понимании «линейности», представляющем интерес для теоретических или практических приложений.

В первой главе диссертации приводятся основные понятия и обзор известных результатов о бент-функциях. Особое внимание уделяется известным обобщениям бент-функций, пока еще очень слабо освещенным в обзорной литературе. Отдельный раздел главы посвящен векторным бент-функциям. Отмечается аналогия между проблемами нижних—верхних оценок для числа бент-функций и числа двоичных кодов, таких как совершенные и равномерно упакованные. Для числа равномерно упакованных двоичных кодов в Теореме 1 устанавливается новая (лучшая на данный момент) верхняя оценка (доказательство теоремы приведено в главе 5).

Во второй главе вводится специальная серия двоичных кодов типа Адамара, с помощью которой определяются бинарные операции (•, •)/. на множестве двоичных векторов и изучаются их свойства; определяются к-преобразование Уолша—Адамара, к-нелинейностъ булевой функции, и вводится понятие к-бент-функции.

С 90-х годов в теории кодирования активно стали исследоваться нелинейные коды, образы которых под действием подходящих (как правило, взаимно-однозначных и изометричных) отображений в другие метрические пространства линейны. Так, ярким примером служат 1^-линейные коды — двоичные коды, прообразы которых относительно отображения Грея ц> : 0 00,1 01,2 11,3 10, являются линейными кодами над кольцом Интересно, что многие нелинейные в обычном смысле двоичные коды (среди них коды Кердока, Препараты, Геталса и др.) оказались линейными, см. работы 1989 года А. А. Нечаева [19] и П. Соле [129], работу 1994 года А. Р. Хэммонса и др. [80]. Можно сказать, что это явление альтернативной линейности, которое удалось обнаружить, послужило ключом к структуре таких кодов и впервые позволило перенести богатый аппарат линейных методов теории кодирования в нелинейную область, см. [65, 20, 9, 91, 50, 39, 38], обзор [138] и другие работы. В данной диссертации альтернативный подход к линейности используется для изучения булевых функций.

Рассмотрим и ^4-линейные коды с параметрами кодов Адамара (далее кратко — коды типа Адамара). Известно, что Ъ^-линейный (т. е. линейный в обычном смысле) двоичный код Адамара длины 2т единствен с точностью до эквивалентности. Д. С. Кротовым [91] было показано, что существуют в точности \т/2\ попарно неэквивалентных Ж^линейных кодов типа Адамара длины 2т+1 при т > 2. Опираясь на классификацию [91] всех таких кодов, рассмотрим специальную серию двоичных кодов типа Адамара Акт, 1 < к ^ т/2, длины 2т [т четно). В этой серии каждый код А^ получается из линейного над кода А^ заменой элементов 0,1 на 0 и элементов 2,3 на 1 в каждой координате, где — подкод соответствующего линейного четверичного кода Адамара типа 4,к2т~2к (см. [91]), состоящий из всех кодовых векторов, имеющих в первой координате только 0 или 2. Каждый код А^ образует абелеву группу относительно операции • , индуцированной операцией + покоординатного сложения над Z4, определенной на векторах кода

Теорема 2. При четном т, целом к, 1 ^ к ^ га/2, выполняются код А\са является кодом с параметрами кода Адамара;

И) код А1т линеен, коды А]п,. ) Атп попарно неэквивалентны',

111) операция заданная на Асогласована с метрикой Хэмминга.

Множество булевых функций, векторами значений которых являются кодовые векторы кода А^п, представляет собой аналог множества аффинных функций — это функции вида (и, V}/; ® а, где аб22и операция (•, играет роль скалярного произведения. Такие функции далее названы к-аффиниымиА . Коды А^ выбраны таким образом, чтобы операции (•, -}к обладали многими свойствами обычного скалярного произведения и на их основе оказались возможными конструктивные построения. Отметим, что каждая операция (-,')к при к ^ 2 не является билинейной формой. Явный вид операции (и, V);;; следующий.

Теорема 3. Пусть т,к — целые, 1 ^ к ^ т/2. Для любого целого г, 1 ^ г ^ т/2, и любых и, V € Ъ™ пусть У{ = (г£2г-1 Ф^2г)(^2г-1 Тогда к к

Каждый класс функций 21^ состоит из 2т~к+1(к + 1) аффинных функций и 2т~к+1(2к — к — 1) квадратичных функций.

С помощью операции {•, определяются к-преобразование Уолта — Адамара и к-нелинейность булевой функции /. Справедлива

Теорема 4 (равенство Парсеваля для И7^). Для любой булевой функции f ~om т переменных выполняется чет.?

Булеву функцию от четного числа переменных т назовем максимально к-нелинейной (к-бент-) функцией, 1 < к ^ т/2, если вектор значений этой функции удален на максимально возможное расстояние 2т~1 от каждого кода типа Адамара А3т, у = 1,., к (или, что эквивалентно,

4Необходимо отметить, что термин «¿-аффинная функция» в другом значении уже использовался ранее М. Л. Буряковым и О. А. Логачевым [4]. Параметр к в их работе играет роль уровня аффинности булевой функции и не имеет ничего общего с параметром, определяемым здесь. К сожалению, такое совпадение терминов было замечено уже достаточно поздно.

W^p(v) = i2m/2 для любого v £ Щ1 и каждого j — 1,.,к). Другими словами, каждая &-бент-функция одинаково плохо аппроксимируется булевыми функциями из каждого класса . j ~ 1,., к. Обычные бент-функции представляют собой класс 1-бент-функций. Через обозначим класс всех /с-бент-функций от т переменных.

Результаты второй главы опубликованы в работах [141, 145, 146, 147].

В третьей главе изучаются способы построения /с-бент-функций и их свойства. Известно, что задача описания бент-функций для произвольного числа переменных т, или хотя 6¿i нахождения хороших нижних и верхних оценок числа таких функций является очень сложной. Об этом свидетельствует, например, тот факт, что число б является максимальным значением для т, при котором еще известно точное значение числа бент-функций (равное 5 425430 528 ~ 232,3, см. описание в [29, 105], и более раннюю работу [116]), несмотря на длительный срок их исследования и большой интерес к этим объектам. В первой части третьей главы дается простое описание класса 2-бент-функций от четырех переменных.

Теорема 5. Пусть параметры ¿i, ¿2,гз и i4 принимают различные целые значения от 1 до 4. Тогда множество функций состоит из всех функций степени 2 с квадратичными частями вида:

VixVy, ф ViЗг>г4 (3 типа)] vixvÍ2 ф v^vi3 Ф v^v^ при {¿i, г2} = {1,2} или {3,4} (4 типа)-, vixvÍ2 ф vÍ2vÍ3 Ф vÍ3vÍ4 ф vhvÍ3 при {гь г2} = {1,2} или {3,4} (4 типа)] V1V2 Ф V\v% Ф viv^ ф V2V3 ф V2V4 ф V3V4 (1 тип).

Тем самым, параметр т = 6 становится наименьшим, при котором к-бент-функции пока не описаны.

Во второй части главы приводится итеративная конструкция к-бент-функций. Пусть 3vn ~ множество всех булевых функций от т переменных, Зз — множество симметрических функций от двух переменных.

Теорема 6. Пусть числа т, г ^ 0 четны, j ^ 0 — любое, к такое, что 1 ^ k ^ га/2, и пусть функция / € $2j+m+r представима в виде f(a1,a'1,.,aj,a'j,u',u")= s¿(a¿,a'¿)j ®p(u')®g(u"), где si,.,sj G £ и q E — функции с непересекающимися множествами переменных. Тогда f принадлежит классу ^{'j+m-w если и только если si,., Sj G р G и q G QSj.

В качестве следствия устанавливается, что для к > £ > 1 класс к-бент-функций ЯЗ^ является собственным подклассом класса ^-бент-функций Показывается, что существуют /г-бент-функции с любой степенью нелинейности d, где 2 ^ d < max{2, Щ — к + 1}.

Пусть Smfk — подгруппа группы Sm подстановок на m элементах, порожденная к транспозициями: (1,2), (3,4),., (2к — 1,2к). Пусть обозначает множество всех функций / G постоянных на каждой орбите множества Z™ под действием группы 5m>fc; справедливо = 22"1 23. Доказана следующая теорема о связи /с-бент-функций и бент-функций.

Теорема 7. При любом четном га ^ 2, целом к, 1 ^ к ^ т/2, справедливо равенство ^ П ЯЗ^ = ^ П

Результаты третьей главы опубликованы в работах [147, 148, 152].

В четвертой главе исследуется возможность квадратичного криптоанализа блочных шифров, в основу которого положены квадратичные аппроксимации специального вида, и роль /с-бент-функции при конструировании таких шифров. Квадратичный криптоанализ является нелинейной модификацией известного метода линейного криптоанализа блочных шифров, предложенного М. Мацу и [101, 102] в 1993 году для шифров FEAL и DES и являющегося в настоящее время одним из наиболее эффективных.

Идея метода линейного криптоанализа заключается в следующем. Сначала для известного алгоритма шифрования определяется линейное соотношение L на биты открытого текста, шифротекста и ключа, выполняющееся с вероятностью р = 1/2 + е, достаточно сильно отличающейся от 1/2. Число е называется преобладанием соотношения L. Затем при фиксированном неизвестном ключе К криптоаналитиком собирается статистика из N пар {открытый текст — соответствующий шифротекст}, и на ее основе с учетом знака £ производится различение двух простых статистических гипотез: выполняется ли соотношение L для данного неизвестного ключа К или нет. В результате для битов ключа К устанавливается новое вероятностное соотношение. Для надежной работы этого метода мощность статистики N должна быть пропорциональна величине \е:\~2.

Общий подход к использованию в линейном криптоанализе нелинейных аппроксимаций предложили в 1996 году Л. Кнудсен и М. Робшау [90]. Основная его идея: обогатить класс аппроксимирующих функций нелинейными функциями и за счет этого повысить качество аппроксимации. Но при этом криптоаналитику придется столкнуться со следующими трудностями. Как эффективно выбрать хорошую нелинейную аппроксимацию? В линейном случае возможно решение такой задачи перебором всех 2т линейных функций (от т переменных). В общем случае полный перебор 22"1 булевых функций неосуществим даже при малых значениях т. Как объединить нелинейные аппроксимации отдельных раундов ? В целом метод нелинейного криптоанализа не получил пока должного развития.

В данной работе предлагается аппроксимировать булевы функции от т переменных г^,. ,ит функциями вида (и,7г(у))^, где 7Г — любая перестановка на т переменных, параметры и € Ъ™, к (1 ^ к ^ т/2) произвольны. Класс Ат всех таких аппроксимирующих функций может быть описан следующим образом. Пусть АНФ(/) — алгебраическая нормальная форма функции /; пусть АсЬ(/) — подмножество максимальной мощности множества {1,2,., т/2} такое, что для любых различных элементов из Асй(/) одночлены ^¿-1^-1, принадлежат множеству АНФ(/). Через р = р(/) обозначим любую перестановку т переменных такую, что [Ас1;(/Р)| = тах |А^(У7Г) |, где по определению

7г е£т

7Г(-) = /(тг(-)). Справедлива

Теорема 8. Булева функция / £ $т, степени не больше двух, такая что /(0) = 0, принадлежит классу Ат тогда и только тогда, когда / удовлетворяет условиям

1) для любых различных чисел г, j (1 ^ г, у ^ т/2) одночлены одновременно принадлежат / не принадлежат множеству АНФ(/^);

2) множество АНФ(/Р) не содержит одночлены вида ^21-1^21;

3) в точности одна из переменных ^¿-ъ у21 принадлежит АНФ(/7') для каждого элемента г € Act(/P).

Из теоремы 8 следует, что множество аппроксимирующих функций состоит из 2т (т. е. всех) линейных функций и не более чем 2m(1+log2 m) квадратичных функций, что не ограничивает криптоаналитика в возможности их полного перебора.

Выбор таких функций для аппроксимации обусловлен наличием простых формул для вычисления расстояния Хэмминга от произвольной булевой функции / до класса 21^,0 С71") функций (u, 7r(v))fc при фиксированных параметрах 7Г и к: dist(/, SftjOr)) = ¡Г"1 - i max wf\v), а также свойствами таких функций, близкими к линейным.

Исследования носят теоретический характер. Предложены модификации алгоритмов 1 и 2 линейного криптоанализа Мацуи [102] для расширенного класса аппроксимирующих функций. Приведены формулы для вычисления абсолютных значений преобладаний и надежности алгоритмов. Показано, что использование /с-бент-фуикций в качестве функций шифрования позволяет снижать максимальное абсолютное значение преобладания до его минимального значения, а следовательно максимально повышать стойкость шифра к данным квадратичным аппроксимациям.

Пусть F : Щ' х Z™key —> Щг — функция шифрования блочного шифра; Р, С и К — открытый текст, шифротекст и ключ соответственно. Пусть вещественное число е(К) — преобладание (при фиксированном ключе К) равенства

MP))i®(bMO)h = где a, b <Е d G Z™key, перестановки ir, с £ STflí т £ Sm^cy, целые числа i, j, к — некоторым образом выбранные параметры. Упомянутую выше роль fc-бент-функций в блочном шифре отражает следующее утверждение.

Теорема 9. Пусть фиксирован ключ К. Если вектор Ь, перестановки 7Г, а и параметр j, таковы что функция является (т!2)-бент-фунщией, то справедливо равенство max |e(iO|= min \е(К)\ = . fc,a,d,r i,fc,a,d,r

Приведены свойства аппроксимирующих функций (u, 7r(v))/c, которые могут быть использованы при согласовании нелинейных раундовых аппроксимаций в квадратичном криптоанализе. В заключение рассмотрены примеры четырехразрядных подстановок, рекомендованных для применения в узлах замены (S-блоках) алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с линейными) квадратичные соотношения специального вида на входные и выходные биты этих подстановок.

Результаты четвертой главы опубликованы в работах [150, 151, 153].

В пятой главе диссертации приводится доказательство Теоремы 1, формулировка которой дана в первой главе. Результаты главы опубликованы в работах [142, 143, 144].

По теме диссертации опубликовано 13 работ: 4 статьи в журналах, 9 работ в трудах и тезисах международных конференций; см. [141-153]. На web-странице www.math.nsc.ru/~tokareva все они доступны в электронном виде.

Результаты докладывались на российских и международных конференциях: Шестой молодежной научной школе по дискретной математике и ее приложениям в 2007 году в Москве, ISIT'2007 — IEEE Международном Симпозиуме по Теории Информации в Ницце (Франция), Шестой школе-семинаре SIBECRYPT',2007 — «Компьютерная безопасность и криптография» в Горно-Алтайске, международной конференции «Математика в современном мире» в Новосибирске в 2007 году, Четвертой международной конференции BFCA'2008 — «Булевы функции: криптография и приложения» в Копенгагене (Дания), Пятнадцатой международной конференции «Проблемы теоретической кибернетики» в Казани в 2008 году, SIBIRCON-2008 — IEEE Международной Конференции «Вычислительные Технологии в Электрической и Электронной Инженерии» в Новосибирске, Седьмой школе-семинаре SIBECRYPT'2008 — «Компьютерная безопасность и криптография» в Красноярске.

Результаты докладывались на семинарах «Дискретный анализ», «Теория кодирования», «Геометрия, топология и их приложения» и общеинститутском семинаре Института Математики СО РАН; научных семинарах

Института проблем передачи информации им. А. А. Харкевича в Москве; лаборатории информатики, сигналов и систем национального центра научных исследований (I3S CNRS) в Софии Антиполисе (Франция); кафедры защиты информации и криптографии Томского государственного университета. Результаты кандидатской диссертации отмечены премией школы «Компьютерная безопасность и криптография» — SIBECRYPT'2007 — в 2007 году. Работа выполнена при поддержке интеграционного проекта СО РАН N 35 «Древовидный каталог математических Интернет-ресурсов mathtree.ru», Российского фонда фундаментальных исследований (проекты 07-01-00248, 08-0Г-00671), гранта «Лучшие аспиранты РАН» за 2008 год Фонда содействия отечественной науке, гранта «NUGET» (Agence Nationale de la Recherche, France), совета научной молодежи ИМ СО РАН и Новосибирского государственного университета.

Заключение

В работе получены следующие результаты.

1. На множестве двоичных векторов длины m введены новые бинарные операции (u, v)j~, являющиеся аналогами скалярного произведения. Исследованы их свойства. Определены новые понятия к-нелинейности и к-преобразования Уолша—Адамара булевой функции.

2. Введено новое обобщение понятия бент-функции — к-бент-функ-ция, — отражающее возможность поэтапного усиления нелинейности булевой функции с ростом целого параметра к. Бент-функции и 1-бент-функ-ции совпадают. Доказано, что класс £-бент-функций строго вложен в класс ¿-бент-функций при к > t.

3. Предложены способы построения /г-бент-функций и исследованы их свойства. Доказано существование /с-бент-функций от m переменных любой степени нелинейности d, где 2 ^ d ^ тах{2, Щ — к + 1}.

4. Классифицированы /с-бент-функции от малого числа переменных.

5. Исследованы квадратичные аппроксимации вида (u,7r(v))fc, где v — вектор переменных; перестановка 7г, целое к и вектор и — параметры. Показано, что использование /с-бент-функций в качестве функций шифрования максимально повышает стойкость блочного шифра к таким аппроксимациям.

6. Рассмотрены четырехразрядные подстановки, рекомендованные для S-блоков алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с линейными) квадратичные приближения функциями вида (u, 7r(v))fc.

7. Отмечена аналогия между проблемами нижних—верхних оценок числа бент-функций и двоичных кодов, таких как совершенные и равномерно упакованные. Для числа равномерно упакованных двоичных кодов установлена новая (лучшая на данный момент) верхняя оценка.

Благодарности

Their eyes were bent on this work.1

Я искренне признательна своему научному руководителю Юрию Леонидовичу Васильеву (Институт математики им. С. JI. Соболева) за неизменную поддержку и постоянное внимание к данной работе.

Моя самая глубокая благодарность Александру Александровичу Нечаеву (Московский государственный университет) и Леониду Александровичу Вассалыго (Институт проблем передачи информации им. А. А. Харкевича, Москва), проявившим неподдельный интерес к моей работе и высказавшим немало ценных замечаний и критики.

Я очень благодарна сотрудникам института математики им. С. Л. Соболева: Денису Станиславовичу Кротову — за ценные замечания, позволившие существенно расширить множество кодов, для которых справедлива Теорема 1, и Владимиру Николаевичу Потапову, взявшему на себя труд прочитать рукопись и указавшему на целый ряд неточностей.

Мне очень приятно выразить признательность профессору Патрику Солё (Национальный Центр Научных Исследований — CNRS, — София Антиполис, Франция) за гостеприимство и увлекательную совместную работу в области бент-функций, благодаря которой удалось узнать много нового.

С большим удовольствием я благодарю Лилию Будагян (Университет Бергена, Норвегия) за консультации по векторным бент-функциям, внимательное прочтение текста и замечания, которые трудно переоценить.

Отдельную благодарность я приношу всем рецензентам печатных работ, обратившим мое внимание на многие существенные вопросы.

1 Игра слов: «Их взор был обращен к этой работе.» (англ.)

1. Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2, N 1. С. 4-6.

2. Амбросимов А. С. Свойства бент-функций дчзначной логики над конечными полями // Дискретная математика. 1994. Т. 6, N 3. С. 50-60.

3. Бассалыго Л. А., Зиновьев В. А., Зайцев Г. В. О равномерно упакованных кодах // Проблемы передачи информации. 1974. Т. 10, Вып. 1. С. 9-14.

4. Буряков М. Л., Логачев О. А. Об уровне аффинности булевых функций // Дискретная математика. 2005. Т. 17, N 4. С. 98-107.

5. Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. 1962. Вып. 8. С. 337-339.

6. Зиновьев В. А., Хеллесет Т. О весовых спектрах сдвигов кодов типа Геталса // Проблемы передачи информации. 2004. Т. 40, Вып. 2. С. 19-36.

7. Иванов А. В. Использование приведенного представления булевых функций при построении их нелинейных аппроксимаций // Вестник Томского госуниверситета. Приложение. 2007. N 23. С. 31-35.

8. Иванов А. В. Мономиальные приближения платовидных функций // Прикладная дискретная математика. 2008. Т. 1, N 1. С. 10-14.

9. Кротов Д. С. Z.i-линейные совершенные коды // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N 4. С. 78-90 (translated at http://arxiv.org/abs/0710.0198).

10. Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишков А. Б. Приближение булевых функций мономиальными // Дискретная математика. 2006. Т. 18, N 1. С. 9-29.

11. Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишкин В. А., Шишков А. Б. Бент-функции и гипербент-функции над полем из 21 элементов // Проблемы передачи информ. 2008. Т. 44, Вып. 1. С. 15-37.

12. Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18, N 3. С. 152-159.

13. Логачев О. А., Сальников А. А., Ященко В. В. Бент-функции на конечной абелевой группе // Дискретная математика. 1997. Т. 9, N 4. С. 3-20.

14. Логачев О. А., Сальников А. А., Ященко В. В. Криптографические свойства дискретных функций // Материалы конференции «Московский университет и развитие криптографии в России», МГУ, 2002. М.: МЦНМО, 2003. С. 174-199.

15. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: Московский центр непрерывного математического образования, 2004.

16. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М: Связь, 1979.

17. Молдовян А. А., Молдовян Н. А., Гуц Н. Д., Изотов Б. В. Криптография: скоростные шифры. СПб.: БХВ-Петербург, 2002.

18. Молдовян А. А., Молдовян Н. А., Еремеев М. А. Криптография: от примитивов к синтезу алгоритмов. СПб.: БХВ-Петербург, 2004.

19. Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1, N 4. С. 123-139.

20. Нечаев А. А., Хонольд Т. Полновесные модули и представления кодов // Проблемы передачи информ. 1999. Т. 35, Вып. 3. С. 18-39.

21. Ростовцев А., Маховенко Е. Введение в теорию итерированных шифров // СПб.: НПО «Мир и Семья», 2003.

22. Рязанов В. В., Чечета С. И. О приближении случайной булевой функции множеством квадратичных форм // Дискретная математика. 1995. Т. 7, N 3. С. 129-145.

23. Семаков Н. В., Зиновьев В. А., Зайцев Г. В. Равномерно упакованные коды // Проблемы передачи информации. 1971. Т. 7, Вып. 1. С. 38-50.

24. Сидельников В. М. О взаимной корреляции последовательностей // Проблемы кибернетики. 1971. Т. 24. С. 15-42.

25. Сидельников В. М. Об экстремальных многочленах, используемых при оценках мощности кода // Проблемы передачи информ. 1980. Т. 14, Вып. 3. С. 17-30.

26. Токарева Н. Н. Представление 24-лииейных кодов Препараты с помощью векторных полей // Проблемы передачи информации. 2005. Т. 41, Вып. 2. С. 50-62.

27. Шнайер В. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си // М.: Триумф, 2002.

28. Adams С. On immunity against Biham and Shamir's «differential cryptanalysis» // Information Processing Letters. 1992. V. 41. P. 77-80.

29. Agievich S. V. On the representation of bent-functions by bent-rectangles // Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics (Petrozavodsk, Russia. June 1-6, 2000). Proc. Boston: VSP, 2000. P. 121-135.

30. Avgustinovich S. V., Heden O., Solov'eva F. I. The classification of some perfect codes // Designs, Codes and Cryptography. 2004. V. 31, N 3. P. 313-318.

31. Bending T. D., Fon-Der-Flaass D. G. Crooked Functions, Bent Functions and Distance Regular Graphs // Electronic Journal of Combinatorics. 1998. N 5 (R34).

32. Bey Ch., Kyureghyan G. An Association Scheme of a Family of Cubic Bent Functions // Proc. of the Int. Workshop on Coding and Cryptography (Versailles, France. April 16-20, 2007). P. 13-19.

33. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V. 4, N 1. P. 3-72.

34. Borges J., Fernandez C., Phelps K. T. Quaternary Reed-Muller codes // IEEE Trans. Inform. Theory. 2005. V. 51, N 7. P. 2686-2691.

35. Borges J., Phelps K. T., Rifa J., Zinoviev V. A. On Z4-linear Preparata-like and Kerdock-like codes 11 IEEE Trans. Inform. Theory. 2003. V. 49, N 11. P. 2834-2843.

36. Borst J., Preneel B., Vandewalle J. Linear cryptanalysis of RC5 and RC6 // Fast Software Encryption, 6th International Workshop — FSE'99. (Rome, Italy. March 24-26, 1999) Proc. Berlin: Springer, 1999. P. 16-30 (Lecture Notes in Comput. Sei. V. 1636).

37. Bracken C., Leander G. New families of functions with differential uniformity of 4 // Proc. Fourth International Conference BFCA — Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). P. 190-194.

38. Budaghyan L., Carlet C., Leander G. On inequivalence between known power APN functions // Proc. Fourth International Conference BFCA — Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). P. 3-15.

39. Budaghyan L. Private communication, 2008.

40. Butty an L., Vajda I. Searching for the best linear approximation of DES-like cryptosystems // Electronics Letters. 1995. V. 31, N 11. P. 873-874.

41. Byrne E., McGuire G. On the non-existence of crookcd functions on finite fields // Proc. of the Int. Workshop on Coding and Cryptography (Bergen, Norway. March 14-18, 2005). P. 316-324.

42. Canteaut A., Carlet C., Charpin P., Fontaine C. On Cryptographic Properties of the Cosets of R{ 1, m) // IEEE Trans. Inform. Theory. 2001. V. 47, N 4. P. 1494-1513.

43. Canteaut A., Charpin P., Kuyreghyan G. A new class of monomial bent functions // Finite Fields and Applications. 2008. V. 14, N 1. P. 221-241.

44. Canteaut A., Daum M., Dobbertin H., Leander G. Finding nonnormal bent functions // Discrete Appl. Math. 2006. V. 154, N 2. P. 202-218.

45. Carlet C. Generalized Partial Spreads // IEEE Trans. Inform. Theory. 1995. V. 41, N 5. P. 1482-1487.

46. Carlet C. ^-linear codes // IEEE Trans. Inform. Theory. 1998. V. 44, N 4. P. 1543-1547.

47. Carlet C. Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications 11 IEEE Trans. Inform. Theory. 2008. V. 54, N 3. P. 1262-1272.

48. Carlet C., Charpin P., Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Designs, Codes and Cryptography. 1998. V. 15, N 2. P. 125-156.

49. Carlet C., Danielsen L.-E., Parker M. G.} Sole P. Self Dual Bent Functions // Proc. Fourth International Conference BFCA — Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). P. 39-52.

50. Carlet C., Ding C. Highly nonlinear mappings //J. Complexity. 2004. V. 20, N 2-3. P. 205-244.

51. Carlet C., Ding C. Nonlinearities of S-boxes // Finite Fields and Applications. 2007. V. 13, N 1. P. 121-135.

52. Carlet C.} Ding C., Niederreiter H. Authentication schemes from highly nonlinear functions // Designs, Codes and Cryptography. 2006. V. 40, N 1. P. 71-79.

53. Carlet G., Gaborit P. Hyper-bent functions and cyclic codes //J. Combin. Theory. Ser. A. 2006. V. 113, N 3. P. 466-482.

54. Gharnes C., Rotteler M., Beth T. Homogeneous bent functions, invariants, and designs // Designs, Codes and Cryptography. 2002. V. 26, N 1-3. P. 139-154.

55. Constantinescu I., Heise W., Honold T. Monomial extensions of isometries between codes over Zm /J Proc. of the Fifth International Workshop on Algebraic and Combinatorial Coding Theory — ACCT 1996 (Sozopol, Bulgaria. June 1-7, 1996) P. 98-104.

56. Delsarte P. An algebraic approach to the association schemes of coding theory // Ph. D. Thesis, Univ. Catholique'de Louvain, 1973.

57. Dillon J. F. A survey of bent functions // The NSA Technical J. 1972. Special Issue. P. 191-215.

58. Dillon J. F. Elementary Hadamard Difference sets // Ph. D. Thesis, Univ. of Maryland, 1974.

59. Dillon J. F., McGuire G. Near bent functions on a hyperplane // Finite Fields and Applications. 2008. V. 14. P. 715-720.

60. Dobbertin H. Almost perfect nonlinear power functions over GF(2n): the Niho case // Inform, and Comput. 1999. V. 151, N 1-2. P. 57-72.

61. Dobbertin H. Almost perfect nonlinear power functions over GF{2n): a new case for n divisible by 5 // Finite Fields and Applications FQ5 (Augsburg, Germany, 2000). Proc. Springer. Eds: D. Jungnickel, H. Niederreiter. P. 113-121.

62. Dobbertin H., Leander G. Cryptographer's Toolkit for Construction of 8-Bit Bent Functions // Cryptology ePrint Archive, Report 2005/089, available at http: //eprint. iacr. org/.

63. Fedorova M., Tarannikov Yu. On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Spectral Matrices // INDOCRYPT 2001. P. 254-266 (Lecture Notes in Comput. Sei. V. 2247).

64. Goethals J. M., Van Tilborg H. G. A. Uniformly packed codes // Philips Res. Repts. 1975. V. 30. P. 9-36.

65. Hammons A. R., Kumar P. V., Calderbank A. R., Sloane N. J. A., Sole P. The Z4-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inform. Theory. 1994. V. 40, N 2. P. 301-319.

66. Heys H. M., Tavares S. E. Substitution-Permutation Networks Resistant to Differential and Linear Cryptanalysis // J. Cryptology. 1996. V. 9, N 1. P. 1-19.

67. Kantor W. M. Codes, Quadratic Forms and Finite Geometries // Proceedings of Symposia in Applied Math. 1995. V. 50. P. 153-177.

68. Kavut S., Maitra S., Yucel M. D. Search for Boolean functions with excellent profiles in the rotation symmetric class // IEEE Trans. Inform. Theory. 2007. V. 53, N 5. P. 1743-1751.

69. Kerdock A. M. A class of low-rate non-linear binary codes // Inform. Control. 1972. V. 20, N 2. P. 182-187.

70. Kim K., Park S., Lee S. Reconstruction of s2DES S-Boxes and their Immunity to Differential Cryptanalysis // Korea — Japan Workshop on Information Security and Cryptography. (Seoul, Korea. October 24-26, 1993) Proc. 1993. P. 282-291. ' .

71. Knudsen L. Practically secure Feistel ciphers // Fast Software Encryption — FSE, The Cambridge Security Workshop. (Cambridge, U.K. December 9-11, 1993) Proc. Springer-Verlag. 1994. P. 211-221 (Lecture Notes in Comput. Sei. V. 809).

72. Krotov D. S. Z4-linear Hadamard and extended perfect codes // Proc. of the Int. Workshop on Coding and Cryptography (Paris, France. January 8-12, 2001). P. 329-334.

73. Krotov D. S., Avgustinovich S. V. On the Number of 1-Perfect Binary Codes: A Lower Bound // IEEE Trans. Inform. Theory. 2008. V. 54, N 4. P. 1760-1765.

74. Kumar P. V., Scholtz R. A., Welch L. R. Generalized bent functions and their properties // J. Combin. Theory. Ser. A. 1985. V. 40, N 1. P. 90-107.

75. Langevin P., Leander G. Monomial bent functions and Stickelberger's theorem // Finite Fields and Applications. 2008. V. 14. P. 727-742.

76. Langevin P., Leander G., McGuire G. Kasami Bent Functions are Not Equivalent to Their Duals // submitted, 2007.

77. Leander N. G. Monomial bent functions // IEEE Trans. Inform. Theory. 2006. V. 52, N 2. P. 738-743.

78. Leander N. G., Langevin P. On exponents with highly divisible Fourier coefficients and conjectures of Niho and Dobbertin //to appear. 2008.

79. Maitra S., Sarkar P. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables // IEEE Trans. Inform. Theory. 2002. V. 48, N 9. P. 2626-2630.

80. Mansoori S. D., Bizaki H. K. On the vulnerability of simplified AES algorithm against linear cryptanalysis // Internat. J. of Computer Science and Network Security. 2007. V. 7, N 7. P. 257-263.

81. McFarland R. L. A family of difference sets in non-cyclic groups //J. Combin. Theory. Ser. A. 1973. V. 15, N 1. P. 1-10.

82. Meng Q., Yang M. C., Zhang H. A novel algorithm enumerating bent functions // Available at http: //eprint. iacr. org, 2004/274.

83. Meng Q., Zhang H., Yang M. C., Cut J. On the degree of homogeneous bent functions // Available at http://eprint.iacr .org, 2004/284.

84. Meng Q., Zhang H., Yang M. C., Cui J. On the degree of homogeneous bent functions // Discrete Applied Mathematics, 2007. V. 155, N 5. P. 665-669.

85. Nakahara J. Jr. A Linear Analysis of Blowfish and Khufu // Information Security Practice and Experience — ISPEC 2007. Third International Conference (Hong Kong, China. May 7-9, 2007). Proc. 2007. P. 20-32 (Lecture Notes in Comput. Sci. V. 4464).

86. Nakahara J., Preneel B., Vandewalle J. Experimental Non-Linear Cryptanalysis // COSIC Internal Report. Katholieke Universiteit Leuven. 2003. 17 p.

87. Nyberg K. New bent mappings suitable for fast implementation // Fast software encryption'93 (Cambridge, December 9-11, 1993). Proc. Berlin: Springer, 1994. P. 179-184 (Lecture Notes in Comput. Sci. V. 809).

88. Olsen J. D., Scholtz R. A., Welch L. R. Bent-function sequences // IEEE Trans. Inform. Theory. 1982. V. 28, N 6. P. 858-864.

89. Parker M. G. The constabent properties of Golay-Davis-Jedwab sequences // IEEE International Symposium on Information Theory — ISIT'2000. (Sorrento, Italy. June 25-30, 2000). Proc. 2000. P. 302.

90. Preneel B. Analysis and design of cryptographic hash functions // Ph. D. thesis, Katholieke Universiteit Leuven, 3001 Leuven, Belgium. 1993.

91. Qu C., Seberry J., Pieprzyk J. Homogeneous bent functions // Discrete Appl. Math. 2000. V. 102, N 1-2. P. 133-139.

92. Riera C., Parker M.G. Generalised Bent Criteria for Boolean Functions (I) // IEEE Trans. Inform. Theory 2006. V. 52, N 9. P. 4142-4159.

93. Rifa J., Zinoviev V. A. On completely regular codes from perfect codes // ACCT 2006 — Tenth Int. Workshop «Algebraic and Combinatorial Coding Theory» (Zvenigorod, Russia. September, 3-9, 2006). Proc. 2006. P. 225229.

94. Rodier F. Asymptotic nonlinearity of Boolean functions // Designs, Codes and Cryptography. 2006. V. 40, N 1. P. 59-70.

95. Rothaus O. On bent functions //J. Combin. Theory. Ser. A. 1976. V. 20, N 3. P. 300-305.

96. Schmidt K-U. Quaternary Constant-Amplitude Codes for Multicode CDMA // Available at http://arxiv.org/abs/cs.IT/0611162.

97. Sdg.uk A. A. On Probability of Success in Linear and Differential Cryptanalysis // J. Cryptology. 2008. V. 21. N. 1. P. 131-147.

98. Shorin V.V., Jelezniakov V.V. Gabidulin E.M. Linear and Differential Cryptanalysis of Russian GOST // Electronic Notes in Discrete Mathematics, V. 6. April 2001. P. 538-547.

99. Siegentaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Trans. Inform. Theory. 1984. V. IT-30, N 5. P. 776-780.

100. Solé P. Private communication, 2008.

101. Tarannikov Yu. On some connections between codes and cryptographic properties of Boolean functions // Seventh Int. Workshop «Algebraic and Combinatorial Coding Theory» (Bansko, Bulgaria. June 18-24, 2000). Proc. 2000. P. 299-304.

102. Xia T., Seberry J., Pieprzyk J., Chames C. Homogeneous bent functions of degree n in 2n variables do not exist for n > 3 // Discrete Applied Mathematics. 2004. V. 142, N 1-3. P. 127-132.

103. Youssef A. M. Generalized hyper-bent functions over GF(p) // Discrete Applied Math. 2007. V. 155, N 8. P. 1066-1070.

104. Zhang В., Lu 5. I/O correlation properties of bent functions // Science in China Series E: Technological Sciences. 2000. V. 43, N 3. P. 282-286.

105. Zhe-Xian Wan. Quaternary codes. Singapore: World Scientific Publishing Co. Pte. Ltd, 1997.

106. Zheng Y., Zhang X.-M. On Plateaued Functions // IEEE Trans. Inform. Theory. 2001. V. 47, N 3. P. 1215-1223.

107. Публикации автора по теме диссертации (доступны по адресу www. math. nsc. ru/~tokareva)

108. Токарева H. H. Иерархия классов бент-функций кратной нелинейности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16-21 апреля, 2007) Часть III, 2007. С. 5-11.

109. Токарева Н. Н. О верхней оценке числа равномерно упакованных двоичных кодов // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16-21 апреля, 2007) Часть III, 2007. С. 11-16.

110. Tokareva N. N. An Upper Bound for the Number of Uniformly Packed Codes // IEEE International Symposium on Information Theory — ISIT'2007. (Nice, France. June 24-29, 2007). Proc. 2007. P. 346-350.

111. Токарева H. H. О верхней оценке числа равномерно упакованных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14, N 3. С. 90-97.

112. Tokareva N. N. On fc-bent functions // Вестник Томского госуниверситета. Приложение. 2007. N 23. С. 74-76.

113. Токарева Н. Я. Бент-функции кратной нелинейности: /с-бент-функции // Материалы российской конференции «Математика в современном мире» (Новосибирск, Россия. 17-21 сентября, 2007). С. 288289.

114. Токарева Н. Н. Бент-функции с более сильными свойствами нелинейности: fc-бент-функции // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14, N 4. С. 76-102.

115. Tokareva N. N. fc-Bent functions and quadratic approximations in block ciphers // Proc. Fourth International Conference BFCA — Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). P. 132-148.

116. Токарева H. H. ^-Преобразование Уолша-Адамара в теории кодирования и криптографии // Материалы XV Международной конференции «Проблемы теоретической кибернетики» (Казань, Россия, 2-7 июня, 2008). С. 113-114.

117. Tokareva N. N. fc-Bent Functions: from Coding Theory to Cryptology // Proc. First IEEE International Conference SIBIRCON — Computational Technologies in Electrical and Electronics Engineering (Novosibirsk, Russia, July 21-25, 2008). P. 36-40.

118. Токарева H. H. О квадратичных аппроксимациях в блочных шифрах // Пробл. передачи информ. 2008. Т. 44, Вып. 3. С. 105-127.

119. Токарева Н. Н. Описание &-бент-функций от четырех переменных // Дискр. анализ и исслед. операций. 2008. Т. 15, N 4. С. 74-83.

120. АВ function, 34 APN function, 34

121. CDMA standard, 8, 27 crooked function, 351. DES, 86

122. Хэмминга, 19 весовой спектр кода, 93гипер-бент-функция, 30 гипотеза Доббертина, 35дифференциально ¿-равномерная функция, 34класс аппроксимирующих функций, 71кодлинейный, 11, 37 Адамара, 6 БЧХ, 35, 98

123. Геталса, 98 Кердока, 7 Препараты, 35, 98 Рида—Маллера, б, 7 равномерно упакованный, 25, 91 совершенный, 24, 97 типа Адамара, 11 конструкция

124. Мэйорана—МакФарланда, 22 степенная, 23частичных разветвлений, 22 корреляционно-иммунная функция, 35' коэффициенты Уолша—Адамара, 20 криптоанализдифференциальный, 8 квадратичный, 70 линейный, 8, 67 нелинейный, 69 критерий

125. Ротхауса, 21 распространения, 2838ортогональное разветвление, 7 отображение Р, 36 7, 36 <Рк, 38