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

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

УДК 519.722 Ярыкина Мария Сергеевна О НЕСУЩЕСТВОВАНИИ ДВОИЧНЫХ КОДОВ ПРИ РАЗЛИЧНЫХ УСЛОВИЯХ РАВНОМЕРНОЙ РАСПРЕДЕЛЕННОСТИ дискретная математика и математическая (01.01.09 кибернетика)

АВТОРЕФЕРАТ

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

Москва 2008

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

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

Официальные оппоненты: доктор физико-математических наук В. М. Блиновский, Институт проблем передачи информа ции имени А. А. Харкевича РАН доктор физико-математических наук, профессор А. А. Сапоженко, Московский государственный универси тет имени М. В. Ломоносова

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

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

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

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

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

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

Актуальность темы Диссертация является исследованием в области теории кодирования.

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

Рассмотрим кодирование с помощью поточного шифратора, исполь зующего регистр сдвига с линейной обратной связью (LFSR). Шифро вание с использованием одно лишь LFSR не обеспечивает достаточной секретности шифрования. Одним из более надёжных является алгоритм, в котором на вход некоторой булевой функции f от t переменных подают ся выходы t различных LFSR нелинейный комбинатор. Используемая булева функция f должна быть уравновешенной (т. е. число единичных значений должно быть равно числу нулевых значений), а также иметь максимальную алгебраическую степень и нелинейность.

Зигенталер1 предложил алгоритм дешифрования указанной выше комбинации LFSR, используя корреляцию выхода функции f и некоторо го подмножества ее входных переменных, и ввел понятие корреляционно иммунной функции. Булева функция f называется корреляционно-им мунной порядка m, где 1 m n, если выход функции f и любое мно жество из m входных переменных статистически независимы. Другими словами, если вес любой подфункции f функции f от n m переменных удовлетворяет условию: wt(f ) = wt(f )/2m. Уравновешенная корреля ционно-иммунная порядка m функция называется m-устойчивой. Для использования функции f в качестве нелинейного комбинатора несколь ких LFSR нужно, чтобы она была m-устойчивой с максимально возмож ным m.

Как видно из определения, корреляционно-иммунные функции явля ются равномерно распределенными по подкубам, т.е. веса всех подкубов Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Transactions on Information theory, V. IT-30, № 5, 1984, pp. 776–780.

определенной размерности одинаковы и вес любого подкуба размерно сти t равен wt(f ) · 2t при n m t n. Корреляционно-иммунная 2n функция порядка n 1 является равномерно распределенной по всем подкубам размерности от 1 до n. Более общий случай равномерного рас пределения по подкубам это l-уравновешенные функции, т. е. функ ции, у которых для любых подфункций f1 и f2 от одинакового числа переменных выполнено неравенство |wt(f1 ) wt(f2 )| l. В отличие от корреляционно-иммунных функций, которые равномерно распределены по подкубам размерности от n m до n, l-уравновешенные функции должны быть равномерно распределены по подкубам всех размерностей одновременно. Таранниковым Ю. В. исследованы 1-уравновешенные2 и l-уравновешенные3 булевы функции.

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

Булева функция f называется равномерно распределенной со степе нью 1 по шарам 4 (1-РРШ), если для каждого радиуса r максимальный вес шара радиуса r и минимальный вес шара радиуса r (из всех 2n ша ров радиуса r в булевом кубе размерности n) отличаются не более, чем на единицу. Весом шара мы называем количество единичных значений функции в шаре, в качестве расстояния используем расстояние Хеммин га. В работе4 полностью описаны все 1-РРШ функции и получено, что при n 7 вес любой 1-РРШ функции либо не превосходит 2, либо не ме нее 2n 2. В диссертации рассматривается вопрос существования кодов, равномерно распределённых по шарам со степенью l, где l произволь ное натуральное число.

Таранников Ю. В. Класс 1-уравновешенных функций и сложность его реализации // Вестник Московского Университета. Серия 1. Математика. Механика. 1991. № 2, с. 83–85.

Таранников Ю. В. О некоторых оценках для веса l-уравновешенных булевых функций. // Дис кретный анализ и исследование операций, 1995, Т. 2, № 4, с. 80–96.

