WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |
РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

На правах рукописи

УДК 519.1, 519.7 ТОКАРЕВА Наталья Николаевна СИЛЬНО НЕЛИНЕЙНЫЕ БУЛЕВЫ ФУНКЦИИ:

БЕНТ-ФУНКЦИИ И ИХ ОБОБЩЕНИЯ специальность 01.01.09 – дискретная математика и математическая кибернетика

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

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

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

Научный консультант: кандидат физ.-мат. наук, Ю. Л. Васильев.

Официальные оппоненты: доктор физ.-мат. наук, Е. А. Окольнишникова, кандидат физ.-мат. наук, Ю. В. Таранников.

Ведущая организация: Томский государственный университет

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

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

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

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

Bent functions deserve our bent to study them...1

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

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

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

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

Пусть u = (u1,..., um), v = (v1,..., vm) двоичные векторы длины m. Обозначим через u, v их скалярное произведение по модулю 2, u, v = u1v1... umvm, где означает сложение над Z2. Булевой функцией от m переменных называется произвольная функция из Zm в Z2. Булева функция f от переменных v1,..., vm называется аффинной, если она имеет вид f(v) = u, v a для некоторого вектора u Zm и константы a Z2. Расстоянием Хэмминга между векторами u, v называется число координат, в Игра слов: Бент-функции заслуживают нашего стремления изучить их... (англ.) В литературе встречается также термин совершенно нелинейные функции.

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

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

Преобразованием Уолша Адамара булевой функции f от m переменных называется целочисленная функция Wf, заданная на множестве Zm двоичных векторов длины m равенством Wf(v) = (-1) u,v f(u).

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

(Wf(v))2 = 22m.

vZm Поскольку число всех коэффициентов равно 2m, из равенства следует, что максимум модуля коэффициента Уолша Адамара не может быть меньше величины 2m/2. Заметим, что расстояние ХэмминАнглийское слово bent очень многозначно; среди его значений: изогнутый, кривой, натяжение, напряженное состояние, призвание, а еще и соцветие подорожника.

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

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

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

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

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

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

Классическая комбинаторная задача построения матриц Адамара порядка n, известная с 1893 года, в случае n = 2m (m четно) при некоторых ограничениях сводится к задаче построения бентфункций от 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-значные бентфункции, обобщенные булевы бент-функции, полу-бент-функции, ненормальные бент-функции, бент-функции на конечной абелевой группе, однородные бент-функции, гипер-бент-функции, Z-бентфункции, нега-бент-функции и др. С одной стороны эти исследования мотивированы высокой сложностью задачи описания бентфункций и являются попытками перехода к более общим (или более частным) ее постановкам в надежде на частичное решение основной проблемы. С другой стороны интерес к обобщениям постоянно стимулируется новыми запросами со стороны приложений.

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

Однако, любой обзор в этой области очень быстро устаревает и a priori неполон.

Цель работы предложить новое обобщение бент-функций k-бент-функции, отражающее возможность поэтапного усиления (с ростом целого параметра k) нелинейных свойств булевой функции. Основная идея обобщения заключается в том, что принадлежность функции f классу бент-функций не исключает того, что f может оказаться достаточно хорошо аппроксимируемой функциями, являющимися нелинейными, но обладающими свойством линейности в другом смысле. Опираясь на недавние результаты теории кодирования, связанные с исследованием альтернативной линейности кодов, мы выделим m/2 различных типов линейности булевой функции от m переменных, схожих с обычной линейностью.

Для этого построим специальную серию из m/2 кодов типа Адамара, на каждом из которых возможно определение групповой операции, согласованной с метрикой Хэмминга. Кодовые слова этих кодов есть векторы значений булевых функций вида u, v a, k где операция ·, · для каждого k, 1 k m/2, является анаk логом скалярного произведения векторов. Булеву функцию назовем k-бент-функцией, 1 k m/2, если она максимально нелинейна при k различных типах линейности одновременно. В таком определении 1-бент-функции совпадают с обычными бент-функциями, т. е. линейность номер 1 есть линейность в обычном смысле, а (m/2)-бент-функции могут считаться наиболее нелинейными в данной иерархии. Цель работы исследовать свойства k-бентфункций, привести способы их построения, классифицировать такие функции от малого числа переменных и рассмотреть возможные приложения k-бент-функций в криптографии. А именно, исследовать возможность квадратичного криптоанализа блочных шифров на основе квадратичных аппроксимаций специального вида и показать, что использование k-бент-функций в качестве функций шифрования максимально повышает стойкость шифра к данным квадратичным аппроксимациям.

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

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»