A Novel Public Key Cryptosystem and Digital Signatures

Abstract

In this article, we develop a new algebraic public key cryptosystem, which is based on generally non-commutative ring. Firstly, we define the polynomials over the non-commutative rings and then take it as underlying work structure. The hard problem of the scheme is the mixture of matrix discrete log problem under modular classes and polynomial symmetric decomposition problem. Using matrices of higher order and large modular classes resist the brute force and other well-known attacks exists in the literature. We also discuss the computational complexity of proposed scheme. On the other hand, we propose a signature scheme over a non-commutative division semiring. The key idea behind the signature scheme is that, for a given non-commutative division semiring, we build a polynomial and then implement digital signatures on multiplicative structure of semiring.