Digital Signature Schemes from Two Hard Problems

In this paper, we propose two new signature schemes and a novel short signature scheme from two hard problems. The proposed schemes have two prominent advantages. Firstly, they are developed from some signature schemes where the security and efficiency have been proven. Therefore, they inherit these properties from the previous schemes. Secondly, the security of the proposed schemes is based on two hard problems. Therefore, they are still safe even when cryptanalysis has an effective algorithm to solve one of these problems, but not both. Moreover, we also propose a method for reducing signatures and this is the first attempt to reduce signatures based on two hard problems. Therefore, our proposed schemes are suitable for the applications requiring long-term security in resource limited systems.