One-way functions based on the discrete logarithm problem in the groups meeting conditions C(3)-T (6)
| Autor: | Olga Chernisheva, Nikolai Bezverhnii |
|---|---|
| Jazyk: | ruština |
| Rok vydání: | 2014 |
| Předmět: |
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 |
| Zdroj: | Nauka i Obrazovanie, Vol 0, Iss 10, Pp 70-101 (2014) |
| ISSN: | 1994-0408 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|