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

08-3 2866

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

На правах рукописи УДК 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 не обеспечивает достаточной секретности шифрования. Одним из более надёжных является алгоритм, в котором на вход некоторой булевой функции / от t переменных подаются выходы t различных LFSR — нелинейный комбинатор. Используемая булева функция / должна быть уравновешенной (т. е. число единичных значений должно быть равно числу нулевых значений), а также иметь максимальную алгебраическую степень и нелинейность.

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

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

'Siegenthaler Т. Correlation-iramunity of nonlinear combming functions for cryptographic applicatione // IEEE Transactions on Information theory, V. IT-30, № 5, 1984, pp. 776-780.

определенной размерности одинаковы и вес любого подкуба размерности £ равен ^р- • 2г при п — ттг < < ^ п. Корреляционно-иммунная функция порядка п — 1 является равномерно распределенной по всем подкубам размерности от 1 до п. Более общий случай равномерного распределения по подкубам — это I-уравновешенные функции, т. е. функции, у которых для любых по подфункций Д и /2 от одинакового числа переменных выполнено неравенство ^¿(/1) — ги£(/2)| ^ I- В отличие от корреляционно-иммунных функций, которые равномерно распределены по подкубам размерности от п — тп до п, ¿-уравновешенные функции должны быть равномерно распределены по подкубам всех размерностей одновременно. Таранниковым Ю. В. исследованы 1-уравновешенные2 и ¿-уравновешенные3 булевы функции.

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

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

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

3Таранников Ю. В. О некоторых оценках для веса ¿-уравновешенных булевых функций. // Дис-

кретный анализ и исследование операций, 1995, Т. 2, К* 4, с. 80-96.

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

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

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

Корреляционная иммунность функции и ее алгебраическая степень являются противоречащими друг другу свойствами: в силу неравенства Зигенталера алгебраическая степень корреляционно-иммунной порядка m функции / от п переменных удовлетворяет неравенству deg(f) ^ п — тп — 1. Нелинейность булевой функции и ее корреляционная иммунность также являются противоречащими друг другу свойствами. Нелинейность произвольной булевой функции не превосходит6 2n_1 — 2"/2-1. В 2000 году было независимо доказано7,819, что нелинейность т-устойчи-вой функции от п переменных не превосходит 2n_1 — 2m+1 при тп < п— 1. Причем если эта граница достигается, то тп > 0.5п — 2.

Таранниковым Ю. В. предложен1**11112 метод построения таких функ-

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

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

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

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

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

10Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики. Вып. 11. — М.: Фиэматлит, 2002. — С. 91-148

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

12Fedorova 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.

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

Цель работы

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

Научная новизна работы

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

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

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

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

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

Методы исследования

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

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

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

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

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

