Abstract: Provable security has become one basic requirement for constructing and analyzing cryptographic schemes. This paper studies the classical issue in the field of provable security, namely how to construct provably secure digital signature schemes with tight security reduction from certain basic mathematical hard problems in the random oracle model. This paper first proposes a new cryptographic primitive called a strong chameleon Hash function. Based on a strong chameleon Hash function, we present a generic framework and its variant respectively for constructing a stateful and stateless digital signature scheme with tight security. We prove that these generic digital signature schemes are both secure under the assumption that the underlying chameleon Hash function is collision resistant in the random oracle model. By applying these generic construction methods to some concrete chameleon Hash functions under common mathematical assumptions such as RSA, CDH and IF (integer factorization), the corresponding digital signature schemes with tight security can be modularly obtained. The two existing classic paradigms to generically construct tightly secure signature schemes, i.e. Fiat-Shamir signatures and Full-Domain-Hash signatures, can be roughly unified by our generic frameworks. Furthermore, under our generic frameworks, a tightly secure signature scheme following the Fiat-Shamir methodology can be seen as the optimized variant of the corresponding tightly secure signature scheme following the Full-Domain-Hash framework.

Key words: digital signature, provable security, tight security, random oracle model, chameleon Hash function, full domain Hash signature