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

Омаров, Рустам Рамазанович

Исследование криптографических параметров, близких к нелинейности, для булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Омаров, Рустам Рамазанович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Исследование криптографических параметров, близких к нелинейности, для булевых функций»

Автореферат диссертации на тему "Исследование криптографических параметров, близких к нелинейности, для булевых функций"

Московский государственный университет имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

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

Омаров Рустам Рамазанович Исследование криптографических

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

01.01.09 — дискретная математика и математическая кибернетика

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

2 8 МАР 2013

Москва - 2013

005051230

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

Научный руководитель: доктор физико-математических наук,

профессор Алексеев Валерий Борисович.

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

профессор Леонтьев Владимир Константинович;

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

Ведущая организация: Национальный исследовательский университет -

Московский энергетический институт.

Защита диссертации состоится 12 апреля 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан марта 2013 г.

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

Н.П. Трифонов

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

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

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

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

1 Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В., Основы криптографии, М.:Гелиос, Ассоциация российских ВУЗов, 2001. 479 с.

2Ба6аш A.B., ШанкинГ.П., Криптография, М.: Солон-Р, 2007. 512 с.

3BihamE., Shamir A., Differential cryptanalysis of DES-like cryptosystems// J. Cryptology, 1991. V.4, N1. 3-72.

4CourtoisN., Meier. W., Algebraic attacks on stream ciphers with linear feedback // Advances in cryptology, EUROCRYPT 2003. - Berlin/Heidelberg: Springer Verl., 2003. 345-359. (Lecture Notes in Computer Science; V. 2656).

5Matsui M., Linear cryptanalysis method for DES cipher// Advancesin Cryptology - EUROCRYPT'93.

Workshop on the theory and application of cryptographic techniques (Lofthus, Norway. May 23-27, 1993),

булевой функции, корреляционную и алгебраическую иммунности. Ежегодно публикуются десятки работ, посвещенных изучению этих параметров, а также связей между ними6'7'8,9.

В ряде методов криптографического анализа существенно используется „близость" криптографических функций к функциям, обладающим простой структурой с хорошо изученными свойствами. Примером таких „плохих" функций служат аффинные функции (в дискретной математике их обычно называют линейными). Мерой удаленности булевой функции от класса аффинных функций является ее нелинейность. Множество функций, для которых нелинейность принимает максимально возможное значение, называется множеством максимально-нелинейных функций. Известно, что при четных п нелинейность булевой функции от тг переменных ограничена величиной Nf < 2n_1 - 2"/2-1, причем для максимально-нелинейных функций это неравенство обращается в равенство.

Наличие у булевой функции свойств, близких к линейным, говорит об определенной „простоте" этой функции, что облегчает исследование других ее параметров и свойств. Поэтому возникает практическая необходимость в построении функций, обладающих высокой или даже максимально возможной нелинейностью10'11'12'13. Несмотря на то, что уже построено довольно много классов максимально-нелинейных функций, не удается описать класс всех максимально-нелинейных функций. Более того, не получено близких верхних и нижних оценок на мощность этого класса. Однако,

Ргос. Berlin: Springer, 1994. 386-397 (Lecture Notes in Comput. Sci. V.765).

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

71&ранников Ю. В., О корреляционно-иммунных и устойчивых булевых функциях// Математические вопросы кибернетики. Вып. 11, М.: Физыатлит, 2002. 91-148.

"Dalai D К., "Gupta К. С., MaitraS., Results on algebraic immunity for cryptographically significant Boolean functions// Progress in Cryptology: INDOCRYPT'04, LNCS V. 1880, Springer-Verlag, 2004. 92-

9SarkarP., MaitraS., Nonlinearity bounds and constructions of resilient Boolean functions// CRYPTO'2000, LNCS V. 1880, Springer-Verlag, 2000. 515-532.

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

11 Carlet С., Two new classes of bent functions// Workshop on the theory and application of cryptographic techniques on Advances in cryptology, January 1994, Lofthus, Norway. 77-101.

"Rodier F., Asymptotic nonlinearity of Boolean functions // Designs, Codes and Cryptography, V.40,

N. 1, 2006. 59-70. .

"Tbrannikov Y., New Constructions of Resilient Boolean Functions with Maximal Nonlinearity// Revised Papers from the 8th International Workshop on Fast Software Encryption, April 02-04, 2001., 66-77.

имеется большое число результатов в этом направлении14,15,16.

