101. One-way functions based on the discrete logarithm problem in the groups meeting conditions C(3)-T (6)
- Author
-
Olga Chernisheva and Nikolai Bezverhnii
- Subjects
Discrete mathematics ,lcsh:Computer engineering. Computer hardware ,diagrams in groups ,lcsh:TK7885-7895 ,General Medicine ,One-way function ,Algebra ,membership problem for cyclic subgroups ,small cancellation conditions ,Discrete logarithm ,one-way functions ,lcsh:Mechanics of engineering. Applied mechanics ,lcsh:TA349-359 ,Mathematics - Abstract
In this work we are consider a possibility to create schemes of open key distribution in the groups meeting conditions C(3)-T(6). Our constructions use the following algorithms.1. The algorithm that solves the membership problem for cyclic subgroups, also known as the discrete logarithm problem.2. The algorithm that solves the word problem in this class of groups.Our approach is based on the geometric methods of combinatorial group theory (the method of diagrams in groups).In a cryptographic scheme based on the open key distribution one-way functions are used, i.e. functions direct calculation of which must be much easier than that of the inverse one. Our task was to construct a one-way function using groups with small cancelation conditions C(3)-T(6) and to compare the calculation complexity of this function with the calculation complexity of its inverse.P.W. Shor has shown in the paper that there exists a polynomial algorithm that can be implemented in a quantum computer to solve the discrete logarithm problem in the groups of units of finite fields and the rings of congruences mod n. This stimulated a series of investigations trying to find alternative complicated mathematical problems that can be used for construction of new asymmetric cryptosystems. For example, open key distribution systems based on the conjugacy problem in matrix groups and the braid groups were proposed.In the other papers the constructions used the discrete logarithm problem in the groups of inner automorphisms of semi-direct products of SL(2,Z) and Zp and GL(2,Zp) and Zp. groups. The paper of E. Sakalauskas, P. Tvarijonas, A. Raulinaitis proposed a scheme that uses a composition of two problems of group theory, namely the conjugacy problem and the discrete logarithm problem.Our results show that the scheme that we propose is of polynomial complexity. Therefore its security is not sufficient for further applications in communications. However the security can be improved through combining the word problem with other algebraic problems such as the problem of the membership in the cyclic subgroups and the conjugacy problem.
- Published
- 2014