Таранников Ю. В. О классе булевых функций, равномерно распределенных по шарам со степе нью 1. // Вестник Московского Университета. Серия 1. Математика. Механика. 1997, вып. 52, №5, стр. 18–22.

В теории кодирования при решении задач списочного декодирования используются коды, являющиеся l-упаковками. Двоичный код C явля ется l-упаковкой радиуса R, если в любой шар радиуса R попадает не более чем l кодовых слов. Точная асимптотическая оценка мощности l упаковки в зависимости от ее радиуса R = n получена Блиновским В. М.5. В теории списочного декодирования принято оценивать не саму мощность кода m, а величину A(m) = (log2 m)/n. В работе5 при больших величина A(m) равна o(1), а в диссертации автором получена явная оценка m( ), которая согласуется с этим результатом и уточняет его.

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

Корреляционная иммунность функции и ее алгебраическая степень являются противоречащими друг другу свойствами: в силу неравенства Зигенталера алгебраическая степень корреляционно-иммунной поряд ка m функции f от n переменных удовлетворяет неравенству deg(f ) n m 1. Нелинейность булевой функции и ее корреляционная иммун ность также являются противоречащими друг другу свойствами. Нели нейность произвольной булевой функции не превосходит6 2n1 2n/21.

В 2000 году было независимо доказано7, 8, 9, что нелинейность m-устойчи вой функции от n переменных не превосходит 2n1 2m+1 при m n 1.

Причем если эта граница достигается, то m 0.5n 2.

Таранниковым Ю. В. предложен10, 11, 12 метод построения таких функ Блиновский В. М. Границы для кодов при декодировании списком конечного объема. Проблемы передачи информации. 1986. Том 22, № 1, стр. 11–25.

Мак-Вильямс Ф. Дж. Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

Sarkar P., Maitra S. Nonlinearity bounds and constructions of resilient Boolean functions // In Advanced in Cryptology: Crypto 2000, Proceedings, Lecture Notes in Computer Science, V. 1880, 2000, pp. 515–532.

Tarannikov Yu. On resilient Boolean functions with maximal possible nonlinearity, // Proceedings of Indocrypt 2000, Lecture Notes in Computer Science,V. 1977, pp. 19–30, Springer-Verlag, 2000.

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

Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математиче ские вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 91– Tarannikov Yu. New constructions of resilient Boolean functions with maximal nonlinearity // Fast Software Encryption. 8th International Workshop, FSE 2001 Yokohama, Japan, April 2–4, 2001. Revised Papers, Lecture Notes in Computer Science, V. 2355, 2002, pp. 66–77.

Fedorova M., Tarannikov Yu. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices // Progress in Cryptology Indocrypt 2001, Chennai, India, December 16–20, 2001, Proceedings, Springer-Verlag, 2001, V. 2247, pp. 254–266.

ций с помощью подходящих матриц. Понятие подходящей (k0, k, p, t) матрицы вводится Таранниковым Ю. В.11 Требуется построить такую t подходящую матрицу, чтобы соотношение t+k было минимально. В дан ной работе доказывается нижняя оценка для этого соотношения пара метров.

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

Научная новизна работы Результаты работы являются новыми. В диссертации получены следую щие основные результаты:

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

2. Для одного поддиапазона мощности кода получена явная оценка значения размерности n, начиная с которой не существует кодов, равномерно распределенных со степенью l по шарам.

3. Получена явная верхняя оценка мощности l-упаковки большого ра диуса (R n/4) в зависимости от параметра = R/n.

4. Получена явная точная оценка параметра матриц специального ви да. С помощью таких матриц построены12 корреляционно-иммун ные функции порядка m 0.5902... · n + O(log2 n) с максимальной нелинейностью.

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

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

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

• Семинар Синтез и сложность управляющих систем под руковод ством О. Б. Лупанова (2003) • Семинар Булевы функции в криптологии под руководством О. А. Логачева и Ю. В. Таранникова на мех-мат факультете МГУ (март 2007).

• Семинар под руководством Л. А. Бассалыго в ИППИ РАН (май 2008).

• Семинар под руководством А. А. Сапоженко на ВМиК факультете МГУ (май 2008).

