Design Of Public-Key Cryptosystems Based On Matrices Discrete Logarithm Problem

Abstract

The Matrices group is a group defined over finite field that forms an Abelian group, which is a suitable choice for constructing a good problem similar to Discrete Logarithm Problem (DLP) and Elliptic Curves Discrete Logarithm Problem (ECDLP). This idea is encouraged to define a new one-way trap-door function over finite matrices group. This leads to create cipher systems based on the difficulty of solution of the presented one-way trap-door function. That is appearing a clear change in the cryptography, and opens new windows for treatment with special groups and new operations.This paper proposes one-way trap-door function defined over Matrices group, We call it Matrices Discrete Logarithm Problem (MDLP) and introduces the first proposed cryptosystems that employ the finite matrices group in the public key cryptosystems. The complication associated with the desined cipher system comes from the wide variety of possible group structures of the matrix element in the Matrices group, and from the fact that matrices multiplication is complicated. The security of the system depends on how difficult it is to determine the integer d, given the square matrix B and the square matrix A where B= Ad mod q, A and B are square matrices defined over finite field Fq, this is referred to as the MDLP. In addition, that appears to offer equal security for a far smallest bit size, that for two reasons. The first reason is that the operations are applied -instead of multiplication of two integer numbers- as a matrix-by-matrix multiplication, in the other hand, the complexity and intractability are increase as much as the size of base matrix is increased. The second reason is that the order of the Matrices group |M(Fq)| with n×n base matrix appears at most qn-1 or its factors, that mean the calculation is applied with q-bit size, needs qn-1 matrix-by-matrix multiplications to solve the MDLP.