Вместе с нелинейностью можно рассматривать и нелинейность порядка г, которая определяется как минимальное расстояние между данной функцией и всеми функциями степени не более г. Если для подсчета нелинейности разработан эффективный аппарат коэффициентов Уолша, то подсчет нелинейности произвольного порядка представляет более сложную задачу. Эту проблему удается частично разрешить. Например, имеются результаты по рекурсивньш оценкам на нелинейность порядка г17, а также оценки на нелинейность через другие параметры функции18,19.

Высокая нелинейность булевой функции означает, что она плохо приближается аффинными функциями. Однако в принципе может оказаться, что данную функцию удастся хорошо приблизить „почти аффинной" булевой функцией. Например, наряду с нелинейностью, исследуется расстояние до множества функций, обладающих нетривиальными линейными структурами20 ( булева функция обладает нетривиальной линейной структурой, если существует ненулевой вектор а, такой что f(x) © f(x Ф а) = const). Также исследовалось расстояние до множества ¿-аффинных функций21 (при к Ф 0 это множество состоит из некоторого числа аффинных и квадратичных функций). В качестве „плохих" функций можно рассматривать и другие классы функций, например алгебраически вырожденные функции22 (функция / называется алгебраически вырожденной, если ее можно представить в виде f(x) = д(Ах), где А — некоторая матрица, а д — функция от меньшего числа переменных).

Анализ конкретных криптографических объектов часто приводит к ре-

14Agievich S. V., On the representation of bent functions by bent rectangles // Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics. Proc. Boston: VSP, 2000. 121-135.

15Caxlet 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. 307-314.

16TokarevaN.N., On the number of bent functions from iterative constructions: lower bounds and hypotheses // Advances in Mathematics of Communications (AMC), 2011, V. 5, N 4. 609-621.

17Carlet C., Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications// IEEE Transactions on Information Theory, V.54, N. 3, 2008. 1262-1272.

"Лобанов M.C., Точные соотношения между нелинейностью и алгебраической иммунностью// Дискретная математика и исследование операций, Изд-во Наука, Москва, 2008, Т. 15, вып. 6. 34-47.

19Лобанов М. С., Получение нижних оценок на нелинейность булевой функции через размерность некоторых подпространств, Материалы X Международного семинара «Дискретная математика и ее приложения», Изд-во мех.-мат. факультета МГУ, Москва, 2010. 416-419.

i0Meier W., Staffelbach О. Nonlinearity criteria for cryptographic functions // LNCS. 1990. V. 434. 549562.

"Токарева H. H. Сильно нелинейные булевы функции: бент-функции и их обобщения. Диссертация на соискание ученой степени кандидата физико-математических наук, Новосибирск, 2008.

22Алексеев Е. К., Аппроксимация дискретных функций алгебраически вырожденными функциями в анализе систем защиты информации. Диссертация на соискание ученой степени кандидата физико-математических наук, Москва, 2011.

шению систем булевых уравнений вида

/(а1э®) = сх,

. /(Йт, X) = Ст;

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

д(ах,х) = а,

< ...

„ д(ат,х) = Ст.

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

системе. Если исходная нелинейная система содержала п неизвестных, то полученная линейная система будет содержать не более п + к неизвестных. При фиксированном к сложность решения такой линейной системы будет 0(п3). Находя решения этой линейной системы и проверяя их на необходимую связь между переменными, мы с некоторой вероятностью можем быстро получить решение исходной системы.

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

Методы исследования. При выполнении диссертационного исследования использовались методы дискретной математики и алгебры.

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

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

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

Соответствие диссертации паспорту научной специальности.

Диссертация соответствует паспорту специальности 01.01.09, поскольку исследования в ней относятся к научному направлению «Дискретная математика».

Апробация результатов. Результаты, полученные в диссертации, докладывались и обсуждались на международных конференциях: X международном семинаре «Дискретная математика и её приложения» (Москва, 2010), VIII международной конференции «Колмогоровские чтения» (Ярославль, 2010), XVI международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011), XI международном семинаре «Дискретная математика и её приложения» (Москва, 2012).

Кроме того, результаты обсуждались на научном семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ.

Публикации. Результаты автора по теме диссертации опубликованы в 6 работах, список которых приводится в конце автореферата; 2 из них опубликованы в журналах из списка ВАК.

Личный вклад автора. Основные результаты диссертации получены автором. В работах, опубликованных в соавторстве с В.Б. Алексеевым, В.Б. Алексееву принадлежит постановка задач, общее руководство исследованиями иобсуждение новых подходов.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии, включающей 29 наименований. Общий объем диссертации составляет 75 страниц.

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

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

В первой главе приводятся основые определения и вспомогательные утверждения.