• Семинар «Синтез и сложность управляющих систем» под руководством О. Б. Лупанова (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 Coding Theory» (Царское Село, сентябрь 2002)

• Международная конференция «IEEE International Symposium on Information Theory ISIT2002» (Швейцария, июль 2002)

• Международная конференция «Indocrypt 2001» (Индия, Ченнай (Мадрас), декабрь 2001)

• Пятая научная молодежная школа по дискретной математике и ее приложениям (Москва, ноябрь 2001)

• Международная школа-семинар «Дискретная математика и математическая кибернетика» (Москва, Ратмино, май 2001)

• Конференция молодых ученых механико-математического факультета МГУ (апрель, 2001г)

Публикации

Результаты диссертации опубликованы в 13 работах автора, список которых приведен в конце автореферата [1-13].

Структура и объем работы

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В главе 1 вводится определение кода, равномерно распределённого со степенью I по шарам

Определение 1 Пусть I — натуральное число. Код С С Vй называется равномерно распределенным по шарам со степенью I (1-РРШ кодом), если

тах{1хй((5г(®)1С)> - тт{ш«((5г(я), С)} ^ I

X X

для каждого г, 0 ^ г ^ п,

где 5г(з;) — шар радиуса г в центром в точке х, и^((5г(х), С) — вес шара 5г(х), равный мощности множества ¿>г(х) П С. В качестве расстояния используем расстояние Хемминга.

Основным результатом глав 1-3 является

Теорема 1 Пусть I — фиксированное натуральное число, п — размерность булевого куба и 21 + 1 ^ т < 2"-1. Тогда в булевом кубе размерности п не существует ¿-РРШ кодов мощности т для достаточно больших п.

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

Напротив, при т < 21 существуют ¿-РРШ коды при сколь угодно больших п:

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

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

В главе 1 рассматриваются коды малой мощности. Рассмотрим произвольную функцию М(п) = о (^y/ne^^J. Тогда под кодами малой мощности понимаем коды, мощность которых удовлетворяет условию 21 + 1 ^ т ^ М(п) -- о ^у/пе*^1^ . В случае кодов малой мощности неравномерность распределения по шарам устанавливается на шарах, радиус которых близок к п/2. При доказательстве теоремы используются неравенства для сумм биномиальных коэффициентов.

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

1)1— константа и ——► О,

ч/пе4,+1 п-»оо

2) I = fclog,m + 0(1) и lim ^ - Inn < f,

n—»oo n

3) I = rn* +0(1) и существует А > 0 такое что lim —^-т- < 1 — А,

п—>оо logjnl

4 / = ? + 0(1) И Иш ф<§.

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

2П

8 nl < тп <

WO

ЕС?) ¿=0

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

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

2п

8п1 < т < ——-.

МО , ч

ЕС)

1=0

В главе 3 рассматривается вопрос существования /-РРШ кодов большой мощности

2"

Л— < тп < 2п~\ па

где А — некоторое положительное число, в > ко(1). Эти параметры выбираются так, чтобы диапазоны средней и большой мощности пересекались. В этой главе доказывается, что для достаточно больших п не существует /-РРШ кодов в указанном диапазоне. В случае кодов большой мощности мы выделим два семейства мощностей, первое семейство рассмотрим в теореме 5, а второе — в теореме 6.

Теорема 5 Пусть I — фиксированное натуральное число. Числа в Е N, и > 1, са — некоторая константа (своя для каждого з) и тп удовлетворяют соотношениям:

и12 2" ^ /п \ 2"

4 £ (?) ^ ^ £ (") >=0 1=0

и12 2" с-1

- • - ^ ТП ^ I , 3=1.

4 п+1

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

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

и ( , и12\ , и12

п >-- (31 + 1 + — , п ^ 61 + 3 + —-.

и — IV 4 / г

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

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

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

2" 2" ^ ш ^ Аг-

£ С) И (?)

1=0 «=0

при достаточно больших п, Ах и Аг — некоторые положительные числа.

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

В главе 4 рассматриваются ¿-упаковки большого радиуса, Я >

(Ь-М-п-

Теорема 7 Пусть I — фиксированное натуральное число. Для достаточно больших п если существует I-упаковка радиуса Я — тп, то

НШ)'

где ) = 2 ^' (1+1)1 2 ^ — определено и для нечетных т.

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

Следствие 1 В условиях теоремы при | — ^тт < т < мощность 1-упаковки радиуса Я = тп при достаточно больших п удовлетворяет условию

где а(т) = (2т - 1) • 2' + 1 и С[ не зависит от т.

9

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

Определение 3 Пусть В = (Ьу) — это (2к х р) матрица с 2к строками и р столбцами, клетки которой заполнены символами из множества {1,2, *}. Пусть ko ut — это натуральные числа. Мы предполагаем, что

(а) для любых двух строк i\ и ¿2 существует столбец j, такой что bia = 1, bÍ2j = 2 или bhj = 2, bÍ3j = 1.

V

(б) для любой строки i выполняется неравенство ^ < t (знаки

з=i

* не дают в суммы никакого вклада).

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

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

Интерес представляет нижняя граница отношения щ параметров подходящей (fco, к,р, £)-матрицы. В этой главе доказывается, что

Теорема 8 Для любой подходящей (ко,к,р,Ь)-матрицы выполняется неравенство ^ ^ log,(^+1) = 0.5902...

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

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

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

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

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

I3Tarannikov Yu. New constructions of résilient 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, Ш, с. 65-97.

[2] Ярыкина М. С. Применение оценок для сумм биномиальных коэффициентов при решении некоторых задач теории кодирования и криптографии. // Математические вопросы кибернетики. Вып. 12. — М.: Физматлит, 2003. — С. 87-108.

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

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

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

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

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

[8] Ярыкина М.С. Несуществование двоичных кодов, равномерно распределенных по шарам, почти всех мощностей // Материалы VI

молодежной научной школы по дискретной математике и ее приложением (Москва, 16-21 апреля 2007г), ч. III, С. 52-56.

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

[10] Fedorova М., 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.

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

[11] Fedorova М., 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.

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

[12] Fedorova M., New results on impossibility of uniform distribution of codewords over spheres // Proceedings of Eighth International Workshop 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.

Издательство ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова

Подписано в печать /Б. 03.0& Формат 60x90 1/16. Усл. печ. л.0,75 Тираж /¿7^7 экз. Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

2007518058

Введение

1 Коды малой мощности

§1.1 Определения.

§1.2 Коды малой мощности.

2 Коды средней мощности

§2.1 Вспомогательные результаты.

§ 2.2 Неравенство для сумм биномиальных коэффициентов.

§ 2.3 Покрытие булева куба.

§ 2.4 Основная теорема для случая средних весов.

3 Коды большой мощности

§3.1 Первое семейство.

§ 3.2 Второе семейство.

4 Оценки для /-упаковок большого радиуса

5 Неравенства для параметров матриц специального вида 66 Литература

В настоящей работе рассматриваются некоторые задачи теории кодирования. Изучается вопрос существования двоичных кодов, равномерно распределенных со степенью I по шарам, рассматривается вопрос существования /-упаковок большого радиуса (R > п/4) и изучается вопрос существования матриц специального вида с особыми значениями параметров.

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

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

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

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

4. Получена явная точная оценка параметра матриц специального вида. С помощью таких матриц в [18] строятся корреляционно-иммунные функции порядка т > 0.5902. •n+0(log2 п) с максимальной нелинейностью.

История вопроса. К одним из самых важных задач теории кодирования относятся задача построения кодов, исправляющих ошибки и задача построения кодов для шифрования данных.

Теория кодирования начала развиваться в 1940-х годах с работ Хеммин-га, Шеннона и Голея. В этих работах рассматривалась практическая задача построения кодов, исправляющих ошибки.

Пусть у нас есть канал связи, на одном конце которого мы кодируем данные, а на другом конце — декодируем, и при передаче данных иногда случаются ошибки (шум, помехи). Задача состоит в том, чтобы придумать такой код, чтобы мы могли выявить и исправить ошибки. Такой код называется кодом, исправляющим ошибки. Наиболее известными являются коды Хемминга - это коды, исправляющие одну ошибку. Кроме того, достаточно известны коды Боуза-Чоудхури-Хеквингема (БЧХ-коды), исправляющие 2 и более ошибок.

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

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

Для кодирования текста с закрытым ключом часто используется поточное шифрование. Оно устроено следующим образом: к нашему (двоичному) тексту мы прибавляем (сложение по модулю 2) некоторую псевдослучайную последовательность Т = {£п}- Чтобы дешифровать закодированный текст, мы прибавляем к нему ту же самую последовательность Т и получаем исходный текст.

Для получения псевдослучайной последовательности Т можно использовать регистр сдвига с линейной обратной связью (LFSR).

Однако, если длина наименьшего LFSR, порождающего последовательность Т, равна Л(Т), то можно узнать всю последовательность Т, зная только 2Л(Т) первых ее значений. Поэтому шифрование с использованием лишь одного LFSR не обеспечивает достаточной секретности шифрования.

Одним из более надёжных является алгоритм, использующий несколько LFSR следующим образом. Выбирается некоторая булева функция / от L переменных, и в качестве входных переменных функции / используются выходы различных LFSR: LFSRi, LFSR2, .LFSRt — такой алгоритм называется нелинейным комбинатором. Используемая булева функция / должна быть уравновешенной (т. е. число единичных значений должно быть равно числу нулевых значений), а также иметь максимальную алгебраическую степень и нелинейность.

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

Как видно из определения, корреляционно-иммунные функции являются I равномерно распределенными по подкубам, т. е. веса всех подкубов определенной размерности одинаковы (от п до п — т) и вес любого подкуба размерности Ь равен • 2Ь при n — m^t^n. Корреляционно-иммунная функция порядка п—1 является равномерно распределенной по всем подкубам размерности от 1 до п.

Помимо задачи равномерного распределения по подкубам, когда веса всех подкубов одной размерности одинаковы, имеется более общая задача равномерного распределения со степенью I по подкубам, т. е. поиска /уравновешенных функций. Булева функция / от п переменных называется I-уравновешенной, если для любых ее подфункций fi и /2 от одинакового числа переменных выполнено неравенство \wt(fi) — wt(f2)\ ^ I. В отличие от корреляционно-иммунных функций, которые равномерно распределены по подкубам размерности от п — т до п, /-уравновешенные функции должны быть равномерно распределены по подкубам всех размерностей одновременно. Все 1-уравновсшснные функции описаны в работе [4], а в работе [5] исследованы /-уравновешенные булевы функции.

Кроме того, в работе [4] доказано, что любую 1-уравновешенную функцию можно реализовать схемой из функциональных элементов с линейной (по п) сложностью.

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

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

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

Поскольку между булевыми функциями и двоичными кодами существует взаимно однозначное соответствие, приведем результаты работы [6] на языке двоичных кодов:

Утверждение 1 (см. [6]) Пусть С С Vn, \С\ ^ 2"-1. Если С- 1-РРШ код, то выполняется один из случаев:

1) |С| ^ 2;

2) п ^ 4;

