Журналов:     Статей:        

Математика и математическое моделирование. 2015; : 43-63

Односторонние функции и композиция проблем сопряжённости и дискретного логарифмирования в 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.

Mathematics and Mathematical Modeling. 2015; : 43-63

One-Way Functions and Composition of Conjugacy and Discrete Logarithm Problems in the Small Cancellation Groups

Bezverkhniy N. V.

Abstract

The paper considers the possibility for building a one-way function in the small cancellation group. Thus, it uses the algorithm to solve the problem for a cyclic subgroup, also known as a discrete logarithm problem, and the algorithm to solve the word problem in this class of groups.

Research is conducted using geometric methods of combinatorial group theory (the method of diagrams in groups).

In public channel exchange of information are used one-way functions, direct calculation of which should be much less complicated than the calculation of the inverse function. The paper considers the combination of two problems: discrete logarithms and conjugacy. This leads to the problem of conjugate membership for a cyclic subgroup. The work proposes an algorithm based on this problem, which can be used as a basis in investigation of the appropriate one-way function for its fitness to build a public key distribution scheme.

The study used doughnut charts of word conjugacy, and for one special class of such charts has been proven a property of the layer-based periodicity. The presence of such properties is obviously leads to a solution of the power conjugacy of words in the considered class of groups. Unfortunately, this study failed to show any periodicity of a doughnut chart, but for one of two possible classes this periodicity has been proven.

The building process of one-way function considered in the paper was studied in terms of possibility to calculate both direct and inverse mappings. The computational complexity was not considered. Thus, the following two tasks were yet unresolved: determining the quality of one-way function in the above protocol of the public key distribution and completing the study of the periodicity of doughnut charts of word conjugacy, leading to a positive solution of the power conjugacy of words in the class groups under consideration.

DOI: 10.7463/mathm.0515.0820675

References

1. Magnus D., Karras A., Soliter D. Kombinatornaya teoriya grupp. Per. s angl. M.: Nauka, 1974.

2. Lindon R., Shupp P. Kombinatornaya teoriya grupp. Per. s angl. M.: Mir, 1980.

3. Ol'shanskii A.Yu. Geometriya opredelyayushchikh sootnoshenii v gruppakh. M: Nauka, 1989.

4. Novikov P.S. Trudy Matematicheskogo in-ta AN SSSR. 1955. t. 44. s. 1 - 444.

5. Bezverkhnii N.V. Razreshimost' problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviem C(6). // Fundamental'naya i prikladnaya matematika. 1999. T.5. №1. s. 39 - 46.

6. Bezverkhnii N.V. Normal'nye formy dlya elementov beskonechnogo poryadka v gruppakh s usloviyami C(3)-T(6) // Izvestiya TulGU. Estestvennye nauki. 2010. Vyp. 1. S. 6 - 25.

7. Bezverkhnii N.V. Problema sopryazhennogo vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviyami C(3)-T(6) // Diskretnaya matematika. 2012. t. 24. vypusk 4. s. 27 - 46.

8. Bezverkhnii V.N. O normalizatorakh elementov v C(p)-T(q)-gruppakh. Algoritmicheskie problemy teorii grupp i polugrupp. Mezhvuzovskii sbornik nauchnykh trudov. Izd-vo Tul. gos. ped. un-ta im. L.N.Tolstogo. 1994. s. 4 - 58.

9. Bezverkhnii V.N., Parshikova E.V. Reshenie problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviyami C(4)-T(4) // Algoritmicheskie problemy teorii grupp i polugrupp. Mezhvuzovskii sbornik nauchnykh trudov. Tula: izd-vo TGPU im. L.N.Tolstogo. 2001. s. 120 - 139.

10. Parshikova E.V. Problema slaboi stepennoi sopryazhennosti v gruppakh s usloviem C(4)-T(4) // Algoritmicheskie problemy teorii grupp i polugrupp. Mezhvuzovskii sbornik nauchnykh trudov. Izd-vo Tul. gos. ped. un-ta im. L.N.Tolstogo. 2001. s. 179 - 185.

11. Bezverkhnii N.V. O kruchenii o i razreshimosti problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviem C(6)// Dep. VINITI 1995, 2033-V95.

12. Bezverkhnii N.V., Chernysheva O.A. Odnostoronnie funktsii, osnovannye na probleme diskretnogo logarifmirovaniya v gruppakh s usloviyami C(3)-T(6)// Nauka i obrazovanie 2014.

13. Bezverkhnii N.V. Kol'tsevye diagrammy s periodicheskimi metkami i problema stepennoi sopryazhennosti v gruppakh s usloviyami C(3)-T(6)// Nauka i obrazovanie 2014.

14. Bezverkhnii N.V. Problema vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviyami C(3)-T(6)// Nauka i obrazovanie 2011.

15. Glukhov M.M. K analizu nekotorykh sistem otkrytogo raspredeleniya klyuchei, osnovannykh na neabelevykh gruppakh // Matematicheskie voprosy kriptografii. 2010. T.1 №4. S. 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.