• Международная конференция NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security (Звени город, сентябрь 2007) • IX международный семинар Дискретная математика и ее прило жения, посвященный 75-летию со дня рождения ак. О.Б. Лупано ва (Москва, июнь 2007) • VI молодежная научная школа по дискретной математике и ее при ложениям (Москва, апрель 2007) • V международная конференция Дискретные модели в теории управляющих систем (Москва, Ратмино, май 2003) • V международная конференция Algebraic and Combinatorial Cod ing Theory (Царское Село, сентябрь 2002) • Международная конференция IEEE International Symposium on Information Theory ISIT2002 (Швейцария, июль 2002) • Международная конференция Indocrypt 2001 (Индия, Ченнай (Мадрас), декабрь 2001) • Пятая научная молодежная школа по дискретной математике и ее приложениям (Москва, ноябрь 2001) • Международная школа-семинар Дискретная математика и мате матическая кибернетика (Москва, Ратмино, май 2001) • Конференция молодых ученых механико-математического факуль тета МГУ (апрель, 2001г) Публикации Результаты диссертации опубликованы в 13 работах автора, список ко торых приведен в конце автореферата [1–13].

Структура и объем работы Диссертация состоит из введения, пяти глав и списка литературы из наименований. Общий объем диссертации 77 страниц, в работе содер жится 2 рисунка.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении содержится обзор результатов, связанных с темой дис сертации, приводится постановка задач, дается краткое изложение ос новных результатов диссертации.

В главах 1–3 рассматривается задача существования двоичных ко дов, равномерно распределенных со степенью l по шарам.

В главе 1 вводится определение кода, равномерно распределённого со степенью l по шарам Определение 1 Пусть l натуральное число. Код C V n называет ся равномерно распределенным по шарам со степенью l (l-РРШ кодом), если max{wt((Sr (x), C)} min{wt((Sr (x), C)} l x x для каждого r, 0 r n, где Sr (x) шар радиуса r в центром в точке x, wt((Sr (x), C) вес шара Sr (x), равный мощности множества Sr (x) C. В качестве расстояния используем расстояние Хемминга.

Основным результатом глав 1–3 является Теорема 1 Пусть l фиксированное натуральное число, n размер ность булевого куба и 2l + 1 m 2n1. Тогда в булевом кубе размер ности n не существует l-РРШ кодов мощности m для достаточно больших n.

Эта теорема следует непосредственно из теорем 3–6.

Напротив, при m 2l cуществуют l-РРШ коды при сколь угодно больших n:

Теорема 2 Пусть l фиксированное натуральное число, n размер ность булевого куба. Тогда для любого n существует l-РРШ код мощ ности m при m 2l.

Если рассматривать шары не всех радиусов сразу, а лишь одного или нескольких равномерное распределение кодовых слов по шарам воз можно при любом n, например, код Хемминга является равномерно рас пределенным со степенью 1 по шарам радиуса r = 1, а любая l-упаковка радиуса R является равномерно распределенной со степенью l по шарам по шарам радиуса r R.

В главе 1 рассматриваются коды малой мощности.

l+1 n Рассмотрим произвольную функцию M (n) = o ne 4. Тогда под кодами малой мощности понимаем коды, мощность которых удовлетво l+1 n ряет условию 2l + 1 m M (n) = o ne 4. В случае кодов малой мощности неравномерность распределения по шарам устанавливается на шарах, радиус которых близок к n/2. При доказательстве теоремы ис пользуются неравенства для сумм биномиальных коэффициентов.

Теорема 3 Пусть l N и m = m(n) 2l + 1. Тогда, для достаточ но больших n не существует l-РРШ кодов мощности m в следующих случаях:

константа и ml+1 0, 1) l n n ne 2k lim m · ln n k, 2) l = k log2 m + O(1) и n n 1 m 3) l = m k + O(1) и существует 0 такое что lim 1, n logk n m m 2.

4) l = + o(1) и lim 4 log 4 n n В главе 2 рассматриваются коды средней мощности:

2n 8nl m.

k0 (l) n i i= где k0 (l) - некоторое целое число. При доказательстве используются свой ства взаимного расположения кодовых слов в шарах различного радиуса, свойства кодов Рида-Маллера первого порядка и свойства сумм бино миальных коэффициентов. Неравномерность распределения по шарам имеется на шарах различного радиуса от k до n.

