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

  • Омаров, Рустам Рамазанович
  • кандидат физико-математических науккандидат физико-математических наук
  • 2012, Москва
  • Специальность ВАК РФ01.01.09
  • Количество страниц 75
Омаров, Рустам Рамазанович. Исследование криптографических параметров, близких к нелинейности, для булевых функций: дис. кандидат физико-математических наук: 01.01.09 - Дискретная математика и математическая кибернетика. Москва. 2012. 75 с.

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

Введение

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

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

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

Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

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

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

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

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

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] (функция / называется алгебраически вырожденной, если ее можно представить в виде /(х) = д(Ах), где А — некоторая матрица, а д — функция от меньшего числа переменных).

Анализ конкретных криптографических объектов часто приводит к решению систем булевых уравнений вида оь х) = С\, V для некоторого неизвестного вектора х. Для произвольной булевой функции / такие системы плохо решаются. Предположим, что для некоторой булевой функции д(а, х) с достаточно большой вероятностью выполняется равенство 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П) показывается, что существуют более устойчивые функции, для которых расстояние до класса АЕ\п заведомо больше и равно 14 • 9"-1

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

Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Омаров, Рустам Рамазанович

Заключение

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

Приведем список основных результатов.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Омаров, Рустам Рамазанович, 2012 год

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

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

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

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

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

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

7. Логачёв О. А., Сальников А. А. Ященко В. В., Булевы функции в теории кодирования и криптологии, МЦНМО, Москва, 2004. 470 с.

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

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

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

11. Agievich 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.

12. Biham E., Shamir A., Differential cryptanalysis of DES-hke cryptosystems// J. Cryptology, 1991. V. 4, N1. 3-72.

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

14. Courtois N., 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).

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

16. Meier W., Staffelbach O. Nonlmearity criteria for cryptographic functions // LNCS. 1990. V. 434. 549-562.

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

18. Sarkar P. MaitraS., Nonlmearity bounds and constructions of resilient Boolean functions// CRYPTO'2000, LNCS V. 1880, Springer-Verlag, 2000. 515-532.

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

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

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

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

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

24. Алексеев В. Б., Омаров Р. Р., "О приближении одного класса максимально-нелинейных булевых функций почти аффинными функциями", Труды VIII

25. Международных Колмогоровских чтений, Изд-во ЯГПУ, Ярославль, 2010, 98104

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

27. Омаров P.P., "О расстояниях от максимально-нелинейных функций до некоторого класса булевых функций", Материалы XI Международного семинара «Дискретная математика и ее приложения», Изд-во мех.-мат. факультета МГУ, Москва, 2012, 425428

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

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