Пусть п - произвольное натуральное число. Через Vn будем обозначать векторное пространство наборов длины п с компонентами из {0,1} с операцией ф покоординатного сложения векторов по модулю 2. Под булевой функцией от п переменных будем понимать отображение / : Vn —» {0,1}. Ее весом wt(f) будем называть количество наборов, на которых она равна 1. Расстоянием от булевой функции / до булевой функции д называется величина dist(f,g) = wt{f ф д), т.е. число наборов, на которых значения функций / и д различаются. Расстоянием от f до множества М булевых функций от п переменных называется величина dist(f, М) = min dist(f, g). Под расстоянием между двумя множествами

gGM

булевых функций М и N будем понимать dist(M, N) = min distlg, h).

дШ heN

Пусть x и у - два произвольных вектора из Vn. Через (х, у) будем обозначать их скалярное произведение над полем GF(2) с двумя элементами 0 и 1: {х, у) = xiyi ф ... ф хпуп (здесь Ф - это сложение по модулю 2). Булева функция f от п переменных называется аффинной, если существуют а = (ai,..., ап) £ Vn и с € {0,1} такие, что /(ж) = (о, х) ф с. Множество всех аффинных булевых функций от п переменных будем обозначать Ап. Расстояние dist(f, Ап) от булевой функции f{x) от п переменных до множества Ап аффинных булевых функций называется нелинейностью функции f(x) и обозначается через Nf.

Булевы функции f(x), для которых Nf равно максимально возможному

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

Далее рассматривается множество приближающих функций, у которых в полиноме Жегалкина присутствует не более к нелинейных слагаемых.

Определение. Через АЕ„ будем обозначать класс всех почти аффинных функций от п переменных, а именно, функций вида Х^©.. .фХ1к®1(х), где X= П хз > ^ ~ произвольные подмножества (возможно, пустые: Х0 — 0)

т _

множества {1,... ,п}, £ = 1, к и 1(х) £ Ап. При к = 1 будем писать АЕп.

Введем следующую функцию рк(и) — сИзЬ(и, АЕ%п), где и — некоторое множество функций от 2п переменных. В следующей теореме получена нижняя оценка для расстояния между классом максимально-нелинейных функций от 2п переменных и множеством приближающих функций АЕ^п-

Теорема 1. Пусть Вгп — множество всех максимально-нелинейных функций от 2п переменных, тогда

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

Определение. Пусть х = (хь... ,хп), у = (ух,... ,уп)- Класс Мэйорана-Мак-Фарланда определяется как класс всех булевых функций /(х, у) от 2п переменных вида /(а:,у) — {к{у),х) ф Ф(у), где 7Г - произвольная подстановка на множестве Уп, а Ф (у) - произвольная булева функция от п переменных. Будем обозначать его через Мгп.

Для класса Мэйорана-Мак-Фарланда удается доказать следующие два утверждения.

Теорема 2. При любом к > 0 и п = рк +1,0 < Ь < к выполняется:

Следствие 1. При любом фиксированном кип-* оо выполняется:

Рк(В2п)>22п-1- Зк-2п~\

рк(М2п) < 22"-1 - 3* • 2"-1 + о(2п~1).

С учетом того, что рк{Вгп) < рк(М2п), из теоремы 1 и следствия 1 получаем.

Теорема 3. При любом фиксированном к и тг оо выполняется:

Рк(В2п) = 22"-1 - 3* • 2""1 + о(2"-1).

Теорема 4. При любом фиксированном к и п —> оо выполняется:

Рк(М2п) = 22"-1 - 3* • 2"-1 + о(2"-1).

Легко заметить, что, в отличие от класса А„, класс АЕ% не является замкнутым относительно невырожденных афинных преобразований. Поэтому интерес также представляет исследование расстояния до класса, содержащего все функции из АЕ„, а также все функции, аффинно эквивалентные им. В частности, интересно, сохранятся ли полученные для АЕ* оценки?

---к

Определение. Через АЕп будем обозначать класс всех функций, аффинно эквивалентных функциям из класса АЕ%, а именно, функций вида д(Ах © d), где д £ АЕА — произвольная невырожденная над полем GF(2) матрица размера п х n, a d € V„ — произвольный вектор и вычисление Ах ® d производится в поле GF(2). При к — 1 будем писать

АЁ\ = АЕп-

Определим функцию Pk(U) как Pk{U) = dist(U, Ае\п), где U — некоторое множество функций от 2п переменных.

Следующая теорема говорит о том, что добавление к функциям класса АЕ\п всех функций, аффинно эквивалентных им, не сокращает расстояние от класса В2п до приближающего класса АЕ2п по сравнению с рк(В2п).

Теорема 5. Для множества максимально-нелинейных функций Вп верно

Рк{Вп) = Рк(Вп)

и, следовательно, при любом фиксированном к и тг —> оо

Рк{В2п) = 22"-1 - Zk • 2п~1 + о(2"-1).

