Другие журналы
Сетевое издание Математика и математическое моделирование

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл. № ФС 77-61857. ISSN 2412-5911

Односторонние функции и композиция проблем сопряжённости и дискретного логарифмирования в C(3)-T(6)-группах

Математика и математическое моделирование # 05, октябрь 2015
DOI: 10.7463/mathm.0515.0820675
Файл статьи: Mathm_Oct2015_043to063.pdf (391.51Кб)
автор: Безверхний Н. В.1,*

УДК 519.40

1 МГТУ им. Н.Э. Баумана, Москва, Россия

В данной работе рассматривается возможность построения односторонней функции в группах с условиями C(3)-T(6). При этом используются следующие алгоритмы.  Алгоритм, решающий проблему вхождения в циклическую подгруппу, известную также как проблема дискретного логарифмирования, и алгоритм, решающий проблему равенства слов в данном классе групп.
Исследование проводится с использованием геометрических методов комбинаторной теории групп (метода диаграмм над группами).
При обмене информацией по открытому каналу используют односторонние функции, прямое вычисление которых должно быть гораздо менее сложным, чем вычисление обратной функции. В данной работе рассмотрена комбинация двух проблем: дискретного логарифмирования и сопряжённости. Это привело к задаче сопряжённого вхождения в циклическую подгруппу. В работе предлагается алгоритм, основанный на этой задаче, который можно брать за основу при исследовании соответствующей односторонней функции на пригодность для построения открытой схемы распределения ключей.
В ходе исследования использовались кольцевые диаграммы сопряжённости слов, и для одного специального класса таких диаграмм было доказано свойство периодичности по слоям.  Наличие такого свойства очевидным образом приводит к решению проблемы степенной сопряжённости слов в рассматриваемом классе групп. К сожалению, в этой работе не удалось доказать периодичность произвольной кольцевой диаграммы, но для одного класса из двух возможных эта периодичность была доказана.
Рассмотренная в работе процедура построения односторонней функции была изучена с точки зрения возможности вычисления как прямого, так и обратного отображений. Сложность этих вычислений не рассматривалась. Таким образом, остались нерешёнными две следующие задачи: определение качества односторонней функции в рассмотренном протоколе открытого распределения ключей и завершение исследования периодичности кольцевых диаграмм сопряжённости слов, приводящее к положительному решению проблемы степенной сопряжённости слов в рассматриваемом классе групп.

Список литературы

  1. М агнус Д., Каррас А., Солитэр Д. Комбинаторная теория групп. Пер. с англ. М.: Наука, 1974.
  2. Л индон Р., Шупп П. Комбинаторная теория групп. Пер. с англ. М.: Мир, 1980.
  3. О льшанский А.Ю. Геометрия определяющих соотношений в группах. М: Наука, 1989.
  4. Н овиков П.С. Труды Математического ин-та АН СССР. 1955. т. 44. с. 1 – 444.
  5. Б езверхний Н.В. Разрешимость проблемы вхождения в циклическую подгруппу в группах с условием C (6). // Фундаментальная и прикладная математика. 1999. Т.5.№1. с. 39 – 46.
  6. Б езверхний Н.В. Нормальные формы для элементов бесконечного порядка в группах с условиями C (3)- T (6) // Известия ТулГУ. Естественные науки. 2010. Вып. 1. С. 6 – 25.
  7. Б езверхний Н.В. Проблема сопряжённого вхождения в циклическую подгруппу в группах с условиями C (3)- T (6) // Дискретная математика.2012. т. 24. выпуск 4. с. 27 – 46.
  8. Б езверхний В.Н. О нормализаторах элементов в C ( p )- T ( q )-группах. Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Изд-во Тул. гос. пед. ун-та им. Л.Н.Толстого. 1994. с. 4 – 58.
  9. Б езверхний В.Н., Паршикова Е.В. Решение проблемы вхождения в циклическую подгруппу в группах с условиями C (4)- T (4) // Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: изд-во ТГПУ им. Л.Н.Толстого. 2001. с. 120 – 139.
  10. П аршикова Е.В. Проблема слабой степенной сопряжённости в группах с условием C (4)- T (4) // Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Изд-во Тул. гос. пед. ун-та им. Л.Н.Толстого. 2001. с. 179 – 185.
  11. Б езверхний Н.В. О кручении о и разрешимости проблемы вхождения в циклическую подгруппу в группах с условием C (6)// Деп. ВИНИТИ 1995, 2033-В95.
  12. Б езверхний Н.В., Чернышева О.А. Односторонние функции, основанные на проблеме дискретного логарифмирования в группах с условиями C (3)- T (6)// Наука и образование 2014.
  13. Б езверхний Н.В. Кольцевые диаграммы с периодическими метками и проблема степенной сопряжённости в группах с условиями C (3)- T (6)// Наука и образование 2014.
  14. Б езверхний Н.В. Проблема вхождения в циклическую подгруппу в группах с условиями C (3)- T (6)// Наука и образование 2011.
  15. Г лухов М.М. К анализу некоторых систем открытого распределения ключей, основанных на неабелевых группах // Математические вопросы криптографии. 2010. T .1 №4. С. 5 – 22.
  16. A nshel I., Anshtl M., Goldfeld D. An algebraic method for public key cryptography // Math/ Res/ Lett. 1999. V. 6. P. 287 – 291.
  17. Koo K.H., Lee S.J., Cheon J.H., Han J.W., Kang J., Park C. New publickey criptosistem using braide groups // CRIPTO 2000, Lect. Notes Comput Sci. 2000. V. 1880. P. 166 – 183.
  18. Y amamura A. Public rey cryptosistem using the modular group // PKC, Lect. Notes Comput. Sci. 1998. V. 1431. P. 203 – 216.
  19. Y amamura A. A functional cryptosistem using a group action// ACISP, Lect. Notes Comput. Sci. 1999. V. 1587. P. 314 – 325.
  20. P aeng S.H., Ha K.C., Kim J.H., Chee S., ParkC. New public key criptosistem using finite nonabelian groups // CRIPTO2001, Lect. Notes Comput. Sci. 2001. V. 2139. P. 470 – 485.
  21. P aeng S.H., Kwon D., Ha K., Kim J.H. Improved public key cryptosystem using non abelian groups // eprint.iacr.org/2001/066.
  22. B ogley W.A., Pride S.J. Aspherical relative presentations // Pros. of the Edinburg Math. Soc. 1992. V. 35. P. 1 – 39.
  23. G ersten, Short. Small cancellation theory and automatic groups // 1990. Invent. math. 102. 305 – 334.

Тематические рубрики:
Поделиться:
 
ПОИСК
 
elibrary crossref neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2018 «Математика и Математическое моделирование» Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)