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

Лобанов, Михаил Сергеевич

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

Лобанов, Михаил Сергеевич АВТОР

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

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

2009 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

Автореферат диссертации на тему "О соотношениях между алгебраической иммунностью и нелинейностью булевых функций."

09-6

1499

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

Лобанов Михаил Сергеевич

О СООТНОШЕНИЯХ МЕЖДУ

АЛГЕБРАИЧЕСКОЙ ИММУННОСТЬЮ И

НЕЛИНЕЙНОСТЬЮ БУЛЕВЫХ ФУНКЦИЙ

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

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

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

АВТОРЕФЕРАТ

Москва - 2009

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

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

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

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

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

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж) Автореферат разослан 20 октября 2009 г.

Ученый секретарь диссертационного совета Д501.001.84 при МГУ

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

Актуальность темы.

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

Многие потоковые шифры состоят из линейной части, порождающей последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной комбинирующей функции /, которая порождает выходную последовательность по данным линейным входам. Исследования криптографической устойчивости таких шифров большей частью сводятся к исследованию нелинейной функции /, в частности, к исследованию этой функции с точки зрения того, удовлетворяет или не удовлетворяет она некоторым критериям, необходимым для того, чтоб успешно противостоять различным криптографическим атакам. Часто эти критерии конфликтуют между собой.

Пусть / является булевой функцией над Известно, что /

единственным образом представляется полиномом. Степенью булевой функции называется длина самого длинного слагаемого в ее полиноме (количество переменных в этом слагаемом), обозначение deg(/). Булева функция д над F? называется аннигилятором булевой функции / над Fg, если fg — 0.

Алгебраической иммунностью AJ(f) булевой функции / над F£ называется степень булевой функции д над F£, где д не равная тождественно нулю функция с минимальной степенью, такал что fg = 0 или (/ + 1)с/ = 0.

Известно, что для любой / над F2" выполнено AI(f) <

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

Н.Куртуа и В.Майер3 показали, что указанные соотношения низкой

'N.Courtois and W.Meier. Algebraic attacks on stream ciphers with lineal feedback // Anvances in cryptoi-ogy, EUROCRYPT 2003. — Berlin/Heidelberg: Springer Verl., 2003 , P. 345-359. (Lecture Notes in Computer Science; Vol. 2656).

2N.Courtois and W.Meier. Algebraic attacks on stream ciphers with linear feedback // Anvances in cryptol-ogy, EUROCRYPT 2003. — Berlin/Heidelberg: Springer Verl., 2003. - P. 345-359. (Lecture Notes in Computer Science; Vol. 2656).

3N.Courtois and W.Meier. Algebraic attacks on stream ciphers with linear feedback // Anvances in cryptol-ogy, EUROCRYPT 2003. — Berlin/Heidelberg: Springer Verl., 2003. - P. 345-359. (Lecture Notes in Computer Science; Vol. 2650).

степени и, соответственно, успешные алгебраические атаки существуют для некоторых хорошо известных шифров, которые иммунны по отношению ко всем другим известным атакам. В частности, было доказано, что соотношение малой степени существует для шифров, использующих комбинирующую функцию / с малым количеством входов. Эти соотношения малой степени можно получить, получая многочлены малой степени, содержащие / в качестве делителя, т.е. умножая функцию / на подходящие функции д малой степени так, чтобы произведение / • д снова было малой степени. Если для функции / такая функция д существует (причем f не обязательно должна иметь малое количество входов), то алгебраическую атаку молено успешно провести. Таким образом, изучение булевых функций с точки зрения существования функций малой степени, содержащей данную в качестве делителя, имеет как теоретический, так и практический интерес.

Н.Куртуа и В.Майером было предложено три разновидности такого рода атак. Позже В.МаЙер, Е.Пасалич и К.Карле4 свели эти три вида к двум и ввели новый термин - алгебраическая иммунность. Те же авторы доказали, что если алгебраическая иммунность достаточно высока, то алгебраическим атакам можно успешно противостоять.

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

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

4W.Meier, E.Pasalic and C.Cariet. Algebraic attacks and decomposition of Boolean functions // Advances in Cryptology — EUROCRYPT 200-1. - Berlin/Heidelberg: Springer Verl., 2004. - P. 474-401. (Lecture Notes in Computer Science; Vol. 3027).

5T.Johansson, F.Jönsson. Fast correlation attacks through reconstruction of linear polynomials // Advunced in Cryptology: Crypto 2000 (Santa Barbara, California, USA, August 20-24, 2000). - Springer-Verlag, 2000. -P. 300-315. (Lecture Notes in Computer Science; Vol. 1880)