3) п = 6,|С| = 4.

Утверждение 2 (см. [6]) Число различных 1-РРШ кодов в Vn равно

22" для n ^ 2,

80 для п = 3,

334 для п — 4,

2818 для п = 6,

3 • 2п + 2 для п ^ 5, п нечетно, (п + 3)2П + 2 для п ^ 8, п четно.

Таким образом, при п ^ 7 мощность любого 1-РРШ кода либо не превосходит 2, либо не менее 2П — 2. Кроме того, при п ^ 7 все 1-РРШ коды мощности 2 состоят из пары противоположных наборов.

В дайной работе рассматривается вопрос существования кодов, равномерно распределённых по шарам со степенью I, где I — произвольное натуральное число. Доказывается, что при достаточно больших п такие коды существуют, только если их мощность не превосходит 21, либо мощность не менее 2П — 21.

Также в данной работе рассматривается задача оцешш мощности I-упаковок. Коды, являющиеся /-упаковками, используются в теории кодирования при решении задач списочного декодирования. Двоичный код С является I-упаковкой радиуса R, если в любой шар радиуса R попадает не более чем I кодовых слов. Точная асимптотическая оценка мощности /-упаковки в зависимости от ее радиуса R = тп получена Блиновским В.М. в работе [1]. В теории списочного декодирования принято оценивать не саму мощность кода 7п, а величину A{m) = (log2т)/п.

