автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:О построении и оценках характеристик корреляционно-иммунных булевых функций и смежных комбинаторных объектов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

На нравах рукописи 005006119 С^^Х

Халявин Андрей Вячеславович

О построении и оценках характеристик корреляционно-иммунных булевых функций и смежных комбинаторных объектов

Специальность 0-5.13.19.......методы и системы защиты информации,

информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 ДЕК 2011

Москва 2011

005006119

Работа выполнена на Механико-математическом факультете Московского государственного университета имени М. В. Ломоносова.

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

кандидат физико-математических наук, доцент Таранников Юрий Валерьевич.

Официальные оппоненты: доктор физико-математических наук

Че.ремцшхин Александр Васильевич;

кандидат физико-математических наук Кузнецов Юрий Владимирович.

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

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

Защита состоится 28 декабря 2011 г. в 10 час. 45 мин. па заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, Московский государственный университет имени М. В. Ломоносова, Мехаиико-математичсский факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Автореферат разослан 28 ноября 2011 г.

Ученый секретарь диссертационного совета,

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

А. А. Корнев

Общая характеристика работы

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

Криптографическая стойкость определяется вычислительной сложностью наиболее быстрого известного алгоритма ее вскрытия. Адекватность оценки криптографической стойкости определяется наличием большого числа попыток анализа алгоритма шифрования, что в немалой степени зависит от его простоты и распространенности на практике. Последнее же напрямую связано со скоростью и удобством использования алгоритма. По этой причине создание новых шифров является непростой задачей, в которой нужно учитывать сложную взаимосвязь различных факторов. Для решения этой задачи создаются открытые международные конкурсы, призванные найти и стандартизировать наилучшие алгоритмы1,2.

Большим классом быстрых алгоритмов, которые используются как сами по себе, так и в качестве примитивов (например s-боксов или рауидовых преобразований) для более сложных шифров с секретным ключом являются комбинирующие и фильтрующие генераторы. Они преобразуют с помощью некоторой нелинейной булевой функции / выходы регистров сдвига с линейными обратными связями (Linear feedback shift register, LFSR) в шифрующую последовательность. Комбинирующие генераторы подают на входы функции / выходы нескольких LFSR, а фильтрующие генераторы подают па входы / последовательные выходы одного LFSR. Ключом этих систем являются начальные состояния регистров. Анализ этих алгоритмов естественно приводит к необходимости изучения и решения систем булевых уравнений, которые связывают элементы неизвестного ключа с известными данными.

1 Конкурс «STREAM (the. ECR.YPT Stream Cipher Project) прнэтан собрат, новые перспективные потоковые шифры.

5NIST проводит конкурс па нопый государственный стандарт хэширования SHA-3.