В первой главе мы попытались ответить на вопрос: Как изменится расстояние между классами В2п и А2п, если перейти от последнего к АЕ%п или

■---к

АЕ2п■ К сожалению, класс В2п полностью не описан, что затрудняет получение точного значения. Но для малого значения параметра к и класса максимально-нелинейных функций М2п удается получить точный ответ.

Во второй главе получена точная формула для расстояния от классов Bin и М2п до классов АЕ2п и АЕ2п при всех п.

Теорема 6. Для класса всех максимально-нелинейных функций В2п при всех п> 2 выполняется равенство:

Р\{В2п) = 22"-1 — 3 • 2™-1 + 2.

(При п = 1 pi(B2n) = 0.)

Примером максимально-нелинейной функции, для которой dist(f, АЕ2п) = 22"-1 - 3 • 2"-1 + 2 служит f(x,y) = (х,у) Ф ух ф ... Ф Уп Ф sg(yu...,yn), где S5(0,...,0) = 0 и sg(yu... ,уп) = 1, если (Уъ...,У»Ж0,...,0).

Следствие 2. Для класса максимально-нелинейных функций М2п при всех п> 2 выполняется равенство:

Р1(М2п) = 22п-1 - 3 • 2""1 + 2.

(При п = 1 pi(M2n) = 0.)

Доказательство следует из того факта, что указанная выше f{x,y) S М2„.

Класс М2п не является инвариантным относительно невырожденных аффинных преобразований.

Определение. Обозначим через Н2п — множество функций от п переменных вида:

h(x) = f{h{x),...,l2n(x)),

где k G A2n,i = IT2ÏÏ, /(z) e AE\n. ____^

Заметим, что AE2n с Н2п и dist(M2n, Н%п) < рк(М2п).

Следствие 3. Для класса максимально-нелинейных функций М2п при всех п> 2 выполняется равенство:

dist(M2n, H\n) = 22"-1 - 3 • 2"-1 + 2.

При п = 1 dist(M2n, Н2п) = 0.

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

Теорема 7. Для любой максимально-нелинейной функции f(x) Є #2п берко неравенство:

сИ8Ь(/,АЕ2п)<22п-1 -2-2п~\

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

Более того, теорема 7 останется верной, если от АЕ2П перейти к АЕ2П-

Теорема 8. При всех п>2 существуют максимально-нелинейные функции от 2п переменных, для которых

<іізі(/, АЕ2п) = 22"-1 - 2 • 2"-1.

В третьей главе исследуется расстояние между классом максимально-нелинейных функций М2п и классом „почти" линейных функций АЩп. Получена точная формула для этого расстояния при всех п. Показано, что существуют функции, расстояние от которых до класса АЕ%п заведомо не достигает этой величины.

Теорема 9. Верно равенство:

Р2{М2п) = 22"-1 - 9 • 2п~1 + 6 (2І.ІІ + 2І*1) - 8

при п > 6. При п = 1,2,3,4,5 величина р2{М2п) равна 0,0,16,88,416 соответственно.

Теорема 10. При всех п > 2 существуют максимально-нелинейные функции от 2п переменных, для которых

йізЦ/, АЕ22п) = 22"-1 - 4 • 2""1.

Основные результаты, выносимые на защиту

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

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

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

3. Получена точная формула для расстояния от класса максимально-нелинейных функций Мэйорана-Мак-Фарланда от 2п переменных до класса функций, у которых в полиноме Жегалкина присутствует не более двух нелинейных слагаемых.

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

Автор выражает благодарность своему научному руководителю, доктору

физико-математических наук, профессору Алексееву Валерию Борисовичу

за постановку задачи и постоянное внимание к работе.

Публикации автора по теме диссертации

[1] Алексеев В. Б., Омаров Р. Р., "О приближении максимально-нелинейных булевых функций почти линейными функциями", Дискретная математика, Изд-во Наука, Москва, 2012, Т. 24, вып. 3, 73-81

[2] Алексеев В. Б., Омаров Р. Р., "Исследование одного параметра булевых функций, близкого к нелинейности", Научные ведомости Белгородского государственного университета, 2009, Т. 15(70), №12/1, 81-87

[3] Омаров Р. Р., "О расстояниях от максимально-нелинейных функций до некоторого класса булевых функций", Материалы XI Международ-

