WWW.DISSERS.RU

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

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

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

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

УДК 519.1, 519.7 Лобанов Михаил Сергеевич О соотношениях между алгебраической иммунностью и нелинейностью булевых функций 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Москва 2009

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Шевченко Валерий Николаевич кандидат физико-математических наук Логачев Олег Алексеевич

Ведущая организация: Институт математики имени С.Л. Соболева СО РАН,

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

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

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

Ученый секретарь диссертационного совета Д501.001.84 при МГУ доктор физико-математических наук, профессор А.О. Иванов

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

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

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

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

n Пусть f является булевой функцией над F2. Известно, что f единственным образом представляется полиномом. Степенью булевой функции называется длина самого длинного слагаемого в ее полиноме (количество переменных в этом слагаемом), обозначение deg(f). Булева n n функция g над F2 называется аннигилятором булевой функции f над F2, если fg = 0.

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

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

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

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).

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).

Н.Куртуа и В.Майер3 показали, что указанные соотношения низкой степени и, соответственно, успешные алгебраические атаки существуют для некоторых хорошо известных шифров, которые иммунны по отношению ко всем другим известным атакам. В частности, было доказано, что соотношение малой степени существует для шифров, использующих комбинирующую функцию f с малым количеством входов. Эти соотношения малой степени можно получить, получая многочлены малой степени, содержащие f в качестве делителя, т.е. умножая функцию f на подходящие функции g малой степени так, чтобы произведение f · g снова было малой степени.

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

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

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

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

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).

T.Johansson, F.Jnsson. Fast correlation attacks through reconstruction of linear polynomials // Advanced 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.Trabbia. Improved fast correlation attacks using Parity-check equations of weight 4 and // Eurocrypt 2000 (Bruges, Belgium, May 14–18, 2000). Springer-Verlag, 2000. P. 573–588. (Lecture Notes in Computer Science; Vol. 1807).

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).

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

Расстояние между булевыми функциями f1 и f2 определяется как n d(f1, f2) =| {x F2 | f1(x) = f2(x)} |.

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

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

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

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

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

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

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

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.

C.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).

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

N.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.

L.R.Knudsen, M.J.B.Robshaw. Non-linear approximations in linear cryptanalysis // Proceedings of EUROCRYPT’96. LNCS 1070, 1996. P. 224-236.

U.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) = nl1(f) достаточно хорошо изучены, и существует аппарат коэффициентов Уолша, который позволяет ее вычислять, то с нелинейностью более высоких порядков все обстоит заметно хуже. Про nlr(f) при r 2 мало что известно. Стоит упомянуть наилучшую, как нам известно, на этот момент верхнюю асимптотическую оценку из работы К.Карле и С.Менаже18.

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

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

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

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

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

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).

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.

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.

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

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

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

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.

A.Braeken, B.Preneel. On the algebraic immunity of symmetric boolean functions // Indocrypt 2005.

LNCS 3797, Springer, 2005. P. 35-48.

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

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

Цель работы.

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

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

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

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

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

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

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

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

Pages:     || 2 |






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