Несмотря па то, что общая задача решения системы нелинейных булевых уравнений является МР-трудной, разработано большое число статистических, теоретико-вероятностных, теоретико-кодовых, алгебраических и иных подходов, которые позволяют решить задачу быстрее чем за 0(2") в конкретных частных случаях. Поэтому анализ конкретных систем уравнений является важной и нетривиальной научной задачей. Отсюда следует, что функцию / нельзя выбирать произвольным способом. Например, корреляционная атака накладывает требование высокой корреляционной иммунности, а методы линеаризации накладывают требования высокой нелинейности. Как следствие, возникает естественное желание построить функции, обладающие как можно более лучшими значениями криптографических характеристик и, как следствие, наилучшим образом сопротивляющиеся известным методам криптоанализа. Разумеется, оптимальные значения всех характеристик не могут достигаться одновременно, поэтому при разработке стойких систем шифрования приходится решать трудную многокритериальную оптимизационную задачу выбора булевой фукции /. В связи с актуальностью этой задачи, имеется множество работ, устанавливающих или уточняющих соотношения между разными криптографическими параметрами.

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

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

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

лучены точные нижние оценки на размер ортогональных массивов большой силы.

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

На защиту выносятся следующие основные результаты диссертации:

- Доказана нижняя оценка на количество элементов ортогонального массива, если его сила не меньше где п — число его факторов.

- Найден новый детермепнровапиый метод построения З-устойчивых булевых функций от 9 переменных с наибольшей возможной нелинейностью 240. Полученные функции обладают симметрией 7 порядка, в то время как ранее известные подходы использовали эвристики и выдавали функции без какой-либо симметрии.

- Впервые построены булевы функции от 9 переменных корреляционно-иммунные 4 порядка с наибольшей возможной нелинейностью 240. С их помощью получены функции от 10 переменных, корреляционно-иммунные 5 порядка с наибольшей возможной нелинейностью 480.

- Показано, что верхняя граница нелинейности п/(/) < 2"-1 - 2т для корреляционно-иммунных функций порядка 0 < т < п — 1 от п переменных может достигаться только при п = 2*+1 + 1, т = 2я и п = 2,+1 + 2, т = 2* + 1, где s>Q,seZ.

Основные методы исследования. Для построения булевых функций используются свойства коэффициентом Уолша, метод "шееНн-ИкмшскПе" и его обобщения. Кроме того, в случае З-устойчивых функций используется симметрия 7 порядка, а в случае корреляционно-иммунных функций 4 порядка используется решение систем линейных уравнений, связывающих значения булевой функции и коэффициентов Уолша, Нижняя оценка на количество элементов ортогонального массива доказывается с номощыо теоремы Титсворта. Верхняя граница нелинейности доказывается с помощью сочетания асимптотических оценок биномиальных коэффициентов и свойств их делимости на степени двойки.

Апробация результатов. Результаты диссертации докладывались на X Международном семинаре «Дискретная математика и ее приложения» в Москве (2010), Седьмой общероссийской научной конференции «Математика и безопасность информационных технологий» и Москве (МаБИТ-2008), конференции NATO Information and Communicatioii Security в Звенигороде (2007) и на семинарах кафедры дискретной математики механико-математического факультета МГУ (2007-2010).

Публикации по теме диссертации. По теме диссертации опубликовано 5 работ [1-5], две из которых — в печатном издании из перечня ВАК [1,2].

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

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

Краткое содержание диссертации

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

В первой главе рассматриваются булевы функции с большим порядком корреляционной иммунности. В разделе 1.1 вводятся основные определения. В разделе 1.2 обсуждается вопрос связи корреляционной иммунности и устойчивости. Известно3, что если порядок корреляционной иммунности m не меньше то булева функция является уравновешенной, а следовательно m-устойчивой. В разделе 1.2 приводится известный пример функции с m = [Цр], для которой это утверденне не верно, поэтому эта оценка является точной.

Раздел 1.3 посвящен обобщению этого результата па ортогональные массивы. Ортогональным массивом с N строками, п факторами над алфавитом из з символов силы т называется таблица N х п с элементами из алфавита, в которой при выборе любых т столбцов, любая из s'" комбинаций символов в этих столбцах встречается среди строк одинаковое число раз.

3F(m-D(.T-Fln;is.s D.C., А Ьоиш! on condufion immuriity. Siberian Electronic Mathematiatl Reports (http://semr.math.nsc.ni), V. 4, 2007, pp. 133 135.

Для ортогональных массивов принято краткое обозначение ОА(М, п, з, то). Если все строки массива различны, то он называется простым. Поскольку любому простому ортогональному массиву силы т можно сопоставить корреляционно-иммунную функцию порядка то, то из этого свойства булевых функций немедленно получается нижняя оценка 2""1 мощности простого ортогонального массива. В разделе 1.3 эта оценка обобщается на общий случай не обязательно простых ортогональных массивов. Более того показывается, что если оценка мощности достигается, то ортогональный массив является простым.

Теорема 1 Еслит > 2" ^, то дм ОА{М, п,2,т) выполнено N > 2"-1.

о

А если при этом N — 2п~1, то ортогональный массив является простым.

Доказательство основано на представлении ортогонального массива как целочисленной функции х„ = 2па - 1 па булевом кубе, где па равно количеству наборов а в ортогональном массиве. Величина ха может принимать лишь значения —1,1,3,... Если ортогональный массив является простым, то ха = ±1, что соответствует булевой функции. Для целочисленной функции хп можно ввести коэффициенты Уолша аналогично булевым функциям: \Ув = Для ортогональных массивов силы то выполнено \Уц = 0 при 1 < |/3| < то.

Коэффициенты Уолша для функции х\ вычисляются как свертка XV$ с самим собой. Поскольку сумма над двух векторов веса больше то не может быть вектором веса больше то, то для коэффициентов Уолша функции х\ веса больше т большинство попарных произведений в свертке равны О и для них можно получить простое выражение Этого оказывается

достаточно для вычисления нулевого коэффициента Уолша функции и получения равенства

£>»-*.) = 5(ЗФо-|Г<-2"), (1)

а

Где ф0 = £ Исходя из того, что левая часть не отрицательна, удастся получить требуемую оценку на И-'о = 2ЛГ - 2" и, как следствие, размер ортогонального массива. В случае N = 2"~' правая часть (1) равна 0 благодаря И'о = 0. Поэтому в этом случае все слагаемые в левой части равны 0, откуда следует простота ортогонального массива.

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

она поддается линейному криптоанализу. Поэтому возникает вопрос о максимальной возможной нелинейности m-устойчивой булевой функции. Из равенства Парсеваля следует ограничение nl{f) < 2"-1 — 2"/2-1 на нелинейность любых булевых функций. При та > п/2 — 2 это неравенство было усилено до nl(f) < 2"-1 — 2"'+1 за счет делимости коэффициентов Уол-ша m-устойчивых булевых функций тремя группами авторов4'5'''. Отсюда возникает вопрос, о достижимости этой оценки. Функции, на которых эта оценка достигается, мы будем называть экстремальными. У экстремальных функций коэффициенты Уолша принимают значения {О, ±2Ш+2}. Это свойство оказывается интересным само по себе. Функции, у которых коэффициенты Уолша принимают значения {0, ±2,;} для некоторого к, называют плагпоаиднылш.

В разделе 2.1 приводится актуальное состояние проблемы построения экстремальных функций. Наилучшие теоретические результаты получены с помощью рекурсивных конструкций7 экстремальных функций для п — 2 > т > О.бп — 1, а доведение этих конструкций до совершенства8 позволяет получить экстремальные функции с параметрами п — 2 > т > ь„ (,/5+i)n + 0(log2«) (это немного лучше: log — 0.5902...). Как видим, основную сложность представляют случаи т близких к п/2. Последующие разделы второй главы посвящены построению функции для случая п — 9, т = 3, который долгое время оставался открытым. Эти функции уже были получены9'10 с помощью эвристического поиска, но в данной диссертации приводится совершенно новый способ их построения. Рассматриваются только булевые функции, симметричные относительно циклических перестановок

4Sarkar P.. Mait.ra S. Nonlinearity bounds nnd constructions of resilient boolean functions // In Advanced in Cryptoiogy: Eurocrypt 21)00, Lecture Notes in Computer Science. - V. 1S80. - 2000. - P. 515-532.

sTarannikov Yu. On resilient Boolean functions with maximal possible nonlinearity // Cryptoiogy ePrint archive (http://eprillt.iacr.org/), Deport 2000/005, March 2000, 18pp.

6Zhong Y., Zhang X. M. Improved upper bound on the nonlinearity of high order correlation immune functions // Selected Ares in Cryptography, 7th Annual International Workshop, SAC2000, Lecture Notes in Computer Science.......V. 2012. - P. 264 -274. — Springer-'Verlag, 2001.

7Tarannikov Yu. New constructions of resilient Boolean functions with maximal nonlinearity, Preproceedings of 8th Fast Software Encryption Workshop, Yokohama, Ларап, April 2-4, 2001, pp.70-81, also available at Cryptoiogy ePrint archive (http://eprint.iacr.org/). Report 2000/060. December 2000. 11pp.

8Fedorova M.. Tararmikov Yu. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices. // Progress in Cryptoiogy — Indocrypt 2001, Chennai, India, December 16-20, 2001, Proceedings, Springer-Verlag, 2001, Lecture Notes In Computer Science, V. 2247, pp. 254-266. Статья также доступна на Cryptoiogy ePrint archive (http://eprint.iacr.org/2001/083), Report 2001/083, 16 pp.

"Saber Z.,Faisal Udilin M., Youssef A. On the existence of (9, 3, 5, 240) resilient functions. IEEE TVansactions on Information Theory, 52(5):22G9-2270, May 2006.

10Kavut S., YucelM., MaitraS. Construction of resilient functions by the concatenation of boolean functions having nonintersecting Walsh spectra. In Third Internation Workshop on Boolean Functions: Cryptography and Applications, BFCA 07, May 2-3. 2007, Pairs, Ftancc.

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

В разделе 2.2 преобразование Уолша записывается с учетом симметрии рассматриваемых функций. Обозначим с^..., eso классы эквивалентности булевых наборов длины 9 при циклических перестановках первых 7 координат. Коэффициенты Уолша на наборах из одного класса эквивалентности равны друг другу. Сопоставим функции / столбец v, в котором в позиции г стоит 1, если }{х) = 0,ж £ с,-, и -1, если f(x) = \,х G c¡. Коэффициенты Уолша запишем в столбец w, в котором на i-й позиции стоит число Wf(u), и 6 С{. Тогда V) — Av, где матрица А имеет коэффициенты

ау = Х)(-1)<и#>.

xecj

где и 6 Построенная матрица А обладает важным свойством.

Теорема 2 Пусть с,- « с/ — классы эквивалентности, у представителей которых восьмой бит установлен в 0. A c¡> и Су ....... классы эквивалентности. полученные из c¡ и cj установкой восьмого бита в 1. Тогда «у = a¡'j = Oif = ~ai'j'-

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

(в ^В )' Соответственно вектора значений функций и коэффициентов

Уолша можно так же разбить па две части: щ = Bvo+Bvi и wi = Bvq—Bvi. Из З-устойчивости следует, что координаты w¿ делятся на 32, откуда выводится, что координаты Вщ н Вщ делятся на 16. Нахождение всех v¡ таких, что Bví делится на 16 выполняется с помощью дальнейшего деления вектора гц и матрицы В на две части: Bv¡ = CoV«,+CiVn ■ Далее перебираются все 220 вариантов для v¡j и сортируются по остаткам от деления на 16 вектора CjVij. Дальнейшее нахождение подходящих пар v¡0, vn может быть выполнено за линейное время. Остается найти подходящие пары Иц и v\. В разделе 2.3 показывается, что если пара таких векторов дает нужную булеву функцию, то остатки Вщ и Bv¡ по модулю 32 совпадают и у этих векторов не найдется ни одной общей координаты со значением ±32. Первое условие позволяет разбить вектора i>¡ на группы в зависимости от остатка Вщ по модулю 32 и проверять только пары векторов из одной группы. Алгорит-

мы сокращения перебора за счет второго условия приведены в следующем разделе.

Сопоставим вектору щ маску, в которой единичка стоит на позициях, где координата Вгц равна ±32. Получаем, что маски векторов v0 и t'i ие должны пересекаться. В разделе 2.4 решается общая задача о поиске не пересекающихся масок. Время работы предложенных алгоритмов оценивается в предположении, что маски имеют равномерные и независимые в совокупности распределения. Первый алгоритм использует разбиение масок по одному биту.

Теорема 3 Обозначим к = п2 — среднее число пар непересекающихся битовых масок. Тогда существует алгоритм их нахождения, среднее время работы которого равно 0(па 4- к) при п оо, где о = log2(l + У3) = 1.388..., tp= 1.618... .......золотое сечение.

Второй алгоритм использует отделение в отдельные группы масок, у которых s битов все равны 0 или все равны 1.

Теорема 4 Для любого s существует алгоритм нахождения всех пар непересекающихся масок, который работает в среднем (предполагая, что все маски равновероятны) за 0(па + n2ß^') действий, где ß = 1 — 2 • 2~" +

3 • 2~2", а = 1 + 1/s, |Л| < п, \В\ < п.

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

Теорема 5 Существуют булевы функции от п = 9 + Зг переменных устойчивые порядка т = 3 4- 2г с нелинейностью 2",_| — 2m+1 при i > 0.

В третьей главе исследуется максимальная возможная нелинейность корреляциоиио-иммунных функций. В разделе 3.1 приводится оценка их нелинейности nl(f) < 2"-1 — 2'". Если эта оценка при некоторых п и т не достигается, то выполнено nl(f) < 2"_1 — 2",+1, что совпадает с оценкой нелинейности m-устойчивых функций. Поэтому случай nl(f) — 2n_1 — 2m,

! 'Pasalic Е., Maitra S-, Johansson Т., Sarkar P. New constructions of resilient and correlation immune boolean functions achieving upper bounds on nonlinearity, Workshop on Coding and Cryptography - YVCC 2001, Paris, January 8-12, 2001, Electronic Notes in Discrete Mathematics, Volume C, Elsevier Science, 2001.

при котором эти оценки различаются, представляет особый интерес. Функции с такими параметрами будем также называть экстремальными. Последующие разделы посвящены решению открытой проблемы построения корреляционно-иммунной функции с параметрами п = 9, m = 4, nl(f) = 28 - 24 = 240.

В разделе 3.2 изучаются коэффициенты Уолша этих экстремальных функций. Показывается, что W/(u) = 0 для векторов и веса 1,2,3,4 и 9. Остальные коэффициенты Уолша равны ±32, при этом их значения определяются знаками коэффициентов Уолша на векторах веса 0 и 5.

В разделе 3.3 приводится алгоритм перебора знаков ненулевых коэффициентов Уолша. Все коэффициенты разбиваются на 4 части в зависимости от значений двух последних битов: Woo, Woi, Ww, W\\. Для каждой из частей можно вычислить соответствующие обратные преобразования Уолша Foo. Foi, Fio, -Ри- Эти обратные преобразования нормированы так, чтобы F(x,i,j) = Т,а,ьРаь{х){-1)а^ = ±16, где 16 соответствует нулевым значениям функции /, а —16 — единичным. В таком случае координаты Fai> должны принадлежать множеству (0, ±8, ±16}.

Перебор части Won может быть значительно сокращен за счет симметрии множества экстремальных функций. Эти симметрии порождаются преобразованиями четырех типов. Первый тип смена знаков у всех коэффициентов Уолша или переход от функции к ее отрицанию. Второй тип — смена знаков у всех коэффициентов Уолша с установленным t-м битом или сдвиг функции вдоль ¿-го аргумента. Третий тип — перестановка коэффициентов Уолша, порожденная перестановкой аргументов функции. Четвертый тип — преобразование

IV'(«1,.. •, щ) = W(m ф in, щ ©«i,..., Щ,..., щ © и{).

Использование этих симметрия позволяет сократить перебор комбинаций знаков в Who н свести все возможные подходящие варианты к 5 комбинациям.

Сдвиг функции вдоль 8-го и 9-го аргументов позволяет сократить перебор знаков в Woi и Wjо вдвое. Кроме того, показывается, что из этих вариантов можно исключить все случаи, где Foo и Foi имеют различные остатки от деления на 16 или имеют общие координаты со значениями ±16. Полный перебор показывает, что количество подходящих вариантов для И'ш и Wio заключено от 10 до 16 миллионов для каждой из 5 комбинаций Woo.

Наконец, перебор последней части Wu выполняется с помощью решения

системы линейных уравнений. Для каждого из вариантов W«), Ví'oi и Ww есть около 90 координат Fu (ж), которые однозначно определяются из условия F(x, i, j) = ±16. В результате получается система линейных уравнений па ненулевые коэффициенты Уолша, которая имеет лишь небольшое число свободных переменных. Все возможные значения свободных переменных проверяются перебором.

В конце раздела 3.3 доказывается, что среди экстремальных функций пет функций, симметричных относительно перестановки двух переменных, н приводится формула построения экстремальных функций с параметрами п — 10, т — 5 из экстремальных функций с параметрами п — 9, т = 4:

д{хъ . . . , Х'щ) = fi'Xi © lio, х2 © lio, • • •, Хд ® Ж1П).

В четвертой главе исследуется достижимость оценки нелинейности nl(f) < 2n_1 — 2m для корреляционно-иммунных функций для всех параметров п и т.

В разделе 4.1 приводятся известные свойства коэффициентов Уолша экстремальных функций. Основное их свойство описывается следующей теоремой.

Теорема 6 Если корреляционно-илшунноя порядка т булева функция f от п переменных, т < п — 2, имеет нелинейность 2n_1 — 2т, то для любого и 6 F2" выполнено

W/(u) = nwi(u)2m+l (mod 2m+2),

где 7Г0 = 1, 7Ti = тг2 = • • • = irm = 0, 7T¿ = Q) (mod 2), tt¿ G {0,1}

при i >771.

Это свойство позволяет получить условие на параметры п и т.

Теорема 7 Если существует корреляционно-иммунная булева функция, / порядка т от п переменных, rn < п -2, с нелинейностью 2"-1 — 2"', то выполнено

j=0

Нахождение всех пар п и т, удовлетворяющих этому уравнению, является основной задачей последующих разделов.

В разделе 4.2 вводятся обозначения и доказываются утверждения необходимые для эффективной работы с остатками биномиальных коэффициентов но модулям степеней двойки. Обозначим F(l) = 1, F(x) — П?=1 (2г + 1) при х > 1, F(x) = l/nL(2i + 1) при х < 0. Эта функция равна. F(x) -2х\/х\ при х > 0. Введем функцию G(x,y) = ¿--(yffil-yy Тогда выполнена следующая теорема.

Теорема 8 = (?п)Н((2п+а) mod2k,(2m + b) rnod2k) (mod 2к), где

а, Ь 6 {0,1}, Я(2.т, 2у) = G(x, у), Н(2х+1,2у) = G(x, y)^rv Щ2х, 2у+ 1) = G(x, Н(2х + 1,2у + 1) = G(x, у)

Обозначим Мк матрицу значений функции Н по модулю 2к:

Мк ■■

Н{0,0) mod 2к ■■■ Н{0,2к - 1) mod 2к Н(2к -1,0) mod 2к ■■■ Н{2к - 1,2к - 1) mod 2к

Элемент этой матрицы в г + 1 строке и j +1 столбце будем записывать как

Mie(i,j) = H(i,j) mod 2к. Пусты«« = a,_i. ..a\do и wb = Ь,-\ • ..Мо........два

двоичных слова. Обозначим Щ(«;о, wb) = П;=о

Тогда для чисел а = X^lJ ар? и b = Х^'-о bp' остаток биномиального коэффициента по модулю 2к можно выразить через Па-.

Лемма 4 (») = (mod 2*).

Для каждой матрицы М — {ту} размера 2к х 2к введем функцию M(wa, wb) = mi+¡„/2»-*],1+|б/2»-*]- Аналогично для строки или столбца {т,-} размера 2к введем функцию M(wa) = rni+[a/2'-fc]- Определим семейство матриц

[О - (/>)

l(V) ••• £:»

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

Ь = Tlk(wb>'W(i)Alk_i('wb} wu) (mod 2*)

Следующий раздел 4.3 посвящен использованию этой формулы для исследования уравнения (2) но модулю 2к. Но для этого вначале выводится

формула для чисел щ.

Лемма 6 При г > т выполнено

т1) (m0d2)-

Благодаря этому сравнению уравнение (2) преобразуется к виду

Е W

i,(^)=i(mod 2)

Теперь уже легко увидеть, что это уравнение выполнено па двух сериях значений.

Лемма 7 Равенство (3) верно при п = 2S+1 + 1, т = 2s и п = + 2, т = 2я + 1, где s> 0.

Оставшаяся часть главы 4 посвящена доказательству обратного факта. Обозначим отношение мажорирования символом ;<. а длину слова w как Исходя из формулы биномиальных коэффициентов по модулю 2 и выражения биномиальных коэффициентов через функции от их двоичных записей, левая часть уравнения преобразуется к виду

1+ £, (<:.

»,(Д)=1(тоа 2)

1+ J2 nfcM,iw + l)M**-i(wn,m + l) (mod 2А"),

где wm и am — двоичные записи п и т, а под wi + 1 понимается слово той же длины, представляющее двоичную запись числа г + 1 (mod 2'"''). Далее доказывается ряд лемм о суммах вида +

l)M(wn,ti« + l) по модулю 2* для различных к, матриц М и ограничений на слова wn и гит. Их доказательство основано на разбиении суммы на две части в зависимости от старшего бита wi и последующего их упрощения. С помощью этих лемм удается доказать три теоремы па свойства нужных нам сумм биномиальных коэффициентов.

Теорема 9 Пусть для некоторых непустых слов w\ и выполнено гит =

lOiui, wn = llu'2 и u>2 > w\ или wm - Olu'i, um — Ю1У2 и W2 < wu тогда 1 + П2(ш, wi + l)Mf(wn, wi + 1) = 2 (mod 4).

Теорема 10 Пусть для некоторых непустых слов u>i и w^ выполнено wm = OIO'Oil'i, wn = ЮО'Гшг, Щ- г1"'11-1 < Щ, t > 0 или win = 01гиь wn = Ии'г, ®i — < Щ < Щ , тогда

1 + ^ П3(№П, wi + l)M£(wn,wi + 1) = 4 (mod 8).

Теорема 11 Пусть для некоторых непустых слов wi и вы,полнено wm = Ollu'i, wn = 110и.'2) Щ — 21й'11"1 <Щ < Щ или гит = 010г01го3. wn = 100'10гг2, Щ - г!""!"1 < Щ < Щ, t > 0 или wm = ОЮ'ЮОг^, wn = 100г1Ш,'2, Щ > Щ, t> 0, тогда

1 4- Y1 И(ivn, wi + l)M^(wn, wi + 1) = 8 (mod 16).

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

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

Теорема 12 При п > 12 выполнение, (3) влечет

п 1 ■ 1. «М , ^ п ~ 1 2 + 2 1о&2 п + 2 log2 {2е ) ~ 1 > т ~ 2 '

Вычисления показывают, что | log2 (|е8,/9) = 0.9669... < 1, поэтому мы будем пользоваться оценкой § + |log2n > то. Сравнение этой оценки с результатами предыдущего раздета позволяет исключить некоторые значения п.

Лемма 20 Ec.nu п > 32, то двоичная запись п не начинается с 11.

12Вотев А. А. О соотношениях между корреляционной иммунностью, нелинейностью и весом для неуравновешенных булевых функций, Математические вопросы кибернетики. Вып. 11, М., Физмат.шт, 2002, с. 1-19-162.

Пусть 2''"1 < п < 2Р. Далее будем рассматривать лишь случай р > 0. Тогда из теорем раздела 4.3 следует оценка на т снизу.

Лемма 21 Пусть п = 10Пш2 = 2,+*:+1 + 2' + Щ, |ш2| - « > 3, к > 1. Тогда т > | +

Получается, что чем дальше п от 2Р~1, тем больше должна быть разница между т и п/2. Но, начиная с некоторого момента, это противоречит пашей верхней границе | +1 п > гп. Это позволяет ограничить п значениями, близкими к 2Р-1.

Лемма 22 Выполнены неравенства

2р-1 <п< 2Р~1 + 8р,

21"2 <т< У'-2 + |р, т < 2Р_1.

С другой стороны, для значений п и т, близких к 2),_1 и 2Р~2 соответственно, можно улучшить оценки на суммы биномиальных коэффициентов. Для оценки суммы биномиальных коэффициентов снизу с учетом доказанных ограничений па п и т получается следующий результат.

Лемма 23 Пусть т = Ю*»!, |Ш1| = к > 0, г — число нулей в слове. к-'ь V ^ тогда

•+ е

¿,(,;)=1(тос12)

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

Лемма 24 Пусть р > 9, тогда

2Р~1 <п < 2"-1 + 16,

2""2 <т< 2"~2 + 8.

Дальнейшее сокращение этой области возможно с помощью оценки суммы биномиальных коэффициентов сверху.

Лемма 25 Пусть р>9,гп = Ю*^, |к>]| = < < 3, г — число нулей в

слове wi. Тогда выполнено

;,(^)=i(mod 2)

Вместе с оценкой снизу, это позволяет получить соотношение менаду п и т. _

Лемма 26 Пусть р > 9, тогда т — lO^wi, |u>i| = t < 3 и п — 2т — t + 2 + 1, где z число нулей в слове Wi-

Далее показывается, что если т четно, то уравнение для пары п и т выполнено тогда и только тогда, когда оно выполнено для пары п + 1 и т + 1. Отсюда следует, что достаточно исследовать пары с нечетным т. С учетом полученных ограничений на п и т остается лишь три серии значений: (2Р-1+5,2Р-2 + 3), (гР-ЧЭ.г^ + б), (2р-1 + 12,2'~2 + 7). Первые две из них откидываются с помощью теорем из раздела 4.3.

Последний случай рассматривается в следующем разделе 4.5 с помощью рассуждений, аналогичных рассуждениям в разделе 4.3.

Теорема 13 Пусть wm — 010*111, wn = 10*1100, тогда

1 + П3(ют1, wi + l)M2*(um, wi + 1) = 4 (mod 8).

Отсюда выводится основной результат, описывающий все решения уравнения (2) при п > 512.

Теорема 14 Если п > 512, 0 < т < п — 1 и пара п, т не принадлежит сериям т = 2s, п = 2S+1 + 1 и т = 2s + 1, п = 2S+1 + 2 при s > 8, то для всех корреляционно-иммуннъа порядка гп булевых функций f от п переменных выполнено неравенство

nl(f) < 2"-1 - 2m+1.

Для меньших значений п уравнение (2) непосредственно проверено на компьютере, что позволяет избавится от условия п > 512 в предыдущей теореме.

Следствие 1 Если пара п, т, 0 < т. < п — 1 не принадлежит сериям т = 2s. 11 = 2S+1 + 1 и т = 2s + 1, n = 2S+1 + 2 при s > 0, т,о для всех

корреляционно-илшунныл порядка т булевых функций / от п переменных выполнено неравенство

п1(}) < 271"1 - 2т+1.

В заключении приведены основные результаты диссертации.

1. Доказана нижняя оценка на количество элементов ортогонального массива, если его сила не меньше где п — число его факторов.

2. Найден новый детермеиированный метод построения 3-устойчивых булевых функций от 9 переменных с наибольшей возможной нелинейностью 240. Полученные функции обладают симметрией 7 порядка, в то время как ранее известные подходы использовали эвристики и выдавали функции без какой-либо симметрии.

3. Впервые построены булевы функции от 9 переменных корреляциопио-имунные 4 порядка с наибольшей возможной нелинейностью 240. С их помощью получены функции от 10 переменных, корреляционно-иммунные 5 порядка с наибольшей возможной нелинейностью 480.

4. Показано, что верхняя граница нелинейности п/(/) < 2"-1 - 2Т" для корреляционно-иммунных функций порядка 0 < т < п - 1 от тг переменных может достигаться только при п = 2в+1 + 1, т — 2* и п = 2"+1 + 2, т = 2" + 1, где я > 0, в € Ъ.

Благодарности. Автор выражает глубокую благодарность и признательность научному руководителю Юрию Валерьевичу Тарашшкову за постановку задач и внимание к работе. Автор также благодарит сотрудников кафедры дискретной математики Московского Государственного Университета им М. В. Ломоносова и Валерия Александровича Васеннна за поддержку и высказанные замечания.

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

[1] Халявин А. В. Оценка мощности ортогональных массивов большой силы. // Вестник Московского университета. Серия 1, Математика. Механика. 2010. №3. - с. 49-51.

[2] Халявин А. В. Оценка нелинейности корреляционно-иммунных булевых функций, Прикладная дискретная математика, №1 (11), 2011, с. 34-69.

[31 Халявнн А. В. Построение 4 корреляционно-иммунных булевых функций от 9 переменных с нелинейностью 240. // Материалы X Международного семинара «Дискретная математика и ее приложения». Москва, МГУ, 1-6 февраля 2010г. — М.: Изд-ио мехашжо-магематпческого факультета МГУ, 2010, 549с. -- с. 534.

[4] Халявин А. В. Неравенства для ортогональных массивов большой силы // Материалы Четвертой международной научной конференции по проблемам безопасности и противодействия терроризму. Московский Государственный Университет им. М. В. Ломоносова, 30-31 октября 2008г. Том 2, Материалы Седьмой общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008). .......М.: МЦНМО, 2009........ 280с........с. 33.

[5] Khalyavin A. Constructing boolean functions with extremal properties. // Boolean functions in cryptology and information security. 2008. IOS Press. - P. 289-295. (NATO Science for Peace and Security Series D: Information and Communication Security.......Vol. 18)

Подписано в печать: 25.11.11

Объем: 1,5 усл.л.л. Тираж: 100 экз. Заказ № 796 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского,39 (495) 363-78-90; www.reglet.ru