ного семинара «Дискретная математика и ее приложения», Изд-во мех.-мат. факультета МГУ, Москва, 2012, 425-428

[4] Алексеев В.Б., Омаров P.P., "О приближении булевых функций почти линейными функциями", Материалы X Международного семинара «Дискретная математика и ее приложения», Изд-во мех.-мат. факультета МГУ, Москва, 2010, 514-516

[5] Алексеев В. Б., Омаров P.P., "О приближении одного класса максимально-нелинейных булевых функций почти аффинными функциями", Труды VIII Международных Колмогоровских чтений, Изд-во ЯГПУ, Ярославль, 2010, 98-104

[6] Алексеев В. Б., Омаров Р. Р., "О расстояниях от максимально-нелинейных булевых функций до почти аффинных функций", Материалы XVI Международной конференции «Проблемы теоретической кибернетики», Нижегородский университет, Нижний Новгород, 2011, 24-28

Напечатано с готового оригинал-макета

Подписано в печать 04.03.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 090 экз. Заказ 054.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Омаров, Рустам Рамазанович, Москва

Факультет вычислительной математики и кибернетики Московский государственный университет имени М. В. Ломоносова

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

04201355388

Омаров Рустам Рамазанович

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

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

кибернетика

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

Научный руководитель: д. ф.-м. н., профессор Алексеев Валерий Борисович

Москва. 2012

Оглавление

Введение 3

1 Оценки для расстояния между классами при произвольном к 9

2 Точные формулы для расстояния при к = 1 20

3 Точные формулы для расстояния при к = 2 28 Заключение 70 Список литературы 72

Введение

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

[2, 3; 12, 16, 18]. К таким свойствам можно отнести нелинейность и устойчивость булевой функции, корреляционную и алгебраическую иммунности. Ежегодно публикуются десятки работ, посвсщенных изучению этих параметров, а также связей между ними (например, [4, 8, 17, 21]).

В ряде методов криптографического анализа существенно используется ,.близость" криптографических функций к функциям, обладающим простой структурой с хорошо изученными свойствами. Примером таких .,плохих" функций служат аффинные функции (в дискретной математике их обычно называют линейными). Мерой удаленности булевой функции от класса аффинных функций является ее нелинейность. Множество функций, для которых нелинейность принимает максимально возможное значение, называется множеством максимально-нелинейных функций. Известно, что при четных п нелинейность булевой функции от п переменных ограничена величиной ./V/ < 2"~1 — г™/2"1, причем для максимально-нелинейных функций это неравенство обращается в равенство.

Наличие у булевой функции свойств, близких к линейным, говорит об определенной „простоте'' этой функции, что облегчает исследование других ее параметров и свойств. Поэтому возникает практическая необходимость в построении функций, обладающих высокой или даже максимально возможной нелинейностью [10, 13, 20, 22]. Несмотря на то, что уже построено довольно много классов максимально-нелинейных функций, не удается описать класс всех максимально-нелинейных функций. Более того, не получено близких верхних и нижних оценок на мощность этого класса. Некоторые результаты в этом направлении можно найти в [11, 14, 23].

Вместе с нелинейностью можно рассматривать и нелинейность порядка г, которая определяется как минимальное расстояние между данной функцией и всеми функциями степени не более г. Если для подсчета нелинейности разработан эффективный аппарат коэффициентов Уолша, то подсчет нелинейности произвольного порядка представляет более сложную задачу. Рекурсивные оценки на нелинейность порядка г можно найти в [15], а оценки на нелинейность через другие параметры функции в [4, 5, б].

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

хорошо приблизить ,,почти аффинной'' булевой функцией. В работе [19]. наряду с нелинейностью, исследуется расстояние до множества функций, обладающих нетривиальными линейными структурами ( булева функция обладает нетривиальной линейной структурой, если существует ненулевой вектор а, такой что /(х) Ф /(о; ф а) = соиз€). Расстояние до множества /с-аффинных функций (при к ф О это множество состоит из некоторого числа аффинных и квадратичных функций) исследуется в [9]. В качестве „плохих" функций можно рассматривать и другие классы функций, например алгебраически вырожденные функции [1] (функция / называется алгебраически вырожденной, если ее можно представить в виде /(х) = д(Ах), где А — некоторая матрица, а д — функция от меньшего числа переменных).

Анализ конкретных криптографических объектов часто приводит к решению систем булевых уравнений вида

/(оь х) = С\,

