Digital signature is one of the most important cryptographic primitives. We proposed a new digital signature scheme based on Catalano’s trapdoor. Since Catalano’s trapdoor is more efficient than existing trapdoors in number theory, our scheme need not modular exponentiation but several modular multiplications in the signing algorithm. We also proved our scheme is provably secure against adap-tively chosen message attack by using the Forking lemma. We propose a new digital signature scheme based on Catalano’s trapdoor. Since Catalano’s trapdoor is more efficient than existing trapdoors in number theory, our scheme requires not modular exponentiation but several modular multiplications in the signing algorithm We also characterized our scheme is provably secure against adap-tively chosen message attack by using the Forking lemma.