GENERALIZATION OF NON-COMMUTATIVE KEY EXCHANGE PROTOCOL

Abstract

A symmetric cryptosystem requires a secret key agreed by both parties. The Diffie-Hellman protocol was originally proposed for its exchange via an open communication channel. It is based on the computational complexity of the discrete logarithm problem in certain finite groups (the multiplicative group of a finite field, the group of points of an elliptic curve over a finite field). The availability of a powerful quantum computer will allow solving the discrete logarithm problem in these groups. Therefore, the issue of construction of  secret key exchange protocols that will be resistant to attacks using a quantum computer has become urgent.

The paper provides a comparative analysis of known protocols for a secret key exchange via an open communication channel. A generalization of the known protocol using non-commutative matrix multiplication over a prime finite field for the case of an arbitrary finite field is proposed. In this protocol, two high order elements from the general linear group over a finite field should be used, which satisfy an additional condition. It consists in the fact that each of the matrices cannot be reduced to a diagonal form by conjugation transformation. This condition follows from the considerations of avoiding an attack on the protocol. It is shown how to construct such elements.

For the proposed generalization of the protocol, the sizes of public and private keys, secret key, the size of the finite field, which ensure the appropriate level of security, are calculated. The dimensions of matrices (elements of the general linear group) that we use are also given. The generalization of the protocol to the case of an arbitrary finite field increases the flexibility of choosing protocol parameters to ensure the desired level of security.