"A.Canteaut, M.IVabbia. Improved fast correlation attacks using Parity-check equations of weight 4 and 5 // Eurocrypt 2000 (Bruges, Belgium, May 14-18, 2000). — Springer-Verlag, 2000. - P. 573-588. (Lecture Notes in Computer Science; Vol. 1807).

7W.Meier, E.Pasalic and C.Carlet. Algebraic attacks and decomposition of Boolean fiuictions // Advances in Cryptology - EUROCRYPT 2004. •- Berlin/Heidelberg: Springer Vorl., 2004. - P. <174-491. (Lecture Notes in Computer Science; Vol. 3027).

порядка 2" *) и оптимальную алгебраическую степень8,9'10'11, имеют при этом достаточно низкую алгебраическую иммунность и не могут противостоять алгебраическим атакам.

Расстояние между булевыми функциями fr и /2 определяется как

Нелинейностью г-го порядка nlr(f) булевой функции / над F£ называется min d(f,l). Нелинейностью nl(f) функции f называется

deg(¡)<r ' J

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

Отметим, что на языке теории кодирования нелинейность г-го порядка функции — это расстояние функции до RM(r, п) кода Рида-Маллера г-го порядка.

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

С точки зрения криптоанализа от булевой функции, используемой в качестве фильтра в потоковом шифре, надо требовать не только достаточно высокой нелинейности первого порядка, но и высокой нелинейности других порядков. В этом можно убедиться по работам Н.Куртуа12, Ж.Голича13, Т.Иваты и К.Куросавы14, Л.Кнудсена и М.Робшау16, У.Маурера16, В.Миллана17.

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

F.Dillon. Elementary Hadamard Difference Sets // Ph. D. thesis, University of Maryland, "USA, 1974,

9P.Camion, C.Carlet, P.Charpin, N.Sendrier. On correlation-immune functions // Eurocrypt'91 (Brighton, UK, April 8-11, 1991). - Springcr-Verlag, 1991. - P. 86-100.

10C.Carlet. A larger class of cryptographic Boolean functions via a study of the Maiorana^McFarland Construction // Crypto 2002 (Santa Barbara, California, USA, August 18-22, 2002). — Springer-Verlag, 2002. -P. 549-564. (Lecture Notes in Computer Science; Vol. 2442).

uE.Pasalic. Degree optimized resilient Boolean functions from Maiorana-McFarland class // in 9-th IMA Conference on Cryptography and Coding, 2003.

nN.Courtois. Higher order corralation attacks, XL algorithm and cryptanalysis of Toyocrypt // Proceedings of ICISC 2002. - LNCS 2587. - P. 182-199.

"J.Golic. Fast low order approximation of cryptographic funtions // Proceedings of EUROCRYPT'96. — LNCS 1070, 1996. - P.268-282.

"T.Iwata, K.Kurosawa. Probabilistic higher order differential attack and higher order bent function // Proceedings of ASIACRYPT'99. - LNCS 1716, 1999. - P.62-74.

15L.R.Knudsen, M.J.B.Robshaw. Non-linear approximations in linear cryptanalysis // Proceedings of EURO-CRYPT'96. — LNCS 1070, 1996. - P. 224-236.

I6U.M.Maurer. New approaches to the design of self-synchronizing stream ciphers // Proceedings of EUROCRYPT'91. - LNCS 547, 1991. - P. 458-471.

"W.Millan. Low order approximation of cipher functions // Cryptographic Policy and Algorithms. — LNCS

1029, 1996. - P. 144-155.

Получение таких оценок дает' не только информацию о взаимосвязи этих двух свойств, но валено еще и по следующей причине. Если вопросы связанные с нелинейностью nl[f) — nl\(f) достаточно хорошо изучены, и существует аппарат коэффициентов Уолша, который позволяет1 ее вычислять, то с нелинейностью более высоких порядков асе обстоит заметно хуже. Про nl,.(f) при г > 2 мало что известно. Стоит упомянуть наилучшую, как нам известно, на этот момент верхнюю асимптотическую оценку из работы К.Карле и С.Менаже18.

В работе Ж.Коэна, И.Хонкалы, С.Лицына и А.Лобстейна19 доказана также достаточно сильная нижняя оценка, которая, правда, тоже носит асимптотический характер и поэтому ничего не дает для оценки нелинейности r-го порядка при г > 1 для конкретных функций.

Эффективных алгоритмов подсчета нелинейности порядков выше перпого тоже, насколько нам известно, пока не предложено. Алгоритм Г.Кабатинского и К.Тавернье20 и его модификации21,22 работают только при г — 2 и п < 13.

В свете выше изложенного, получение как можно более сильных нижних оценок нелинейности r-го порядка через значение алгебраической иммунности приобретает особую важность. Отметим, что в работах Ф.Дидье, Ж.Тиллича23 и В.Баева24'25 был предложен ряд алгоритмов подсчета алгебраической иммунности, а в работах Ф.Армкнехта, М.Краузе26, А.Брэкена, В.Пренеля27, К.Карле28, Д.Далаи и Ш.Майтры29 построено несколько семейств функций, имеющих максимально возможную алгебраическую иммунность