Если двоичный код С является /-РРШ кодом и существует шар радиуса R, не содержащий ни одного кодового слова, то код С является /-упаковкой радиуса R. Примененные в этой работе методы позволили получить явную оценку мощности /-упаковки в зависимости от ее радиуса R = тп при т, близких к 1/2. При рассматриваемых значениях т в работе [1] величина А{тп) равна о(1). Результат, полученный в данной работе согласуется с этим результатом и уточняет его.

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

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

Корреляционная иммунность функции и ее алгебраическая степень являются противоречащими друг другу свойствами: в силу неравенства Зигеп-талера алгебраическая степень корреляционно-иммунной порядка т булевой функции / от п переменных удовлетворяет неравенству: deg{f) ^ п — т — 1.

Нелинейность булевой функции и ее корреляционная иммунность также являются противоречащими друг другу свойствами. Как показано в [3, гл. 14], нелинейность произвольной булевой функции не превосходит 2П~1 — 2n/2-i g работах [22], [24] и [27] было независимо доказано, что нелинейность m-устойчивой функции от п переменных не превосходит 2n1 — 2m+1 при т ^ п — 1. Причем если эта граница достигается, то т > 0.5п — 2.

В работах [7, 25, 18] приводится метод построения корреляционно-иммунных и устойчивых функций с максимальной нелинейностью с помощью подходящих матриц. Понятие подходящей (ко. к,/р. £)-матрицы вводится Та-ранниковым Ю.В. в работе [25]. Требуется построить такую подходящую к, р: ^-матрицу, чтобы соотношение щ; было минимально. В главе 5 настоящей работы доказывается, что :>-L-= 0.5902. t + k log2(V/5 + l) и что можно построить подходящую (к, к,р, ^-матрицу со сколь угодно близким к нижней границе соотношением параметров.

На основании этого результата в работах [25, 18] Тараиниковым Ю. В. строятся эффективные конструкции гп-устойчнвых булевых функций с максимальной нелинейностью при т > 0.5902. • п + 0(log2 п).

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

Краткое содержание диссертации. В данной работе изучаются коды, равномерно распределённые со степенью I по шарам для любого натурального I, в то время как в работе [6] рассматривался только случай / = 1. Приводится полное доказательство несуществования кодов мощности более 2/, равномерно распределенных со степенью I по шарам для любого натурального I.

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

В главе 4 рассматривается вопрос существования /-упаковок большого радиуса: R > n/А. Получена явная оценка мощности I упаковки при нулевой скорости. Этот результат удалось получить с применением методов, использованных в главах 1-3.

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

Введем определение кода, равномерно распределенного со степенью I по шарам.

Пусть у нас п — размерность булева куба, С — код, т = \С\ — мощность кода. В качестве расстояния между двумя точками булева куба используем расстояние Хемминга. Вес шара Sr{x) радиуса г с центром в точке х — это мощность пересечения шара Sr(x) и кода С.

В булевом кубе размерности п рассмотрим все 2п шаров некоторого радиуса г. Посчитаем для каждого шара его вес wt(Sr(x)). Код С называется равномерно распределенным со степенью I по шарам, или /-РРШ кодом, если для каждого радиуса г максимальный вес шара радиуса г и минимальный вес шара радиуса г отличаются не более, чем на I.

Заметим, что если у нас для некоторого радиуса г минимальный вес шара радиуса г равен нулю (т. е. существует пустой шар радиуса г), то код является /-упаковкой радиуса г.

Если С является /-РРШ кодом, то легко видеть, что его дополнение — код С также является /-РРШ кодом. Поэтому без ограничения общности можно рассматривать только коды мощности не более 2п~1. Если код С будет иметь мощность больше, чем 271-1, то будем рассматривать его дополнение — код С (его мощность равна 2П — |С|).

Полное описание кодов, равномерно распределенных по шарам со степенью 1 (1-РРШ кодов) было дано в [6]. Было доказано, что при п ^ 7 не существует кодов, равномерно распределенных по шарам со степенью 1 мощности 3 ^ т ^ 2п — 3. И для любого п существует 1-РРШ код мощности т = 2. Таким кодом является любой код, состоящий из двух противоположных точек булева куба размерности п.

В данной работе без ограничения общности мы рассматриваем только коды мощности т ^ 2n1. Мы доказываем следующую теорему

Теорема 1 Пусть I — фиксированное натуральное число, п — размерность булевого куба и 21 + 1 ^ т ^ 2п~1. Тогда в булевом кубе размерности п не существует /-РРШ кодов мощности т для достаточно больших п.

Для одного поддиапазона мощности кода удалось указать значение По, такое что при п > uq не существует /-РРШ кодов.

При т ^ 21 существуют /-РРШ коды для сколь угодно больших значений размерности п.

Мы выделим три диапазона (асимптотической) мощности кода: коды малой мощности, средней мощности и большой мощности. малая мощность средняя мощность большая мощность

Г гт

21+1 8nl

В главе 1 рассматривается вопрос существования /-РРШ кодов малой мощности

Границей диапазона кодов малой мощности является некоторая последовательность т — т(п), удовлетворяющая вышеуказанному условию (от выбора этой последовательности зависит, начиная с какого значения п размерности

2" \ он—1 п" МО г » 2n \

ЕС) оценка па щ указана булевого куба будут выполнены условия теоремы несуществования). В главе 1 доказывается, что для достаточно больших п не существует /-РРШ кодов в указанном диапазоне. При доказательстве теоремы используются неравенства для сумм биномиальных коэффициентов вида