для некоторого неизвестного вектора х. Для произвольной булевой функции / такие системы плохо решаются. Предположим, что для некоторой булевой функции д(а, х) с достаточно большой вероятностью выполняется равенство f(a,x) = д(а,х), тогда с определенной

вероятностью будет выполняться система равенств

д{а>1, х) = С\,

^(З'ТП! ■£) Сто-

Если функция д - аффинная относительно х, то получим линейную систему, которая быстро решается, и мы с определенной вероятностью находим решение исходной системы. Однако решение можно быстро найти и в тех случаях, когда функция д в своем полиноме Жегалкина содержит не более к нелинейных слагаемых. Заменяя каждый моном вида х^ ... на соответствующую переменную Игь...1г5, мы придем к некоторой линейной системе. Если исходная нелинейная система содержала п неизвестных, то полученная линейная

система будет содержать не более п + к неизвестных. При фиксированном к сложность решения такой линейной системы будет 0(н3). Находя решения этой линейной системы и проверяя их на необходимую связь между переменными, мы с некоторой вероятностью можем быстро получить решение исходной системы.

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

Пусть Fn множество булевых функций от п переменных. Определим расстояние между двумя булевыми функциями как число наборов, на которых они различаются, т.е. dist(f,g) — | {% : f(x) ф $(х')} I- Расстоянием между двумя множествами функций М, N С

Fn называется dist(M,N) — mmdist(f,g). Множество булевых функций, у которых сте-

/ем geN

пень полинома Жегалкина не превосходит 1, называется множеством аффинных функций. Обозначим его через Ап. Тогда нелинейность функции / равна Nf = dist(f, Ап). Множество булевых функций, у которых нелинейность равна максимально возможному значению для функций из Fn, называется множеством максимально-нелинейных функций.

Пусть АЕ„ множество функций от п переменных, у которых в полиноме Жегалкина

---к

присутствует не более к нелинейных слагаемых, а АЕп множество функций от п переменных аффинно эквивалентных функциям из АЕ„. Обозначим через Pk(U) = dist(U, АЕ^), где U - некоторое множество функций от 271 переменных.

В диссертации получены следующие основные результаты (в скобках приводятся номера теорем в тексте диссертации).

Теорема 1 (теорема 1.1) Пусть £?2,г множество всех максимально-нелинейных функций от 2п переменных, тогда

Pk(B2n)> 22n-l-'Sk-2n~l.

Обозначим через Мп известный класс максимально-нелинейных функций от ~и переменных

— класс Мэйорана-Мак-Фарланда.

Теорема 2 (теорема 1.2) При любом к > 0 и п = рк + 0 < Ь < к выполняется:

Рк(м2п) < 22п~'- зк ■ (г - ^^ -2п-\

Из теорем 1 и 2 следует.

Теорема 3 (теорема 1.3) При любом фиксированном к и п —> оо выполняется:

Рк{В2п) = 22п~1 - Зк ■ 2п~1 + о(2п~1).

При малых значениях параметра к удается получить точные формулы для величин Рк{В2п) и рк{М2п)

Теорема 4 (теорема 2.1) Для класса всех максимально-нелинейных функций В2п при всех п > 2 выполняется равенство:

Р\{В2п) — 22"-1 — 3 • 2п~1 + 2.

(При п = 1 Р1(в2п) = о.;

Теорема 5 (теорема 3.1) Верно равенство:

р2(М2п) = 22п~1 - 9 • 2п~1 -4- 6 (^21^-1 Ч- — 8

при п > 6. При п — 1,2,3,4,5 величина р2(М2п) равна 0, 0,16, 88,416 соответственно. Опишем кратко содержание работы.

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

В главе 1 приводятся основые определения и вспомогательные утверждения. Рассмат-

---к

риваются два множества приближающих функций АЕ2п и АЕ2п. Доказывается, что расстояние от максимально-нелинейных функций до АЕ2п снижается по сравнению с их нелинейностью не более чем на (Зк — 1) ■ 2п~1. Строится пример максимально-нелинейной функции из класса Мэйорана-Мак-Фарланда, для которой расстояние до класса АЕ2п асимптотически равно 22'1-1 — Зк ■ 2п~х 4- о(2п~1) при фиксированном кип—* оо. Далее показывается, что добавление к функциям класса АЕ2п всех функций, аффинно эквивалентных им, не сокращает расстояние по сравнению с рк{В2п).

В главе 2 исследуется величина Рк{В2П) при к = 1. Получена точная формула для величины р\(Вгп), ПРИ всех п- Доказывается, что для всех максимально-нелинейных функций от 2п переменных расстояние до класса АЕ\п гарантированно снижается по сравнению с их нелинейностью на величину 2п~1. Показывается, как для произвольной максимально-нелинейной функции построить функцию д(х) из класса АЕ\п, для которой (Иэ^.д) — 22п~~1 — 2 • 2п~1. Также доказывается, что существуют максимально-нелинейные функции, для которых сЙ5£(/, АЕ12п) = 22"-1 — 2 • 2П_1. Причем этот результат сохраняется при переходе от класса АЕ\п к классу АЕ2п.

В главе 3 исследуется величина Рк{М2П) при к = 2. Получена точная формула для этой величины при всех 71. Как и в случае Р\(В2П) показывается, что существуют более устойчивые функции, для которых расстояние до класса АЕ\п заведомо больше и равно 1_4 • 9"-1

В диссертации принята следующая нумерация теорем. Теоремы нумеруются двойками чисел, где первое число номер главы, а второе - номер теоремы внутри главы. Определения, леммы, утверждения и следствия, а также формулы, нумеруются аналогичным образом. Основные результаты диссертации опубликованы в работах [24, 25, 26, 27, 28, 29].

Глава 1

Оценки для расстояния между классами при произвольном к

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

Пусть Ii - произвольное натуральное число. Через Vn будем обозначать векторное пространство наборов длины п с компонентами из {0,1} с операцией ® покоординатного сложения векторов по модулю 2. Под булевой функцией от п переменных будем понимать отображение / : Vn —> {0,1}. Множество всех булевых функций от п переменных будем обозначать через Fn.

Определение 1.1. Пусть / € Fn булева функция. Ее весом wt(f) будем называть количество наборов, на которых она равна 1. В некоторых случаях для определенности мы будем писать wtn{f).

Определение 1.2. Пусть f,g € Fn. Расстоянием от булевой функции / до булевой

функции д называется величина dist(f,g) = wt(f Ф д), т.е. число наборов, на которых

значения функций fug различаются. Расстоянием от f до множества М булевых

функций от и переменных называется величина dist(f, М) = min dist(f,g). Под расстоя-

дем

нием между двумя множествами булевых функций М и N будем понимать d1st(M А") =

тшйгз^д К) 9ем

Определение 1.3. Пусть 1 £ Уп, у 6 Уп Через (г, у) будем обозначать скалярное произведение х и у над полем СР{2) с двумя элементами 0 и 1 (х, у) = Х\у\ ф ф хпуп (здесь ф - это сложение по модулю 2 )

Определение 1.4. Булева функция / от п переменных называется аффинной, если существуют а — {а\ ап) € Уп и с € {0,1} такие, что /(%) = (а,х) ф с = 01X1 ф ф апхп ф с Множество всех аффинных булевых функций от V переменных будем обозначать Ап

Определение 1.5. Расстояние дгз^,Лп) от булевой функции }{х) от п переменных до множества Ап аффинных булевых функций называется нелинейностью функции /(х) и обозначается через N/

Лемма 1.1. [7] Для любой булевой функции f(x) от п переменных справедливо неравенство Ау- < 2п~1 — 2"/2-1 Для четных п эта оценка достижима

Определение 1.6. Булевы функции ¡{х), для которых N} равно максимально возможному значению среди всех функций от п переменных, называют максимально-нелинейными функциями ( при четном п этот класс также называют классом бент функций) Множество таких функций будем обозначать через Вп

Определение 1.7. Для каждого а 6 Уп величина Wf(u), задаваемая равенством

называется коэффициентом Уолша-Адамара булевой функции / 6 Рп

Приведем без доказательства некоторые факты о максимально-нелинейных функциях из [7]

Для максимально-нелинейной булевой функции / 6 В2П все ее коэффициенты Уолша-Адамара равны ±2П Булеву функцию / € -р2п задаваемую равенством

И',(?/) = 2"(-1)/(и)

называют дуальной функцией к максимально-нелинейной функции /

Лемма 1.2. [7] 1) Функция f G F2n, дуальная к максимально-нелинейной функции f G F2n, сама является максимально-нелинейной; 2) пусть / G B2n,a,b G V2n,c G {0,1} и g{x) = f(x ф а) Ф (b, x) ф с. Тогда g G B2n, причем

