A NOVEL DIGITAL SIGNATURE SCHEME BASED ON CUBIC RESIDUE WITH PROVABLE SECURITY

Since a single computationally hard problem today may possibly be solved efficiently in the future, many researchers endeavored in recent years to base their cryptosystern security on solving two or more hard problems simultaneously to enhance the system security. However, it is found that many previously suggested signature schemes with their (1) security based on integer factorization and discrete logarithm problems and with (2) verification equation using exponential quadratic forms were not as secure as claimed and gave no provable security under the random oracle model. We, therefore, use the theory of cubic residues to present a new signature scheme with an exponential cubic verification equation to prevent the attack from Pollard-Schnorr's congruence solutions and give a formal proof of the scheme security by random oracle modeling. We formally prove that, based on solving the discrete logarithm problem with a composite modulus (which has been shown by Bach in 1984 to be exactly as hard as simultaneously solving the integer factorization and the discrete logarithm with a prime modulus), the proposed scheme is resistant against both no-message and adaptively chosen-message attacks.