It is a challenging task to construct a signature that it can be tightly reduced to a weak security assumption in the standard model. In this paper, we introduce a simple chameleon-hash-based transformation and show that it can tighten a security reduction of a signature scheme that suffers from a loose security reduction. Taking the Waters' signature from Eurocrypt 2005 as an example, we demonstrate an improvement of the security reduction that the probability of success in the security reduction can be made as a constant and independent of the signature queries from an adversary. Our reduction methodology has never been considered in the literature and is applicable to many signature schemes such as identity-based signature schemes, online/offline signatures, and signatures with strong unforeability. © Springer-Verlag 2009.