Алгеброгеометрические методы избыточного кодирования информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Степанов, Михаил Владимирович

• Степанов, Михаил Владимирович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Степанов, Михаил Владимирович

Введение

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, обладающий преимуществами перед известными методами.

Список литературы диссертационного исследования кандидат технических наук Степанов, Михаил Владимирович, 2007 год

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.