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

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

А/1ГЕБР0ГЕ0МЕТРИЧЕСКИЕ МЕТОДЫ ИЗБЫТОЧНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ

Специальность 05 13 01 «Системный анализ, управление и обработка информации (в технике и технологиях)»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2007

ооз

003161152

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" (ГУАП)

Научный руководитель-

доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты:

доктор технических наук профессор Шепета Александр Павлович кандидат технических наук, доцент Шкиртиль Вячеслав Иванович

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

Холдиноговая компания "Ленинец"

Защита состоится '"^С " Гж^тгэю^» 32007 года на заседании диссертационного совета Д 212 233 02 при Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" по адресу 190000, г Санкт-Петербург, ул Большая Морская, д 67

С диссертацией можно ознакомиться в библиотеке ГУАП

Автореферат разослан " " 2007 г

Ученый секретарь диссертационного совета

Л А Осипов

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

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

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

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

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

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

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

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

Методы исследования Для достижения поставленной цели в работе рассматриваются следующие основные задачи

• построение оптимальных помехоустойчивых кодов,

• построение лучших из известных множеств, свободных от покрытий,

• построение алгоритмов быстрых вычислений на эллиптических кривых

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

Научная новизна работы заключается в следующем

• предложен метод построения подкласса оптимальных алгеброгеомет-рических (эллиптических) кодов,

• найдено истинное расстояние для построенного подкласса оптимальных эллиптических кодов,

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

• предложен новый алгоритм для умножения скаляра на точку в поле характеристики 3, выигрывающий по сложности у известных методов

Практическая ценность и реализация результатов. Практическая ценность работы заключается в том, что в ней предложен способ построения нового оптимального подкласса g-ичных кодов Использование таких кодов позволяет улучшить существующие системы передачи информации Кроме того, были предложены эффективные методы умножения скаляра на точку на эллиптической кривой, обладающие преимуществами перед известными методами Публикации Основные результаты работы отражены в 8 публикациях Из них 2 работы опубликованы в журналах, входящих в список ВАК Основные положения, выносимые на защиту

• подкласс оптимальных алгеброгеометрических (эллиптических) кодов, лежащих на верхней границе существования,

• метод определения истинного расстояния и размерности для кодов из полученного подкласса оптимальных кодов,

• множества свободные от покрытий, на основе алгеброгеометрических (эллиптических) кодов

Структура работы Диссертация состоит из введения, трех глав, заключения и списка использованной литературы Работа изложена на 93 страницах Основное содержание работы включает 11 рисунков, 8 таблиц и 14 алгоритмов

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

Вторая глава посвящена вопросам использования кодов, исправляющих ошибки, для построения множеств, свободных от покрытий Кроме того, произведено сравнение множеств, свободных от покрытий, построенных па эллиптических кодах и кодах Рида-Соломона

Третья глава посвящена вопросам быстрого умножения скаляра на точку

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

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

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

