Preview

Математика и математическое моделирование

Расширенный поиск

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

Полный текст:

Аннотация

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

DOI: 10.7463/mathm.0515.0820675

Об авторе

Н. В. Безверхний
МГТУ им. Н.Э. Баумана
Россия


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

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. Anshel 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. Yamamura A. Public rey cryptosistem using the modular group // PKC, Lect. Notes Comput. Sci. 1998. V. 1431. P. 203 - 216.

19. Yamamura A. A functional cryptosistem using a group action// ACISP, Lect. Notes Comput. Sci. 1999. V. 1587. P. 314 - 325.

20. Paeng 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. Paeng S.H., Kwon D., Ha K., Kim J.H. Improved public key cryptosystem using non abelian groups // eprint.iacr.org/2001/066.

22. Bogley W.A., Pride S.J. Aspherical relative presentations // Pros. of the Edinburg Math. Soc. 1992. V. 35. P. 1 - 39.

23. Gersten, Short. Small cancellation theory and automatic groups // 1990. Invent. math. 102. 305 - 334.


Для цитирования:


Безверхний Н.В. Односторонние функции и композиция проблем сопряжённости и дискретного логарифмирования в C(3)-T(6)-группах. Математика и математическое моделирование. 2015;(5):43-63.

For citation:


Bezverkhniy N.V. One-Way Functions and Composition of Conjugacy and Discrete Logarithm Problems in the Small Cancellation Groups. Mathematics and Mathematical Modeling. 2015;(5):43-63. (In Russ.)

Просмотров: 194


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)