2-ка 1 — 2а г

1 + 0

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

В главе 2 рассматривается вопрос существования /-РРШ кодов средней мощности

2 п

Ш<т< ад — ' £ (") г=0 где /со(7) - некоторое целое число, далее определяемое в работе. Доказывается, что для достаточно больших п не существует /-РРШ кодов в указанном диапазоне. При доказательстве используются свойства взаимного расположения кодовых слов в шарах различного радиуса, свойства кодов Рида-Маллера первого порядка, а также свойства сумм биномиальных коэффициентов ви-к да J2 (") при каждом фиксированном к. В случае кодов средней мощности i=о неравномерность распределения по шарам имеется на шарах различного радиуса от к до п.

В главе 3 рассматривается вопрос существования /-РРШ кодов большой мощности on

Л— <т^2п-\

71s где А — некоторое положительное число, s > (/). Эти параметры выбираются так, чтобы диапазоны средней и большой мощности пересекались. В этой главе доказывается, что для достаточно больших п не существует /-РРШ кодов в указанном диапазоне. В случае кодов большой мощности мы выделим два семейства мощностей. Основная идея доказательства — подсчет пар кодовых слов на некотором расстоянии к двумя способами (верхняя оценка и нижняя оценка) и сравнение полученных величин. В случае кодов большои мощности неравномерность распределения по шарам имеется на шарах радиусов от 1 до 2s. Для поддиапазона ul2 2П Т1 , т ^ 2п~\

