An MDP Public-Key Digital Signature Scheme

A new public-key digital signature scheme is developed in this paper by exploring the hard matrix diagonalization problem (MDP) over Z\-n, the ring of integers with modulo-n addition and multiplication, where n is an RSA modulus. In the proposed system, a digital signature is obtained by embedding simple functions of a message into two 2×2 matrices as their eigenvalues, while the eigenvectors of the matrices are computed from the signer's private key. Security of the new scheme depends on the problem of solving three simultaneous quadratic equations with total five variables. It remains to be proved that the new crypto problem is as hard as solving Rabin equations, but it is apparently harder than solving pure bi-variate quadratic equations, i.e., Ong-Schnorr-Shamir equations, and it is not vulnerable by Pollard-Schnorr attack. The most important feature of the new scheme is its high efficiency. Since no high crder exponentiation is involved, it takes only a dozen of multiplications to sign a message, among which only 4 multiplications should be performed online, the rest can be pre-computed, while more than 1000 modulo-n multiplications are required to obtain an RSA signature. new scheme can also be used for identity-based digital signature.