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

В настоящей работе рассматриваются некоторые задачи теории кодирования. Изучается вопрос существования двоичных кодов, равномерно распределенных со степенью 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] величина А{тп) равна о (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.