iaC.Carlet, S.Mesnager. Improving the upper bounds on the covering radii of binary Reed-Muller codes // IEEE TYausactions on Information Theory, 2006.

'"G.Cohen, I.Honkalft, S.Litsyn, A.Lobstoin. Covering codes. North-Holland, 1997.

20G.Kabatiansky, C.Tavernier. List decoding of second order Reed-Muller codes // In Proc. 8<л Intern. Simp. Comm. Theory and Applications (Ambelside, UK, July 2005).

21I.Dumer, G.Kabatiansky, C.Tavernier. List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity // Proceedings of ISIT 2006. Seattle, USA.

22R.Fourquet. Una FFT adaptee au decodage par lists dans les codes de Reed-Muller d'ordres 1 et 2 // Master-thesis of the University of Paris VIII, Thates communication, Bols Colombes, 200fi.

23F,Didier, J.P.Tillich. Computing the algebraic immunity efficiently // Fast softwware encryption 200(1, LNCS 4047, 200(5. - P. 359-374.

24B.B Баев. Некоторые нижние оценки на алгебраическую иммунность функций, заданных сноими след-формами // Пробл. передачи информ. — 2008. — Т. 44, вып. 3. — С. 81-104.

25В.В Баев. Усовершенствованный алгоритм поиска аннигиляторов низкой степени дли многочлена Жегалкина // Дискретная математика. — 2007. — Т. 19, нын. 4. — С. 132-138.

26F.Armlmecht, M.Krause. Constructing single- and multi-output boolean functions with maximal algebraic immunity // International conference on automata, language and programing 2(K)(i. — LNCS 4052, Springer, 2006.- Part II. - P. 180-191.

27A.Braeken, B.Preneel. On the algebraic immunity of symmetric boolean functions // Indocrypt 2005. — LNCS 3797, Springer, 2005. - P. 35-48.

28C.Carle. A method of construction of balanced functions with optimum algebraic immunity // Cryptolngy ePrint archive, http://eprint.iacr.org/2006/149.

29D.K.Dalai, S.Maitra. Balanced Boolean functions with (more than) maximum algebraic immunity // Oryp-tology ePrint archive, http://eprint.iacr.org/2006/434.

Цель работы.

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

Научная новизна.

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

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

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

3. Получена точная нижняя оценка нелинейности второго порядка (г = 2) через значение алгебраической иммунности.

4. Получена новая нижняя оценка нелинейности г-го порядка через значение алгебраической иммунности при всех г.

Основные методы исследования.

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

Теоретическая и практическая ценность работы.

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

Апробация работы.

Результаты диссертации докладывались на следующих научно-исследовательских семинарах и конференциях:

® Семинар "Булевы функции в криптологии"под руководством к.ф.-м.н. О.А.Логачева и к.ф.-м.н., доцента Ю.В.Тарашгакова (2005-2009).

® Семинар "Математические вопросы кибернетики "под руководством д.ф.-м.н., профессора О.М.Касим-Заде (21 марта 2008).

• Вторая международная конференция по проблемам безопасности и противодействия терроризму (МГУ, 25-26 октября 2006).

• VI молодежная научная школа по дискретной математике и ее приложениям (Москва, 16-21 апреля, 2007).

® IX международный семинар "Дискретная математика и ее приложения " (Москва, 18-23 июня, 2007).

• Ежегодная научная конференция "Ломоносовские чтения"(МГУ, апрель 2007)

® Международная конференция "NATO Advanced Study Institute on Boolean Punctions in Cryptology and Information Security" (Звенигород, сентябрь 2007).

в XVII международная школа-семинар "Синтез и сложность управляющих систем "(Новосибирск, 27 октября - 1 ноября, 2008).

в Международная конференция "Современные проблемы математики, механики и их приложений"(Москва, 30 марта - 02 апреля, 2009).

Публикации.

Основное содержание диссертации было опубликовано в 8 работах, список которых приведен в конце автореферата [1]—[8].

Структура и объем диссертации.

Диссертация состоит из введения, 6 глав и списка литературы. Объем диссертации — 64 страницы, библиография включает 47 наименований.

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

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

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

Определение 1. Алгебраической иммунностью AI(f) булевой функции / над F£ называется степень булевой функции д над F2", где д не равная тождественно нулю функция с минимальной степенью, такая что fg = 0 или (/ + - 0.

Определение 2. Нелинейностью г-го порядка nlr(f) булевой функции / над F2" называется min d(f, I). Нелинейностью nl(f) функции / называется

deg(i)<r

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

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