Теорема 4 Пусть l фиксированное натуральное число и k0 (l) некоторое натуральное число. Тогда в булевом кубе размерности n при достаточно больших n не существует кодов, равномерно распределен ных со степенью l по шарам, мощности m, удовлетворяющей неравен ствам:

2n 8nl m.

k0 (l) n i i= В главе 3 рассматривается вопрос существования l-РРШ кодов боль шой мощности 2n s m 2n1, n где некоторое положительное число, s k0 (l). Эти параметры вы бираются так, чтобы диапазоны средней и большой мощности пересе кались. В этой главе доказывается, что для достаточно больших n не существует l-РРШ кодов в указанном диапазоне. В случае кодов боль шой мощности мы выделим два семейства мощностей, первое семейство рассмотрим в теореме 5, а второе в теореме 6.

Теорема 5 Пусть l фиксированное натуральное число. Числа s N, u 1, cs некоторая константа (своя для каждого s) и m удовлетво ряют соотношениям:

ul2 2n 2n n m + cs, s 1.

s s s 4 n n i i i=0 i= ul2 2n m 2n1, · s = 1.

4 n+ Тогда для достаточно больших n в булевом кубе размерности n не существует l-РРШ кодов мощности m.

Кроме того, в случае s = 1 в булевом кубе размерности n не суще ствует l-РРШ кодов, если n удовлетворяет следующим условиям:

ul2 ul u n 3l + 1 +, n 6l + 3 +.

u1 4 Отметим, что случай s = 1 покрывает почти все двоичные коды. Кроме того, к нему относятся все уравновешенные коды. При этом неравномер ность распределения по шарам имеется уже на шарах радиусов 1 и 2.

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

Теорема 6 Пусть l фиксированное натуральное число. Тогда в бу левом кубе размерности n не существует кодов, равномерно распреде ленных по шарам со степенью l, следующей мощности m:

2n 2n 1 m s s n n i i i=0 i= при достаточно больших n, 1 и 2 некоторые положительные чис ла.

Положительные числа 1 и 2 выбираем так, чтобы первое и второе се мейства мощностей пересекались.

В главе 4 рассматриваются l-упаковки большого радиуса, R 1 2 2l+1 · n.

Теорема 7 Пусть l фиксированное натуральное число. Для доста точно больших n если существует l-упаковка радиуса R = n, то m/ 1 l+ 12, m 2 l+ ( m 1)...( m l) m m/ где = определено и для нечетных m.

2 2 l+1 (l+1)!

Получена явная верхняя оценка мощности l-упаковки в зависимости от ее радиуса R = n:

Следствие 1 В условиях теоремы при 1 2l+1 1, мощность 2 l-упаковки радиуса R = n при достаточно больших n удовлетворяет условию l(l + 1) 1 l(l + 1) m + 4a( )cl, 4a( ) 2a( ) где a( ) = (2 1) · 2l + 1 и cl не зависит от.

В главе 5 рассматриваются матрицы специального вида, так назы ваемые подходящие матрицы. Понятие подходящей (k0, k, p, t)-матрицы было введено Таранниковым Ю. В.13 :

Определение 3 Пусть B = (bij ) это (2k p) матрица с 2k строка ми и p столбцами, клетки которой заполнены символами из множе ства {1, 2, }. Пусть k0 и t это натуральные числа. Мы предполага ем, что (а) для любых двух строк i1 и i2 существует столбец j, такой что bi1 j = 1, bi2 j = 2 или bi1 j = 2, bi2 j = 1.

p (б) для любой строки i выполняется неравенство bij t (знаки j= не дают в суммы никакого вклада).

(в) в каждой строке число единиц не превосходит k0.

Если матрица B удовлетворяет всем свойствам (а), (б), (в), то мы говорим, что B является подходящей (k0, k, p, t)-матрицей.

t Интерес представляет нижняя граница отношения t+k параметров подходящей (k0, k, p, t)-матрицы. В этой главе доказывается, что Теорема 8 Для любой подходящей (k0, k, p, t)-матрицы выполняется t неравенство t+k = 0.5902...

log ( 5+1) и что можно построить подходящую (k, k, p, t)-матрицу с соотношением параметров, сколь угодно близким к нижней границе:

