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. (C) 2011 Elsevier Inc. All rights reserved.
digital signatures q-sdh assumption security proof