Во второй главе проблема получения как можно более сильных нижних оценок нелинейности г-го порядка через значение алгебраической иммунности функции полностью сводится к задаче определения размерности некоторых подпространств Bk{h) = {д(хь..., ж„)| deg(g) < к, deg(gh) < к}.

Теорема 1 Пусть f(xi, ...,£„) имеет AI(f) = к, тогда

nlrif) > min dim(Bk-i(g)).

deg{g)<r

Кроме того, при к < существует функция /0, AI{f0) = к, для которой п1 г (/о) = min diin(Bk~i{g)).

deg{g)<r

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

из работы группы индийских исследователей30, а также оценку

АГШ-г-1

nlrU) > 2

¡=о 4 г

из работы К.Карле31 и оценку, полученную независимо автором [3] и С.Менаже32:

АДД-г-1 , ч АЦП-*-1 / \

»ш> Е (")+ Е ("Г> «

<=0 4 J ¿=Я/(/)-2г V '

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

Третья глава посвящена случаю обычной нелинейности nl(f). В главе доказана оценка

АГ(/Ь2 ,. v

nl(f)=nl1(f)= min d(f,l)>2 ]Г Г , (2)

deg(l)<l ^ W

и построено семейство функций

(О, если wt(xi,.. ., хп) < к, 1, если wt{x 1, ...,хп)>п~ к, ii, если к < wt(xi,... ,хп) <п — к,

на которых оценка достигается при всех допустимых значениях параметров п и AI{f). А именно, доказано, что

AI(fn,k) = к

к-2 , , (П — 1

nl(in,k)=2Y]

\ Z

Также в третьей главе мы доказываем следующее утверждение:

30D .K.Dalai, K.C.Gupta and S.Maitra. Results on Algebraic Immunity for Cryptographically Significant Boolean Functions // Indocrypt 2004 (Chennal, India, December 20-22, 2004) — Berlin/Heidelberg: Springer Verl., 2004, - P. 92-106.

3IC.Carlet. Oil the higher order nonlinearities of algebraic immune functions // CRYPTO 2006. — Berlin/Heidelberg: Springer, 2006. — P. 584-601. (Lecture Notes in Computer Science; Vol.4117).

32S.Mesnager. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity. Cryptology ePrint archive(http://eprint.Iacr.org/), Report 2007/117.

Следствие 8. Пусть f{x\,..., ж„) булева функция над F£ и AI(f) = к, к < тогда равенство в неравенстве (2) может достигаться не более чем на одной линейной функции I.

Там же показываем, что для функции /2fc+i,i:+i равенство в неравенстве (2) достигается сразу на нескольких линейных функциях I.

Четвертая глава посвящена получению оценки на нелинейность второго порядка.

В начале вводятся определения множества Sau...iari(k) и (а1;...,а9)-бесповторного полинома:

Определение 6. Пусть есть набор целых чисел ai > a2 > ... > а,, > 0, таких что Y11=iai ~ п> тогда двоичному набору х = (ej, ... ,х„) длины п можно сопоставить набор из целых чисел: (si(x),... ,sq(x)) =

*<.Е^Г'-i• • •.E^^tX-i+i0бозначим чеРет

множество двоичных наборов х длины п, таких что st(x) — 0 при некотором tj. < q, 0 < Si(i) < tti при г < tg и также к — а^ < wt(x) < к.

Определение 7. Полином, в котором каждая переменная входит не более чем в один моном, будем называть бесповторным. Если полином имеет вид

где а\ > а2 > . ■ ■ > aq, то будем его называть (сц,..., а9)-бесповторным.

Для бесповторного полинома доказана теорема, которая для довольно широкого класса функций сводит проблему вычисления размерности пространства Bk(f) к несложному комбинаторному подсчету:

Теорема 2 Пусть f(xj,,.., хп) — это (ai,..., aq)-бесповторный полином. Тогда

dvm{Bk{f)) = Е (") - ^.....«.(*)!■

Известно33,34, что любую квадратичную булеву функцию можно аффинным преобразованием перевести в функцию с бесповторным полиномом. Благодаря этому факту и теоремам 1 и 2, доказывается точная нижняя оценка на нелинейность второго порядка:

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

31F.J.McWilliams, N.J.A.Sloane. The Theory of Error Correcring Codes. New York: North-Holland, 1977. -760 p.

Теорема 3 Пусть /(хг, .. .,хп) умеет А1(/) = к, тогда

Кроме того, при к < [|] существует функция /о, А1(/п) = к, для которой

В пятой главе доказана оценка, которая является на настоящий момент рекордной для нелинейностей третьего и выше порядков:

Теорема 4 Пусть А1(д) = к: тогда

Доказательство этой теоремы опирается на доказанное нами утверждение:

Утверждение 17. Пусть ¡(х\,..., а;„) булева функция, deg(f) — к > 1. Тогда аффинными преобразованиями ее можно привести к многочлену, который будет содержать моном Х1Х2 ■ ■ -Хк и любой другой моном которого будет содержать не более чем к —2 аз переменных хг,х2,..., Хк-

В шестой главе для конкретных значений п, А1(/) и г — 2 сравниваются оценки (1), (4) и (3). Из преведенных сравнений видно, что в случае нелинейности второго порядка оценка (3) заметно сильнее.

Также для конкретных значений п, А1(/) и г > 3 сравниваются оценки (1) и (4). Оказывается, что вторая оценка существенно лучше.

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

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

Список публикаций по теме диссертации.

[1] М.С.Лобанов. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика, — 200б. — Т. 18, вып. 3. - С. 152-159.

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

13] М.С.Лобанов. Оценка нелинейности высоких порядков булевой функции через значение ее алгебраической иммунности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля, 2007). Часть 2. — М.: Институт прикладной математики РАН, 2007. - С. 11-16.

[4| М.С.Лобанов. Новый подход к оценке нелинейности высоких порядков булевой функции через значение ее алгебраической иммунности // Материалы IX международного семинара "Дискретная математика и ее приложения "(Москва, 18-23 июня, 2007). — М.: Издательство механико-математического факультета МГУ, 2007. — С. 434-437.

[5] М.С.Лобанов. Новая нижняя оценка нелинейности высокого порядка через алгебраическую иммунность // Материалы XVII международной школы-семинара "Синтез и сложность управляющих систем "(Новосибирск, 27 октября - 1 ноября, 2008). — Новосибирск: Издательство института математики, 2008. — С. 95-98.

[6] М.С.Лобанов. Об оценках нелинейности высоких порядков через алгебраическую иммунность // Материалы международной конференции "Современные проблемы математики, механики и их приложений "(Москва, 30 марта - 02 апреля, 2009). — М: Издательство "Университетская книга", 2009. - С. 395.

[7] М.С.Лобанов. Неулучшаемая оценка нелинейности функции через значение алгебраической иммунности // Материалы II международной конференции по проблемам безопасности и противодействия терроризму (МГУ, 25-26 октября 2006). - М.: МЦНМО, 2007. - С. 210-217.

[8] M.Lobanov. Tight bounds between nonlinearity and algebraic immunity of high orders // Boolean fonctions in cryptology and information security. — 2008. - IOS Press. - P. 296-305. (NATO Science for Peace and Security Sériés D: Information and Communication Security - Vol. 18)

Подписано в печать О9

Формат 60x90 1/16. Усл. печ. л. 0,75 Тираж /00 экз. Заказ 33

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

2008154857

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

Введение

Глава 1. Предварительные сведения

Глава 2. Сведение задачи к оценке размерности определенных линейных пространств булевых функций

Глава 3. Точная нижняя оценка для нелинейности (г — 1) и построение функций, на которых она достигается

Глава 4. Алгебраическая иммунность и нелинейность второго порядка

4.1 Точное значение сИт(Вк(/)) для бесповторных полиномов

4.2 Точное соотношение между алгебраической иммунностью и нелинейностью второго порядка.

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

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

Для того, чтобы противостоять этим атакам (таким, как атакам Берлекэм-па-Мэсси, различным типам корреляционных и линейных атак [47, 38, 20] и алгебраической атаке (см. [26])), функция должна удовлетворять следующим критериям:

1. Уравновешенность. Булева функция должна выдавать нули и единицы с одинаковой вероятностью.

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

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

4. Высокая алгебраическая степень.

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

Также важными критериями являются низкая автокорреляция, простая схемная реализация и т.д.

Критерии зачастую конфликтуют друг с другом, выяснению их взаимосвязей посвящена обширная литература. Например, упомянем работу [13], в которой приведена последовательность функции с высокой корреляционой иммунностью, высокой нелинейностью и неплохой алгебраической иммунностью.

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

Пусть / является булевой функцией над .Кр. Известно, что / единственным образом представляется полиномом. Степенью булевой функции называется длина самого длинного слагаемого в ее полиноме (количество переменных в этом слагаемом). Булева функция д над ^ называется аннигилятором булевой функции / над Р2П, если /д = 0. Очевидно, что аннигиляторы / образуют линейное подпространство в пространстве всех булевых функций от п переменных.

Определение 1 Алгебраической иммунностью А1(/) булевой функции / над ^ называется степень булевой функции д над , где д не равная тождественно нулю функция с минимальной степенью, такая что $д = 0 или (/ + 1 )д = 0.

Известно [26, 42], что для любой / над выполнено

AI(f)< if"!- (1)

В [29] доказано, что доля уравновешенных функций / от п переменных, для которых выполнены неравенства ^ — Inn < AI(f) < стремится к единице при п —> оо. То есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п/2 — максимально возможный.

Алгебраическая иммунность - это способность противостоять разного рода алгебраическим атакам на регистры сдвига с линейной обратной связью (linear feedback shift registers, LFSR). Эти атаки впервые были предложены в [26]. Они раскрывают секретный ключ путем решения системы уравнений, зависящих от многих переменных. Данные системы уравнений описывают соотношения между битами ключа/состояния и выходными битами / (комбинирующей функции для LFSR). Если найдено такое соотношение низкой степени, алгебраические атаки очень эффективны ([28]).

В [26] показано, что указанные соотношения низкой степени и, соответственно, успешные алгебраические атаки существуют для некоторых хорошо известных шифров, которые иммунны по отношению ко всем другим известным атакам. В частности, доказано, что соотношение малой степени существует для шифров, использующих комбинирующую функцию / с малым количеством входов. Эти соотношения малой степени можно получить, получая многочлены малой степени, содержащие / в качестве делителя, т.е. умножая функцию / на подходящие функции д малой степени так, чтобы произведение f-g снова было малой степени. Если для функции / такая функция д существует (причем / не обязательно должна иметь малое количество входов), то алгебраическую атаку можно успешно провести. Таким образом, изучение булевых функций с точки зрения существования функций малой степени, содержащей данную в качестве делителя, имеет как теоретический, так и практический интерес.

В [26] предложено три разновидности такого рода атак. В [42] авторы сводят эти три вида к двум и вводят новый термин - алгебраическая иммунность. Авторы доказывают, что если алгебраическая иммунность достаточно высока, то алгебраическим атакам можно успешно противостоять.

Требование высокой алгебраической иммунности может конфликтовать с требованиями удовлетворения остальным критериям. В [42] авторы показали, что, например, функции класса Майораны-Макфарланда, имеющие высокую устойчивость, высокую нелинейность (асимптотически порядка 2n1) и оптимальную алгебраическую степень ([33, 18, 23, 46], - имеют при этом достаточно низкую алгебраическую иммунность и не могут противостоять алгебраическим атакам.

Весом wt(x) набора х из называется число единиц в х. Расстояние между булевыми функциями f\ и /2 определяется как d{f\. /2) =| {х Е .F21 j h(x) ^ f2(x)} \.

Определение 2 Нелинейностью г-го порядка nlr(f) булевой функции f над называется min deg(Z)<r

Нелинейностью nl(f) функции / называется расстояние между / и множеством аффинных функций, т. е. нелинейность первого порядка.

Отметим, что на языке теории кодирования нелинейность r-го порядка d(fj). функции - это расстояние функции до ЯМ (г, п) кода Рида-Маллера г-го порядка.

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

Получение таких оценок дает не только информацию о взаимосвязи этих двух свойств, но важно еще и по следующей причине. Если вопросы связанные с нелинейностью п1(/) = Ы^) достаточно хорошо изучены и существует аппарат коэффициентов Уолша, который позволяет ее вычислять, то с нелинейностью более высоких порядков все обстоит заметно хуже. Про п1г(/) при г > 2 мало что известно. Стоит упомянуть наилучшую, как нам известно, на этот момент верхнюю оценку из [24], которая имеет асимптотический вид: пЦЛ < 2П-1 - ^(1 + у/2)г~22п'2 + 0{пг~2).

Доказана также достаточно сильная нижняя оценка [25], которая, правда, тоже носит асимптотический характер и поэтому ничего не дает для оценки нелинейности г-го порядка при г > 1 для конкретных функций.

Эффективных алгоритмов подсчета нелинейности порядков выше первого тоже, насколько автору известно, пока не предложено. Интересный алгоритм и его модификации, предложенные в [34, 36, 39], работают только при г = 2 и п < 13.

В свете выше изложенного, получение как можно более сильных нижних оценок нелинейности г-го порядка через значение алгебраической иммунности приобретает особую важность. Отметим, что в [11, 12, 42, 30] был предложен целый ряд алгоритмов подсчета алгебраической иммунности, а в [16, 17, 21, 31] построено несколько семейств функций, имеющих максимально возможную алгебраическую иммунность .

В работе [32] был доказан результат, эквивалентный следующей оценке на нелинейность г-ого порядка:

Позже в [1] автором была доказана нижняя оценка нелинейности (г=1) функции через значение ее алгебраической иммунности:

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

Еще позднее К.Карле в [22] обобщил доказанную автором оценку (3) на случай других г:

Отметим, что ни одна из двух приведенных выше оценок (2) и (4) для нелинейности г-ого порядка не влечет другую.

В работах [43] и [3] была доказана следующая оценка

А1(Л-г-1 / . А1(/)-г-1 / ч е (:)+ Е (п7. (5) г=0 4 7 г=АГ(/)-2г 4 У более сильная, чем (2) и (4).

В работе [2] была доказана точная оценка для нелинейности второго порядка: п- 2г — 1 \ г=0 4 ' г=0 \ \J У / которая достигается при всех допустимых значениях параметров.

В 2008 году автором [5] получена новая оценка нелинейности г-го порядка при г > 2, которая сильней всех ранее известных оценок: АГ(/)—г—1 , ч А1(Л-г-1 , х АГ(Я-г-2 nfe(/)> Е (")- Е < п / n V

1 / \ 1 / \ U ' ' /

Е I + Е Т)+а Е i—П N / И ГС f Г)„ \ / Л ГС О- 1 \ п — г — 2 г г=0 4 ' i=AI(f)—2r 4 ' г—Л/(/)—2r—1

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

Во второй главе проблема получения как можно более сильных нижних оценок нелинейности r-го порядка через значение алгебраической иммунности функции полностью сводится к задаче определения размерности некоторых подпространств Bk(h) = {д{хi,., жп)| deg(g) < /с, deg(gh) < Теорема 1 Пусть f(xi,., хп) имеет AI(f) = к, тогда nlr(f) > min dim(Bk-i(g)). deg(g)<r

Кроме того, при к < существует функция /о, А/(/0) = к, для которой nlr(fo) = min dim(Bk-i(g)). deg(g)<r

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

Третья глава посвящена случаю обычной нелинейности п/(/). В главе доказана оценка и построено семейство функций ■ • •, хп), на которых оценка достигается при всех допустимых значениях параметров п и АГ(/).

В четвертой главе получена оценка на нелинейность второго порядка которая тоже достигается при всех допустимых значениях параметров. Эти результаты удалось получить благодаря сведению проблемы нахождения min dim(Bk~i{g)) из теоремы 1 к задаче комбинаторного подсчета deg{g)<r в случае, когда д является бесповторным полиномом, и аффинной классификации квадратичных булевых функций, которая утверждает, что любую квадратичную булеву функцию можно аффинным преобразованием превратить в бесповторпый полином.

Пятая глава посвящена получению оценки которая при г > 3 является рекордной на настоящий момент.

На страницах 49-51 шестой главы можно найти сравнение оценки 6 с оценками (7) и (5) для конкретных п, и АГ(/) и г = 2.

На страницах 52-57 шестой главы можно найти сравнение оценок (7) и (5) для конкретных п, АГ(/) и г > 3.

Результаты автора по теме диссертации опубликованы в работах [1]—[10].

AI(f)—r—l

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Лобанов, Михаил Сергеевич, Москва

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

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

3. М.С.Лобанов. Неулучшаемая оценка нелинейности функции через значение алгебраической иммунности // Материалы II международной конференции по проблемам безопасности и противодействия терроризму (МГУ, 25-26 октября 2006). М.: МЦНМО, 2007. - С. 210-217.

4. M.Lobanov. Tight bound between nonlinearity and algebraic immunity. Cryptology ePrint archive(http://eprint.iacr.org/), Report 2005/437.

5. M.Lobanov. Tight bounds between algebraic immunity and nonlinearities of high orders. Cryptology ePrint archive(http://eprint.iacr.org/), Report 2007/444.

6. B.B Баев. Некоторые нижние оценки на алгебраическую иммунность функций, заданных своими след-формами // Пробл. передачи информ. 2008. - Т. 44, вып. 3. - С. 81-104.

7. В.В Баев. Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина // Дискретная математика. — 2007. Т. 19, вып. 4. - С. 132-138.

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

9. Ю. В. Таранников, Д. П. Кириенко. Спектральный анализ коррелляционно-иммунных функций высокого порядка // Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем". — Москва, 2001. — Ч. 2. — С.177-189.

10. F.Armknecht, M.Krause. Constructing single- and multi-output boolean functions with maximal algebraic immunity // International conference on automata, language and programing 2006. — LNCS 4052, Springer, 2006.— Part II. P. 180-191.

11. A.Braeken, B.Preneel. On the algebraic immunity of symmetric boolean functions // Indocrypt 2005. LNCS 3797, Springer, 2005. - P. 35-48.

12. P.Camion, C.Carlet, P.Charpin, N.Sendrier. On correlation-immune functions // Eurocrypt'91 (Brighton, UK, April 8-11, 1991). — Springer-Verlag, 1991. P. 86-100.

13. A. Canteaut. Open problems related to algebraic attacks on stream ciphers // International Workshop (WCC 2005) (Bergen, March 14-18, 2005) —Berlin/Heidelberg: Springer Verl., 2005. — P. 120-134. (Lecture Notes in Computer Science; Vol. 3969).

14. A.Canteaut, M.Trabbia. Improved fast correlation attacks using Parity-check equations of weight 4 and 5 // Eurocrypt 2000 (Bruges, Belgium, May 14-18, 2000). — Springer-Verlag, 2000. — P. 573-588. (Lecture Notes in Computer Science; Vol. 1807).

15. C.Carle. A method of construction of balanced functions with optimum algebraic immunity / / Cryptology ePrint archive, http://eprint.iacr.org/2006/149.

16. C.Carlet. On the higher order nonlinearities of algebraic immune functions // CRYPTO 2006. Berlin/Heidelberg: Springer, 2006. - P. 584-601. (Lecture Notes in Computer Science; Vol.4117).

17. C.Carlet, S.Mesnager. Improving the upper bounds on the covering radii of binary Reed-Muller codes // IEEE Transactions on Information Theory, 2006.

18. G.Cohen, I.Honkala, S.Litsyn, A.Lobstein. Covering codes. North-Holland, 1997.

19. N.Courtois and W.Meier. Algebraic attacks on stream ciphers with linear feedback // Anvances in cryptology, EUROCRYPT 2003. — Berlin/Heidelberg: Springer Verl., 2003. — P. 345-359. (Lecture Notes in Computer Science; Vol. 2656).

20. N.Courtois. Higher order corralation attacks, XL algorithm and cryptanalysis of Toyocrypt // Proceedings of ICISC 2002. LNCS 2587. — P. 182-199.

21. F.Didier. A new bound on the block error probability after decoding over the erasure channel // IEEE Trans, on Information Theory, vol. IT-52, e 10, 2006.

22. F.Didier, J.P.Tillich. Computing the algebraic immunity efficiently // Fast softwware encryption 2006, LNCS 4047, 2006. P. 359-374.

23. D.K.Dalai, S.Maitra. Balanced Boolean functions with (more than) maximum algebraic immunity / / Cryptology ePrint archive, http://eprint.iacr.org/2006/434.

24. D.K.Dalai, K.C.Gupta and S.Maitra. Results on Algebraic Immunity for Cryptographically Significant Boolean Functions // Indocrypt 2004 (Chen-nai, India, December 20-22, 2004) — Berlin/Heidelberg: Springer Verl., 2004. P. 92-106.

25. J.F.Dillon. Elementary Hadamard Difference Sets // Ph. D. thesis, University of Maryland, USA, 1974.

26. I.Dumer, G.Kabatiansky, C.Tavernier. List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity // Proceedings of ISIT 2006. Seattle, USA.

27. J.Golic. Fast low order approximation of cryptographic funtions // Proceedings of EUROCRYPT'96. LNCS 1070, 1996. - P.268-282.

28. R.Fourquet. Une FFT adaptee au decodage par liste dans les codes de Reed-Muller d'ordres 1 et 2 // Master-thesis of the University of Paris VIII, Thales communication, Bois Colombes, 2006.

29. T.Iwata, K.Kurosawa. Probabilistic higher order differential attack and higher order bent function // Proceedings of ASIACRYPT'99. — LNCS 1716, 1999. P.62-74.

30. G.Kabatiansky, C.Tavernier. List decoding of second order Reed-Muller codes //In Proc. 8th Intern. Simp. Comm. Theory and Applications (Ambelside, UK, july 2005).

31. L.R.Knudsen, M.J.B.Robshaw. Non-linear approximations in linear crypt-analysis // Proceedings of EUROCRYPT'96. LNCS 1070, 1996. - P. 224236.

32. U.M.Maurer. New approaches to the design of self-synchronizing stream ciphers // Proceedings of EUROCRYPT'91. LNCS 547, 1991. - P. 458-471.

33. W.Meier, E.Pasalic and C.Carlet. Algebraic attacks and decomposition of Boolean functions // Advances in Cryptology — EUROCRYPT 2004. — Berlin/Heidelberg: Springer Verl., 2004. — P. 474-491. (Lecture Notes in Computer Science; Vol. 3027).

34. S.Mesnager. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity. Cryptology ePrint archive(http://eprint.iacr.org/), Report 2007/117.

35. F.J.McWilliams, N.J.A.Sloane. The Theory of Error Correcring Codes. New York: North-Holland, 1977. 760 p.

36. W.Millan. Low order approximation of cipher functions // Cryptographic Policy and Algorithms. LNCS 1029, 1996. - P. 144-155.

37. E.Pasalic. Degree optimized resilient Boolean functions from Maiorana-McFarland class //in 9-th IMA Conference on Cryptography and Coding, 2003.

38. T.Siegenthaler. Decrypting a Class of Stream Ciphers Using Ciphertext Only // IEEE Transactions on Computer. — V. C-34, No 1, Jan. 1985. — P. 81-85.