Теорема 9 Для любого 0 существует подходящая (k, k, p, t)-мат t рица, для которой t+k log (5+1) +.

t Матрицы с минимальным отношением t+k используются в [10] для по строения корреляционно-иммунных функций с высокой нелинейностью.

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

Tarannikov Yu. New constructions of resilient Boolean functions with maximal nonlinearity // Fast Software Encryption. 8th International Workshop, FSE 2001 Yokohama, Japan, April 2–4, 2001. Revised Papers, Lecture Notes in Computer Science, V. 2355, 2002, pp. 66–77.

Список литературы [1] Ярыкина М. С. Несуществование двоичных кодов, равномерно рас пределенных по шарам. // Дискретный анализ и исследование опе раций. 2008, №2, с. 65–97.

[2] Ярыкина М. С. Применение оценок для сумм биномиальных ко эффициентов при решении некоторых задач теории кодирова ния и криптографии. // Математические вопросы кибернетики.

Вып. 12. М.: Физматлит, 2003. С. 87–108.

[3] Федорова М. С. О неравенствах для параметров комбинаторных матриц специального вида. // Вестник Московского Университе та. Серия 15. Вычислительная математика и кибернетика. 2002, №2, с.45–49.

[4] Федорова М. С. О соотношениях между параметрами матриц специ ального вида. // Современные исследования математики и механи ки. Труды XXIII конференции молодых ученых механико-математи ческого факультета МГУ (9–14 апреля 2001г.) Москва, Изд-во цен тра прикладных исследований при мех-мат факультете МГУ, 2001, том 3, стр. 334–337.

[5] Федорова М. С. О неравенствах для параметров матриц специаль ного вида. // Труды международной школы-семинара Дискрет ная математика и математическая кибернетика, Ратмино, 31 мая– июня 2001г. Москва 2001, стр. 26.

[6] Федорова М. С. Равномерно распределить двоичные наборы по ша рам не всегда возможно. // Труды Пятой научной молодежной шко лы по дискретной математике и ее приложениям (Москва, 13– ноября 2001 г.). M., Изд-во центра прикладных исследований при мех-мат факультете МГУ, 2001, с. 94–100.

[7] Ярыкина М. С. Об оценках для l-упаковок большого радиуса. // Труды V международной конференции Дискретные модели в тео рии управляющих систем, Ратмино, 26 мая–29 мая 2003г. Москва 2003, стр. 94.

[8] Ярыкина М. С. Несуществование двоичных кодов, равномерно рас пределенных по шарам, почти всех мощностей // Материалы VI молодежной научной школы по дискретной математике и ее прило жением (Москва, 16–21 апреля 2007г), ч. III, С. 52–56.

[9] Ярыкина М.С. Двоичные коды почти всех мощностей не могут быть равномерно распределенными по шарам // Материалы IX междуна родного семинара Дискретная математика и ее приложения, по священного 75-летию со дня рождения ак. О.Б. Лупанова, Изд-во мех-мат фак. МГУ, 2007 С. 464–467.

[10] Fedorova M., Tarannikov Yu. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices // Progress in Cryptology Indocrypt 2001, Chennai, India, December 16–20, 2001, Proceedings, Springer-Verlag, 2001, V. 2247, pp. 254–266.

http://eprint.iacr.org/2001/083 16 pp.

Ярыкиной М.С. принадлежит теорема о нижней оценке о соот ношениях матриц специального вида.

[11] Fedorova M., Tarannikov Yu. On impossibility of uniform distribution of codewords over spheres in some cases. // Proceedings of 2002 IEEE International Symposium on Information Theory ISIT2002, Lausanne, Switzerland, June 30 - July 05, 2002, p. 344.

Федоровой М.С. принадлежат основные результаты.

[12] Fedorova M., New results on impossibility of uniform distribution of codewords over spheres // Proceedings of Eighth International Work shop on Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, September, 2002, pp. 104–107.

[13] Yarykina M. S. The Impossibility of Uniform Distribution of Codewords over Spheres. // Proceedings of the NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security, Zvenigorod, Russia, 8–18 September, 2007. IOS press, 2008, vol.18, pp. 315–331.