3) пусть А — произвольная невырожденная над полем матрица размера 2п х 2ть.

Тогда функция /л = }{Ах) является максимально-нелинейной, причем

для любой f G В'2п, где А* = (А 1)Т

Лемма 1.3. [7] Пусть / G В2п, L С V2n - произвольное подпространство и a,b G V2n -произвольные вектюра. Тогда

где Ь1- ортогональное дополнение к Ь в У2п.

Определение 1.8. Через АЕ^ будем обозначать класс всех почти аффинных функций от п переменных, а именно, функций вида Хі1 ф ... ф Хік ф 1(х), где ХІІ — х3, її -

произвольные подмножества (возможно, пустые: Х0 = 0) множества {1,..., п}, £ = 1, /с и 1{х) £ Ап. При к — 1 будем писать АЕп.

Введем следующую функцию рк{и) = йгз^и, АЕ2п), где и — некоторое множество функций от 2п переменных. Верна следующая теорема.

Теорема 1.1. Пусть В2п ~ множество всех максимально-нелинейных функций от 2ть переменных, тогда

Доказательство. Пусть /(ж) — некоторая максимально-нелинейная функция от 2п переменных, а д{х) — X/х ф ... ф Х1к ф (а.х) ф с произвольная функция из класса АЕ2п. Обозначим через /'(х) = /(ж) Ф (а, х) ф с, д'(х) = Х1г ф ... ф Х1к. Тогда