В параграфе 1 1 рассмотрено краткое введение в результаты алгебраической геометрии В параграфе 1 2 представлен общий подход к построению алгеброгеометрических кодов В параграфе 1 3 рассмотрены некоторые конструкции алгеброгеометрических кодов Также показано, что среди алгеброгеометрических кодов есть оптимальные, лежащие на верхней границе Грайсмера 4 Ключевым объектом, необходимым для задания алгеброгеометрических кодов, является поле функций (<-£), заданное на гладкой неприводимой кривой X С помощью дивизора (3 может быть задано линейное пространство функций Ь(0) 6 ¥Ч(Х) Алгеброгеометрическим кодом называется множество

С{Х,Т,С) = {(/(РО, ,/(Р„)) /е £(<?)} с

где V — {Р\,Р2, ,Ри) — это множество Ед-рациональных точек на X, V П виррО — 0 а V — это подмножество множества точек проективного пространства Р2

Параметры такого (п, к, й)д кода можно оценить как

k>deg(G) + l-g,

где д — это род гладкой неприводимой кривой Кроме того, параметры алгсброгеометричсского кода будут удовлетворять неравенству

п+1>к+й>п+1-д

Рассматривая оценки на параметров алгеброгеометрических кодов, можно сформулировать необходимое условие, выполнение которого будет означать, что код лежит на границе Грайсмера Лемма 1 Если д удовлетворяет неравенству

к-1

1

1.04

тогда алгеброгеометрический код лежит на границе Грайсмера

Рассмотрим неприводимые гладкие однородные кривые вида

У22 + сцХУг + а3Уг2 = X3 + а2Х2г + а4хг2 + а6г3, аг е ¥д (1)

Кривые такого вида называются эллиптическими, коды, построенные на таких кривых, также носят название эллиптических Род д кривой (1) будет равен единице Можно показать что среди кодов, построенных на кривой, заданной уравнением (1), есть коды, лежащие на границе Грайсмера Теорема 1 Эллиптический код с ¿> д и д > 4 лежит на границе Грайсмера

Можно показать, что параметры кода удовлетворяют следующему соотношению

Следствие 1 Параметры любого эллиптического кода с с1 > ди а > 4 удовлетворяют равенству

п = к + <1

Кроме того, для эллиптических кодов, лежащих на границе Грайсмера удается найти их истинное расстояние

Следствие 2 Если у эллиптического кода к > 2 (1> д и д > 4, то (I — п - deg(G)

Таким образом, в данной главе было доказано, что часть эллиптических кодов лежит на границе Грайсмера

Во второй главе рассматриваются вопросы использования кодов, исправляющих ошибки, для построения множеств, свободных от покрытий (МСП) Произведено сравнение множеств, свободных от покрытий, построенных на эллиптических кодах и кодах Рида,- Соломона

В параграфе 2 1 вводятся основные определения и обозначения В параграфе 2 2 производится сравнение множеств свободных от покрытий, построенных с помощью кодов Рида-Соломона, и множеств, свободных от покрытий, построенных с помощью эллиптических кодов, введенных в предыдущей главе В параграфе 2 3 приводятся примеры использования множеств, свободных от покрытий

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

• многоканальной связи,

• распознавания образов

• построения плана эксперимента,

• защиты авторских прав,

• построения многоразовой подписи

Определение 1 Пусть X — это некоторое множество элементов Пусть В = {Вх, В2, , Вт} — это множество, состоящее из подмножеств множества X Подмножество Вг па.ювем блоком Если любой набор из г блоков удовлетворяет

г

Вк0£{)Вк}, з=1

тогда пара (X, В) будет определять множество, свободное от покрытий Множество, свободное от покрытий, характеризуются следующим набором параметров

• N — мощность множества X,

• Т — количество блоков, мощность множества В

• г — количество непокрывающих блоков

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

X = {1,2, ,п} х¥ч (2)

Для каждого кодового слова с = (сх, сг, , с„) определим подмножества мощности п из X как

Вс = {(г>Сг) 1 <1<п} (3)

Тогда тожество В определяется как

В = {Вс, с € С} (4)

Таким образом, определяется пара (X, В), образующая множество, свободное от покрытий.

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

N = пд, Т = д\

п-1

г = -1

п — а

С помощью (п, к, (Г]ч кода Рида-Соломона может быть получено множество, свободное от покрытий, с параметрами

N<q2+q, Т = дк,

г= -2-1

С помощью (п,к,с1)я эллиптического кода может быть получено множество свободное от покрытий, с параметрами

N<q2 + q+l2Jq¡q, Т = й\

к

Известно что множества, свободные от покрытий, построенные на кодах Рида-Соломона, близки к верхним границам существования Соотношения между параметрами эллиптических кодов Грайсмера и кодов Рида-Соломона близки Таким образом, становится актуальным вопрос о поиске множеств, свободных от покрытий, лучших, чем множества свободные от покрытий, полученные из кодов Рида-Соломона

При построении множества, свободного от покрытий, необходимо стремиться к такому выбору параметров (п, к, <1)д кода, при котором для фиксированного г, N ш, Т —» шах

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

Фиксируя г и Т, можно построить минимальный код Рида-Соломона Д5/, который будет соответствовать минимальному множеству, свободному от покрытий Увеличение на единицу (I у кода Д5/ приведет к тому, что его параметры изменятся (п 4- 1, к, в, + 1)д, увеличивая далее расстояние этого кода до тех пор пока п +1 < д + I, получим множество, свободное от покрытий, с одними и теми же величинами г и Т. но большими значениями N

Откладывая па графике но оси абсцисс величины, соответствующие значению N, а по оси ординат величины, соответствующие значению Т, получим множество точек, соответствующие множеству, свободному от покрытий, с одними и теми же величинами г и Г для кода Д5/ Это множество точек будет лежать на отрезке, перпендикулярном оси ординат Кроме того точки, принадлежащие некоторому множеству, свободному от покрытий, оказавшиеся строго ниже этого отрезка, будут хуже, чем множества, свободные от покрытий, построенные на коде Л5/ Эта ситуация показана на рисунке 1

Для того, чтобы уменьшить N для множества, свободного от покрытий, сооч встс I вугощему минимальному коду Д5/ необходимо уменьши гь значение параметра к такого кода, что приведет к снижению Т Укорочение минимального кода по <1 приведе! к уменьшению параметра г Укорочение по к кода Н31. приведет к получению минимального кода НЗц, еще одно укорочение по к приведет к минимальному коду Д5гл Множества,

Рис 1 Параметры множеств, свободных от покрьиий, построенных на кодах Рида-Соломона с фиксированными Тяг

Рис 2. Параметр множеств, свободных от покрытий, построенные на кодах Ридаг-Соломова с фиксированным г

свободные от покрытий, полученные с помощью кодов Яви, НЭт показаны на рисунке 2

Ряс 3 Параметры множеств, свободных от покрытий, построенных на кодах Рида-Соломона и эллиптических кодах Грайсмера с г = 4

г=2

«О 530 560 630

N

Рис. 4. Параметры множеств, свободных от покрытий, построенные на кодах Рида-Соломона и эллиптических кодах с г — 2

Код Д5/II укорачивается до тех пор, пока множество, свободное от покрытий, соответствующее коду с меньшим ц, не будет лучше по параметрам N аТ множества, свободного от покрытий, полученного из последнего укорочения кода Эта ситуация показана на рисунке 2 для кода ЯБц,-На рисунке 3 представлен пример, который показывает, что с помощью множеств, свободных от покрытий, построенных на эллиптических кодах Грайсмера, параметры множеств, свободных от покрытий, могут быть выбраны более гибко

На рисунке 4 представлен другой пример поведения множеств, свободных от покрытий, построенных на эллиптическом коде Множество, свободные от покрытий, полученное из эллиптического кода (27,13,14)19, лучше, чем множество, свободные от покрытий, полученные из кода Рида-Соломона (43,12,12)23 Множество, свободное от покрытий, построенное на эллиптическом коде Грайсмера (27,13,14)гз, попадает между двумя минимальными множествами, свободными от покрытий, построенными на кодах

Рида-Соломона

Таким образом использование эллиптических кодов может улучшить выбор параметров множеств, свободных от покрытий, по сравнению с множествами, свободными от покрытий, построенных на кодах Рида-Соломона То есть существует множество точек, в которых множества, свободные от покрытий, построенные на эллиптических кодах, лучше чем множества, свободные от покрытий, построенные на кодах Рида-Соломона

В третьей главе рассматриваются быстрые алгоритмы вычислений на эллиптических кривых

В параграфе 3 1 — 35 приводится понятие группы точек на эллиптической кривой и описываются необходимые формулы для сложения точек, в параграфе 3 6 приводятся известные алгоритмы для умножения скаляра на точку В параграфе 3 7 рассматриваются алгоритмы умножения скаляра на точку в поле характеристики 3

Задача умножения скаляра на точку состоит в быстром вычислении следующей суммы

кР = Р + Р+ + Р

у " V

к

Эффективные алгоритмы вычисления кР могут быть важны, например, для криптографических приложений

В работе рассматривается неособая кривая над полем Р3™

у2 = ж3 + ах2 + Ъх + с (5)

Над точками кривой (5) определены следующие операции

• Сложение точек- (х3,у3) = (агьу\) + {хъ,Уъ)

хз = Л2 — а — XI — Х2 Уз = Л(х1 - яз) - г/1 д _ 3/2 — У1 х2 - Хг

• Удвоение точки: (х2,г/2) = 2(11,2/1)

Х2 — А2 — о — 2х\ г/2 = А(а:1 - ж2) - Уг 2ах1 + Ь = 2У1

В работе предложена модификация метода Коблица-Солиноса для поля харак гсристики 3

Пусть Е— это эллиптическая кривая вида (5), определенная над конечным полем Рзт, причем а, Ъ, с £ Рз Поскольку кривая определена над Рзт,

то для нее справедливо, что, если Р = (я:,у) — точка на кривой Е то и точка (ж3, у3) будет также лежать на кривой Е Следующее свойство

(х9,у9)-г(х3,у3) + 3(х,у)=<Э (6)

верно для каждой точки {х,у) на Е, где t = |]Уу3(1) — (3 + 1)) и —

это количество ¥з-рациональных точек на эллиптической кривой Отображение г определяется как

т(х,у) = (х3,/) Тогда (6) перепишется в виде

г(т(Р))-*г(Р)+ЗР = 0 (7)

дня всех Р 6 Е Решением уравнения будет

Скаляр £ может быть представлен как ряд

к = к0 + кхт + + ¿¡-хг'-1, (8)

где г = Ш/ЕЕН и ^ 6 {о, 1, -1} Тогда

1-1

kP = J2hr1(P)

Для нахождения представления к по основанию т используется теорема 2 Теорема 2 а+Ът делится на т тогда и только тогда, когда а = 0 mod 3 Предложенный в работе алгоритм 1 находит представление числа вида х + уг по основанию т Поскольку

rm(x,v) = От3",/") = (х,у),

или

Ттпр = (9)

или

rm = 1 (10)

Тогда

a = k mod (тш - 1), кР = аР

Алгоритм 1 Знаковое тернарное представление х + yr по основанию г

1 Вход- х, у, t

2 Выход: Знаковое тернарное представление по основанию г

3 а <— х,Ъ <— у

4 repeat

5 к, *— a mod 3 > кг е {0, ±1}

6 if кг = 2 then кг = -1

7 end if

8 а <— а + кг

9 к 1 — fc'j

10 (а,Ь)-(£+Ь,-|)

11 г <— г + 1

12 until а ^ 0 and Ь Ф О

13 return(fcj_i, , ki, kfj)

Для того чтобы уменьшить длину последовательности, используется тот факт, что кР = аР

Если к выбран порядка Зт, то длина знакового тернарного представления по основанию г составит к т разрядов

Для нахождения а вычисляется значение гт — 1 в виде а + Ът, где о, 6 € Z, и затем используется алгоритм, который вычисляет о; mod (а + Ът) Первая задача решена применением рекурсивной процедуры Пусть То = 0, Тх = 1 и

Т*=ЙГ/к_1-ЗГ*_2 (11)

для к > 2 Легко увидеть, что

тт = - 3Тт-г (12)

Далее вычисляется значение к mod (а + Ьт) Для иллюстрации алгоритма вычисления остатка по модулю комплексного числа в работе выбирается кривая у2 = х3 + 2х'2 + 2 с t — 2, характеристическое уравнение которой будет иметь следующий вид

т2 = 2т - 3,

и корень

г = 1 + JV^

Предложенный в работе алгоритм 2 находит остаток комплексного числа Представляя кР как

кР =А:г_!Г(-1(Р) -I- кг-.2т1-г{Р) + hr1 (Р) +■ к0т°(Р) =

= fci_lT'-1(i3)+ + Jfct.-» , г^+ЧЛ + fc(,-1)T^(P)+ 2 ' 2

+к,,-1> 1т^~1(Р)+ + к1т1(Р)+к0т°{Р),

Алгоритм 2 Нахождение остатка при делении на комплексное число

1 Вход: а, Ь, с, d

2 Выход е, / е + /т «— (а + Ът) mod (с + dr)

3 д be — ad

4 h <— ас + 2ad -)- 3bd

5 m <— (с + ¿)2 + id?

6 p<— [/i/mj

7 <? Is1/"»]

8 e а — pc + 3 qd

9 / <— b — qc-pd- 2qd

10 return e, / _ ___

можно переписать

2 — i ("13) rHfct.-!), + feiP) 4- r°(fc(,-D Q +■ kpP),

где Q = г^тг^(Р)

Используя представление (13), можно улучшить метод, полученный из прямой модификации метода Коблица-Солиноса

Для к ~ Зт средняя сложность алгоритма 3 составит

+ (14)

и

Алгоритм 3 Метод разбиения _________

2 Выход: кР

3 Использовать (11) для нахождения числа с 4- dr = тт — 1

4 Использовать алгоритм 2 для нахождения е + fr = к mod с + dr

5 Использовать алгоритм 1 для вычисления знакового представления к

6 if I mod 2 = 1 then

7 l*-l + 1

8 AT;-! <- 0

9 end if

10 Q <~ ri(P)

11 Предвычислить P + Q,P - Q,-P - Q-P + Q

12 R *— О

13 for г <— 1/2 — 1,0 do

14 R «— г Л

15 5 <— h/2+iQ + k,P c- 5 предвычислено

16 R *- R + S

17 end for is return(j?)

Операции Сложность метода в среднем

Представление по основанию т Щ(*-А + ттМ

Обощающий метод 2 А+ ЩА + ттМ

Таблица 1. Сравнительная таблица методов

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Основные результаты работы можно сформулировать следующим образом

1 Найден подкласс эллиптических кодов, лежащих на границе Грай-смера

2 Для кодов из этого подкласса показано, что их истинное совпадает с конструктивным

3 Показано, что множества, свободные от покрытий, полученные из кодов Грайсмера, являются лучшими из известных

4 Модифицированы алгоритмы быстрого умножения скаляра на точку в поле характеристики 3

5 Предложен новый алгоритм быстрого умножения скаляра на точку на эллиптической кривой в поле характеристики 3, обладающий преимуществами перед известными методами

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Степанов М В , Беззатеев С В Алгеброгеометрические коды на границе Грайсмера,// Информационно-управляющие системы 2005 Т 16 №3 С 47-50

2 Степанов М В Методы вычислений на эллиптических кривых в поле характеристики три// Системы управления и информационные технологии//2007 Т28 №2 2 С 296-298

3 Степанов М В Система на эллиптических кривых для отслеживания пользователей// Сборник докладов научной сессии аспирантов СпбГУАП 2004 С 269-271

4 Степанов М В , Беззатеев М.В Использование эллиптических кодов дня построения непокрывающих множеств// Сборник докладов наг учной сессии аспирантов СпбГУАП 2005 С 200-203

5 Степанов М В , Беззатеев М В Вычисления на эллиптических кривых в полях характеристики 3// Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601852, 2006

6 Stepanov М and Bezzateev S Algebraic-geometry codes on griesmer bound // In Proceedings of Algebraic and Combinatorial Coding Theory, ACCT-10, Zvenigorod, Russia, pages 256-259, 2006

7 Stepanov M , Bezzateev S , Jung E , and Yi J Elliptic-gnesmer codes and their applications to cover-free families construction / / In 8th International Symposium on Systems and Information Security, 2006

8. Augot D , El-Khamy M., McEhece R J , Parvaresh F , Stepanov M , Vardy A Algebraic List Decoding of Reed-Solomon product codes //In Proceedings of Algebraic and Combinatorial Coding Theory, ACCT-10, Zvenigorod, Russia, pages 210-213, 2006

Формат 60x841\16 .Бумага офсетная Печать офсетная Тираж 100. экз. Заказ №5ЙЦ

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

Введение

1 Алгеброгеометрические коды

1.1 Введение в алгебраическую геометрию

1.1.1 Аффинные и проективные многообразия.

1.1.2 Локальное кольцо в точке.

1.1.3 Дивизоры. Линейное пространство, заданное на дивизоре.

1.2 Коды на кривых.

1.3 Некоторые алгеброгеометрические коды.

1.3.1 Коды рода ноль.

1.3.2 Эллиптические коды.

1.3.3 Эллиптические коды Грайсмера.

1.3.4 Коды Эрмита.

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

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

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

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

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

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

Методы исследования. Для достижения поставленной цели в работе рассматриваются следующие основные задачи:

• построение оптимальных помехоустойчивых кодов,

• построение лучших из известных множеств, свободных от покрытий,

• построение алгоритмов быстрых вычислений на эллиптических кривых.

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

Научная новизна работы заключается в следующем:

• предложен метод построения подкласса оптимальных алгеброгеометрических (эллиптических) кодов;

• найдено истинное расстояние для построенного подкласса оптимальных эллиптических кодов;

• с помощью эллиптических кодов построены множества, свободные от покрытий, параметры которых будут лучшими из известных;

• предложен новый алгоритм для умножения скаляра на точку в поле характеристики 3, выигрывающий по сложности у известных методов.

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

Публикации. Основные результаты работы отражены в 8 публикациях. Из них 2 работы опубликованы в журналах, входящих в список ВАК.

Основные положения, выносимые на защиту:

• подкласс оптимальных алгеброгеометрических (эллиптических) кодов, лежащих на верхней границе существования;

• метод определения истинного расстояния и размерности для кодов из полученного подкласса оптимальных кодов;

• множества, свободные от покрытий, на основе алгеброгеометрических (эллиптических) кодов.

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

Основные результаты данной главы могут быть сформулированы следующим образом:

• доказано, что подкласс эллиптических кодов лежит на границе Грайсмера;

• доказано, что для эллиптических кодов, лежащих на границе Грайсмера, истинное расстояние равно минимальному.

Глава 2

Множества, свободные от покрытий

В данной главе рассматриваются множества, свободные от покрытий (МСП). Впервые этот объект был введен Каутцом (Kautz) и Синглтоном (Singleton) в 1964 году в работе [69]. Каутц и Синглтон назвали этот объект "superimposed codes".

В общем случае под МСП можно понимать множество векторов, в котором объединение любых г векторов не покроет полностью никакой другой вектор из множества.

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

Позднее введенный Синглтоном и Каутцом объект рассматривался в работах [50, 51, 10, 52, 80, 74].

В 1985 году Ердош [Erdos], Франкл [Frankl] и Фюреди [Fiiredi] [55] ввели множества, свободные от покрытий, как комбинаторный объект.

В 1987 году в работе Хванга [Hwang] [66] МСП были введены для задачи построения плана экспериментов. Эта задача появилась еще во времена второй мировой войны и была связана с необходимостью построения схем тестирования большого количества образцов крови. Целью являлось построение плана с минимальным количеством экспериментов, с помощью которого можно было бы протестировать максимальное количество образцов и выявить среди них дефектные.

В 1997 году в работах [44, 43, 68] было предложено использовать МСП для задач распознавания образов. Такие приложения возникают при анализе текстов поисковыми серверами и в системах коррекции орфографии. Например, если слово написано с ошибкой вида перестановки двух соседних символов, то составляя из слова код, полученный наложением кодов символов, построенных как вектора МСП, получим некоторый код, который будет равен коду полученному из слова, если бы оно было написано без ошибки. Далее, используя таблицу соответствия кодов слов и самих слов, можно исправить ошибку.

Существуют различные способы построения МСП: на схемах, латинских квадратах и кодах, исправляющих ошибки [69]. С помощью границы существования МСП, приведенной в работе [10], можно показать, что МСП, построенные с помощью кодов Рида-Соломона, будут лежать близко от границы. Поэтому параметры МСП на кодах Рида-Соломона считаются лучшими из известных. Соответственно задача построения подоптимальных МСП на кодах, исправляющих ошибки, лучших чем коды Рида-Соломона, является актуальной.

В данной главе будет проведено сравнение параметров МСП, построенных с помощью кодов Рида-Соломона, и МСП, построенных на эллиптических кодах Грайсмера [21]. В параграфе 2.1 вводятся основные определения и обозначения. В параграфе 2.2 производится сравнение МСП, построенных с помощью кодов Рида-Соломона, и МСП, построенных с помощью эллиптических кодов, введенных в предыдущей главе. В параграфе 2.3 приводятся примеры использования МСП.

2.1 Определения и обозначения

Рассмотрим определение множеств, свободных от покрытий, которое предлагается в работе [92].

Определение 18 Пусть X это некоторое множество элементов. Пусть В = {В\, В2,., Вт} это множество, состоящее из подмножеств множества X. Подмножество Bi назовем блоком. Если любой набор из г блоков удовлетворяет г

Bko£\jBk], i=i тогда пара (X, В) будет определять множество, свободное от покрытий (МСП).

Рассмотрим графическую интерпретацию МСП. На рисунке 2.1 показан пример, когда три произвольных блока из множества X не покрывают другой произвольный блок.

МСП характеризуются следующим набором параметров:

• N — мощность множества X;

• Т — количество блоков, мощность множества 5;

• г — количество непокрывающих блоков.

Рис. 2.1. Множество, свободное от покрытий

2.2 МСП и коды, исправляющие ошибки

В работах [55, 69, 96] было показано, как построить МСП на дизайнах, латинских квадратах и кодах. В работе [10] была приведена граница на мощность множества X. Соотношения параметров МСП представлены в таблице 2.1.

Объект Оценка на |Х|

Дизайны 0(Т)

Латинские квадраты 0(Тг'2)

Кодовые конструкции (Коды Рида-Соломона) о(^-гН2(Т))

Нижняя теоретическая граница c10;;(r)i°g2co

Заключение

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

1. найден подкласс эллиптических кодов, лежащих на границе Грайсмера;

2. для кодов из этого подкласса показано, что их истинное расстояние совпадает с конструктивным;

3. показано, что множества, свободные от покрытий, полученные из кодов Грайсмера, являются лучшими из известных;

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

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

1. Б.И. Белов, В.Н. Логачев, В.П. Сандимиров. Построение класса линейных двоичных кодов достигающих границы Варшамова-Грайсмера. Проблемы передачи информации, 10(3):211—217, 1974.

2. Э. Берлекэмп. Алгебраическая теория кодирования. М.: Мир, 1971.

3. Р. Блейхут. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

4. А.А. Болотов , С.Б. Гашков , А.Б. Фролов,. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.

5. Б.Л. Ван дер Варден. Алгебра. М.: Наука, 1976.

6. И.М. Виноградов. Основы теории чисел. М.:Наука, 1965.

7. С.Г. Влэдуц, Д.Ю. Ногин,М.А. Цфасман. Алгеброгеометрические коды: основные понятия. М.:Независимый московский университет, 2003.

8. В.Д. Гоппа. Коды ассоциированные с дивизорами. Проблемы передачи информации, 13:22-27, 1977.

9. В.Д. Гоппа. Коды на алгебраических кривых. Доклады Академии Наук СССР, 259:1289-1290, 1981.

10. А.Г. Дьячков , В.В. Рыков. Границы на длину дизъюнктивных кодов. Проблемы передачи информации, (18):7—13, 1981.

11. Т. Касами , Н. Токура , Е. Ивадари , Я. Инагаки. Теория кодирования. М.: Мир, 1978.

12. Н. Коблиц. Курс теории чисел и криптографии. М.: Научное издательство ТВП, 2001.

13. Н. Коблиц. Введение в эллиптические кривые и модулярные формы. М.: Мир, 1998.

14. Р. Лидл , Г. Нидеррайтер. Конечные поля, Т. 1,2. М.: Мир, 1988.

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

16. В.В. Острик , М.А. Цфасман. Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые. М.: МЦНМО, 2005.

17. У. Питерсон , Э. Уэлдон. Коды, исправляющие ошибки. М.: Мир, 1976.

18. А.Г. Ростовцев. Алгебраические основы криптографии. Санкт-Петербург: НПО "Мир и Семья", 2000.

19. Ю.Л. Сагалович. Разделяющие системы. Проблемы передачи информации, 30(2):14—35, 1994.

20. Н. Смарт. Криптография. М.: Техносфера, 2006.

21. М.В. Степанов , С.В. Беззатеев. Алгеброгеометрические коды на границе Грайсмера. Информационно-управляющие системы, (3):47-50, 2005.

22. М.В. Степанов. Система на эллиптических кривых для отслеживания пользователей. Сборник докладов научной сессии аспирантов СпбГУАП, pages 269-271, 2004.

23. М.В. Степанов , С.В. Беззатеев. Алгеброгеометрические коды на границе Грайсмера. Вопросы передачи и защиты информации:Сборник статей/СпбГУАП. Спб, pages 69-73, 2006.

24. М.В. Степанов , С.В. Беззатеев. Использование эллиптических кодов для построения непокрывающих множеств. Сборник докладов научной сессии аспирантов СпбГУАП, pages 200-203, 2005.

25. М.В. Степанов , С.В. Беззатеев. Вычисления на эллиптических кривых в полях характеристики 3. Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601852, 2006.

26. М.В. Степанов. Методы вычислений на эллиптических кривых в поле характеристики три. Системы управления и информационные технологии, 28(2.2):296-298, 2007.

27. К.Э. Шеннон. Работы по теории информации и кибернетики. М.: Иностранная литература, 1963.

28. N. Alon. Explicit contractions of exponential sizes families of k-independent sets. Discrete Math., (58):191-193, 1986.

29. M. Atici, S. S. Magliveras, D. R. Stinson, and W.D. Wei. Some recursive constructions for perfect hash families. Journal of Combinatorial Designs, 4(5):353—363, 1996.

30. D.J. Balding and D.C. Torney. Optimal pooling designs with error detection. Journal of Combinatorial Theory, 74(1):131-140, 1996.

31. A. Barg and G. A. Kabatiansky. A class of i.p.p. codes with efficient identification. J. Complexity, 20(2-3): 137-147, 2004.

32. I.F. Blake, G. Seroussi, and N.P. Smart. Elliptic Curves in Cryptography. Cambridge University Press, 1999.

33. M. Boer. Almost mds codes. Design Codes Cryptography, 9(2):143-155, 1996.

34. D. Boneh and J. Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory, 44(5): 1897-1905, 1998.

35. I. Bouchemakh and K. Engel. Interval stability and interval covering property in finite posets. Discrete Math., (9):163-175, 1992.

36. I. Bouchemakh and K. Engel. The order-interval hypergraph of a finite poset and the konig property. Discrete Math., (170):51—61, 1997.

37. M. Brown, D. Hankerson, J. Lopez, and A. Menezes. Software implementation of the nist elliptic curves over prime fields. In CT-RSA, pages 250-265, 2001.

38. K. A. Bush, W. T. Federer, H. Pesotan, and D. Raghavarao. New combinatorial designs and their application to group testing. Journal of Statistical Planning and Inference, (10):335—343, 1984.

39. B. Chor, A. Fiat, and M. Naor. Tracing traitors. In CRYPTO, pages 480491, 1994.

40. B. Chor, A. Fiat, M. Naor, and B. Pinkas. TVacing traitors. IEEE Transactions on Information Theory, 46(3):893-910, 2000.

41. M. Ciet, Т. Lange, F. Sica, and J. Quisquater. Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. In EUROCRYPT, pages 388-400, 2003.

42. C. J. Colbourn and J. H. Dinitz. CRC Handbook of Combinatorial Designs. CRC Press, 1996.

43. R. Cole and R. Hariharan. Tree pattern matching and subset matching in randomized o(n log^m) time. In STOC, pages 66-75, 1997.

44. R. Cole, R. Hariharan, and P. Indyk. Tree pattern matching and subset matching in deterministic (log^ )-time. In SODA, pages 245-254, 1999.

45. M. Franklin D. Boneh. Identity-based encryption from the weil pairing. In CRYPTO, pages 213-229, 2001.

46. Y. Desmedt, R. Safavi-Naini, H. Wang, L.M. Batten, C. Charnes, and J. Pieprzyk. Broadcast anti-jamming systems. Computer Networks, 35(2-3):223-236, 2001.

47. S.M. Dodunekov and I.N. Landgev. On near MDS codes, report LiTH-ISY-R-1563, Dept. of Electrical Engineering. Linkoping University, 1994.

48. Y. Driencourt and J.F. Michon. Remarques sur les codes geometriques. Compt.Rend., 301:15-17, 1985.

49. D.Z. Du and F. K. Hwang. Combinatorial Group Testing and Applications. World Scientific, 1993.

50. A.G. Dyachkov, A.J. Macula, and V.V. Rykov. On optimal parameters of a class of superimposed codes and designs. In IEEE Int. Symp. Information Theory, pages 363-364, 1998.

51. A.G. D'yachkov, A.J. Macula, and V.V. Rykov. New constructions of superimposed codes. IEEE Transactions on Information Theory, 46(1):284-290, 2000.

52. A.G. Dyachkov, V.V. Rykov, and A.M. Rashad. Superimposed distance codes. Problems of Control and Information Theory, (18):237—250, 1989.

53. M.E. Dyer, T.I. Fenner, A.M. Frieze, and A. Thomason. On key storage in secure networks. Journal of Cryptology, 8(4):189-200, 1995.

54. K. Engel. Interval packing and covering in the boolean lattice. Combinatorics, Probability & Computing, 5:373-384, 1996.

55. P. Erdos, P. Frankl, and Z. Fiiredi. Families of finite sets in which no set is covered by the union of two others. . Journal of Combinatorial Theory, (33):158—166, 1982.

56. A. Faldum and W. Willems. Codes of small defect. Des. Codes Cryptography, 10(3):341-350, 1997.

57. P. Frankl. On sperner families satisfying an additional condition. Journal of Combinatorial Theory, (20): 1-11, 1976.

58. P. Frankl and V. Rodl. Near perfect coverings in graphs and hypergraphs. Europ. J. Combinatorics, (6):317—326, 1985.

59. Z. Fiiredi. On r-cover-free families. Journal of Combinatorial Theory, 73(1):172—173, 1996.

60. E. Gafni, J. Staddon, and Y.L. Yin. Efficient methods for integrating traceability and broadcast encryption. In CRYPTO, pages 372-387, 1999.

61. R. Gallant, R. Lambert, and S. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In CRYPTO, pages 388-400, 2001.

62. J. A. Garay, J. Staddon, and A. Wool. Long-lived broadcast encryption. In CRYPTO, pages 333-352, 2000.

63. A.G. Garcia and H. Stichtenoth. Algebraic function fields over finite fields with many rational places. IEEE Transactions on Information Theory, 41(6):1548—1563, 1995.

64. D. Hankerson, A. Menezes, and S. Vanstone. Guide to Eliptic Curve Cryptography. Springer, 2004.

65. H. D. L. Hollmann, J. H. van Lint, M. G. Linnartz Jean-Paul, and L. M. G. M. Tolhuizen. On codes with the identifiable parent property. Journal of Combinatorial Theory, 82(2):121-133, 1998.

66. F. K. Hwang. A method for detecting all defective members in a population by group testing. J. Amer. Statist. Assoc., (67):605-608, 1972.

67. F. K. Hwang and V. T. Sos. Non-adaptive hypergeometric group testing. Studia Sci. Math. Hungar., (22):257-263, 1987.

68. P. Indyk. Deterministic superimposed coding with applications to pattern matching. In FOCS, pages 127-136, 1997.

69. W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory, (10):363-377, 1964.

70. E. Knill, W. J. Bruno, and D. C. Torney. Non-adaptive group testing in the presence of errors. Discrete Applied Mathematics, 88(1-3):261—290, 1998.

71. N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computations, 48(1):203—209, 1987.

72. N. Koblitz. Cm-curves with good cryptographic properties. In CRYPTO, pages 279-287, 1991.

73. N. Koblitz. An elliptic curve implementation of the finite field digital signature algorithm. In CRYPTO, pages 327-337, 1998.

74. J. Korner and M. Lucertini. Compressing inconsistent data. IEEE Transactions on Information Theory, 40(3):706-715, 1994.

75. R. Kumar, S. Rajagopalan, and A. Sahai. Coding constructions for blacklisting problems without computational assumptions. In CRYPTO, pages 609-623, 1999.

76. R Laval and S. Abdul-Jabbar. Decoding of superimposed codes in multiaccess communication, pages 186-210, 1988.

77. W. Meier and 0. Staffelbach. Efficient multiplication on certain nonsupersingular elliptic curves. In CRYPTO, pages 333-344, 1992.

78. V. Miller. Use of elliptic curves in cryptography. In CRYPTO, pages 279287, 1985.

79. C. J. Mitchell and F. C. Piper. Key storage in secure networks. Discrete Applied Mathematics, (21):215-228, 1988.

80. Q. A. Nguyen and T. Zesel. Bounds on constant weight binary superimposed codes. Problems of Control and Information Theory, (17):223-230, 1988.

81. D. Page and N.P. Smart. Hardware implementation of finite fields of characteristic three. In CHES, pages 529-539, 2002.

82. J. Pieprzyk, H. Wang, and C. Xing. Multiple-time signature schemes against adaptive chosen message attacks. In Selected Areas in Cryptography, pages 88-100, 2003.

83. K. A. S. Quinn. Bounds for key distribution patterns. Journal of Cryptology, 12(4):227—239, 1999.

84. V. Rodl. On a packing and covering problem. Europ. J. Combin., (5):69-78, 1985.

85. M. Ruszinko. On the upper bound of the size of the r-cover-free families. Journal of Combinatorial Theory, (66):302—310, 1994.

86. R. Safavi-Naini and H. Wang. New results on multi-receiver authentication codes. In EUROCRYPT, pages 527-541, 1998.

87. J. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, 1986.

88. J.A. Solinas. Efficient arithmetic on koblitz curves. Designs, Codes and Cryptography, 19(2/3):195-249, 2000.

89. V. T. Sos. An additive problem in different structures. In Second International Conference on Graph Theorey, Combinatorics, Algorithms, and Applications, pages 486-510, 1989.

90. J. Sperner. Ein satz tiber untermengen einer endlichen menge. Math., (27).'544-548, 1928.

91. J. Staddon, D.R. Stinson, and R. Wei. Combinatorial properties of frameproof and traceability codes. IEEE Transactions on Information Theory, 47(3): 1042-1049, 2001.

92. M. Stepanov and S. Bezzateev. Algebraic-geometry codes on griesmer bound. In AC С T-10, pages 256-259, 2006.

93. M. Stepanov, S. Bezzateev, E. Jung, and J. Yi. Elliptic-griesmer codes and their applications to cover-free families construction. In 8th International Symposium on Systems and Information Security, 2006.

94. H. Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, 1993.

95. D.R. Stinson, T. van Trung, and R. Wei. Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. Journal of Statistical Planning and Inference, (86):595-617, 2000.

96. D.R. Stinson and R. Wei. Combinatorial properties and constructions of traceability schemes and frameproof codes. SI AM J. Discrete Math., 11(1):41—53, 1998.

97. D.R. Stinson and R. Wei. Key preassigned traceability schemes for broadcast encryption. In Selected Areas in Cryptography, pages 144-156, 1998.

98. D.R. Stinson and R. Wei. Generalized cover-free families. Discrete Mathematics, 279(1-3):463-477, 2004.

99. D.R. Stinson, R. Wei, and L. Zhu. Some new bounds for cover-free families. Journal of Combinatorial Theory, 90(l):224-234, 2000.

100. M. A. Tsfasman, S. G. Vladut, and T. Zink. Modular curves, shimura curves, and goppa codes, better than the varshamov-gilbert bound. Math. Nachrichten, 109:21-28, 1982.

101. J.L. Walker. Codes on Curves. Amer Mathematical Society, 2000.

102. H. Wang and C. Xing. Explicit constructions of perfect hash families from algebraic curves over finite fields. J. Comb. Theory, 93(1):112—124, 2001.

103. L. Xu. Improvement on parameters of goppa geometry codes from maximal curves using the vladut-xing method. IEEE Transactions on Information Theory, 51 (6):2207—2210, 2005.