4 п + 1 где и > 1 — некоторое число, удалось указать значение пц, такое, что при п > ?го не существует /-РРШ кодов мощности т. В этом случае неравномерность распределения по шарам имеется уже на шарах радиусов 1 и 2. Заметим, что в этот поддиапазон попадают почти все коды булева куба размерности п.

В главе 4 рассматриваются /-упаковки большого радиуса, R > — ^тт) ■ п. Получена явная верхняя оценка мощности /-упаковки в зависимости от ее радиуса R = тп, где т не зависит от п: +1) 1 ///(/ + 1)У и . . где а(т) = (2т — 1) • 2l + 1 и q не зависит от т. Для доказательства этой оценки используются методы, изложенные в главе 1.

В главе 5 рассматриваются матрицы специального вида, так называемые подходящие матрицы. Понятие подходящей (ко, к,р, /)-матрицы было введено Таранниковым Ю. В. в работе [25]. Интерес представляет нижняя граница отношения щ; параметров (/со, к,р, /,)-иодходящей матрицы. В этой главе доказано, что ^-\=-= 0.5902. t + k log2(\/5 + 1)

Кроме того, автором доказано, что можно построить подходящую (k,k,p,t)~ матрицу с соотношением параметров, сколь угодно близким к нижней границе log = 0.5902. Матрицы с минимальным отношением используются в работе [18] для построения корреляционно-иммунных функций с высокой нелинейностью.

Непосредственно к теме диссертации относятся работы автора [8-16, 19, 20, 26].

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

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

2. Гаврилов Г. П. Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977.

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

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

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

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

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

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

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

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

11. Ярыкина М. С. Применение оценок для сумм биномиальных коэффициентов при решении некоторых задач теории кодирования и криптографии. // Математические вопросы кибернетики. Вып. 12.'— М.: Физмат-лит, 2003. С. 87-108.

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

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

14. Blinovsky V. Bounds for Multiple Packing in q-ary Hamming Space.// Proceedings of ISIT 2002, Lausanne, Switzerland, June 30 July 5, 2002, p. 401.

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

16. Fedorova M. New results on impossibility of uniform distribution of codewords over spheres // Proceedings of Eighth International Workshop on Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, September, 2002, pp. 104-107.

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

18. Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Transactions on Information theory, V. IT-30, № 5, 1984, pp. 776-780.

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