fA = (f)A*

хЄафЬ

y€b®LA-

Pk{B2n) > 22n_1 — 3k • 27l_1.

wt(f(x)@g(x)) = wt(f(x)®g'(x)) = wt(f(x)) + £ (-1)''<*>. (1.1)

<?'(*)=i

Лемма 1.4. Для произвольной булевой функции f(x) G F2n и k > 1 верно

£ = Е(-2)г £ £(-i)/0r), (i-2)

ieV2n г=0 S'Ç{1, ,k}Xi =1

где Is = U /i-

les

Доказательство. Доказательство проведем методом математической индукции. При к = 1 утверждение леммы очевидно. При к = 2 имеем

£ (-D/W = £ (_i)/W + £ -2.^

ri Tl п ^G^hn

Положим, что при к — Ь — 1 формула (1.2) также верна. Докажем ее при к = Ь.

£ (-i)/w= £ £(-i)/w-x€V2n xeV2n жбК2„

_ 2 . (-!)/<*> = g(-2y £ E (-!)/<*> + E (-1)/W-

iev2u г=0 S'Ç{1„ ,t- 1}X, =1 xev2„

-2.g(-2r £ £ (-!)'<*> = £(-2Г £ £(-1рЧ

1=0 5Ç{1, ,i—1} X/S = l 1=0 SÇ{1,. ,£—1> X/S. = l

|S|=i+l x/t=l |S|=1+1

+ £(-i)/w + £(-2r £ £ (-i)/(x) = £(-2)г £ £(-i)/w-

x6V2n г=1 5C{1, ,,t}X/s = l г=0 SÇ{1, ,£}X/S. = 1

xh=1 |S|=t+l |S|=i+l

tes

Лемма доказана. □

Пусть А С {1,..., г/,} — некоторое подмножество. Обозначим через ЬА = {х : хг = 0, г € А}, а € У2п : = 1,1 6 А,^ = 0, г А. Заметим, что ЬА линейное подпространство в У2п размерности 2п — |Л|. Тогда можно доказать следующую лемму.

Лемма 1.5. Пусть /(х) £ В2п — произвольная максимально-нелинейная функция и к > 1. Тогда для нее верно равенство

к-1

(-1)/(х) = ^(-2)г ^ 2п_|/з1 ^ (-1 хбУ2п г=0 5С{1 ,к} уеи

Доказательство. Рассмотрим сумму ^ ( — А С {1,.. ,?;}. Заметим, что {х . х 6

Х4 = 1

У2п,ХА = 1} = : а; 6 ЬА} = + ЬА.

Тогда по лемме 1.3 для функции /(у), дуальной функции /(у) , верно

у^ (_!)/(*) = ^ (_1)/(») = 2а1тЬл~п ^ (-1)/(у)®^Л'у) =

Ха=1 (1.3)

Запишем (1.2) с учетом (1.3)

к-1

г=0 5С{1, ,/с}

Лемма доказана. □

Функция /(х) е 52п, следовательно 'ш^/'(х)) > 22™"1 — 271-1 . Учитывая это, лемму 1.5 и то, что (1%тЬ\з = |/51, из (1.1) получим

к-1

г=0 5С{1, ,к} |5|=г+1

)2п— 1 _ суп—

л ■ ^2гС\ = 22""1 - Зк

к _ г)7г— 1

г=0

В силу произвольности выбора функций f(x) и д(х) имеем

Pk(B2n) > 22п~1 - Зк ■ 2n_1

(1.4)

Теорема 1.1 доказана.

□

Рассмотрим широко извест