Key Distribution System Based on Exponential Representations of Linear Group $GL_n(F_p)$

The first key distribution system was suggested by Diffie and Hellman [IEEE Trans. Inf. Theory, 22, 472–492 (1976)] (see also K. S. McCurley [Proc. Symp. Appl. Math, 42, 49–74 (1989)]). In Sidelnikov et al., [Doklady RAN, 332, No. 5, 566–567 (1993)] (see also Sec. 1 of the present paper) a new construction technique was proposed for a key distribution by means of a noncommutative group $G$. In this paper we study a particular case, where ideas of Diffie and Hellman and Sidelnikov et al. are united. Namely, we consider systems based on the group $GL_n(\mathbf F_p)$ represented by means of an auxiliary cyclic group $U$ of order $p$. One can take, for instance, a group of $\mathbf F_q$-points of an elliptic curve for $U$.
We treat in detail the case where $U=(\eta)$ is the subgroup of order p in the multiplicative group of an auxiliary field $\mathbf F_q$, $p|q-1$, and $G$ is the group of affine transformations of the field $\mathbf F_q$, $G< GL_2(\mathbf F_p)$. In this case the problem of determination of the common key $u_{XY}$ for users $X$ and $Y$ is equivalent from the computational point of view to the following one: evaluate the element $\eta^{xy/z}$ as soon $\eta^x$, $\eta^y$, $\eta^z$ are known. The latter problem does not presumably reduce to several Diffie–Hellman problems, i.e., to evaluation of the element $f=\eta^{xy}$ for $\eta^x$, $f=|eta^y$ known.
In the system constructed by using the group $G<GL_2(\mathbf F_p)$, there arise several new parameters not involved in Diffie–Hellman-type systems. In particular, a new private key arises for the whole system such that it is presumably impossible to determine the key $u_{XY}$ without its knowledge.
In Sec. 4 we present a new way of evaluating numeral signatures of messages.