Improving security of q-SDH based digital signatures

In Eurocrypt 2009, Hohenberger and Waters pointed out that a complexity assumption, which restricts the adversary to a single correct response, seems inherently more reliable than their flexible counterparts. The q-SDH assumption is less reliable than standard assumptions because its solution allows exponential answers. On the other hand, the q-SDH assumption exhibits the nice feature of tight reduction in security proof. In this paper, we propose a variant of the q-SDH assumption, so that its correct answers are polynomial and no longer exponentially many. The new assumption is much more reliable and weaker than the original q-SDH assumption. We propose a new digital signature scheme that can tightly reduce the security to the proposed assumption in the standard model. We show that our signature scheme shares most properties with the q-SDH based signature schemes. We also propose a new approach to construct fully secure signatures from weakly secure signature against known-message attacks. Although our security transformation is conditional and not completely generic, it offers another efficient approach to construct fully secure signatures.