Skip to main content
Improving security of q-SDH based digital signatures
Faculty of Informatics - Papers (Archive)
  • Fuchun Guo, University of Wollongong
  • Yi Mu, University of Wollongong
  • Willy Susilo, University of Wollongong
Publication Date
Publication Details

Guo, F., Mu, Y. & Susilo, W. (2011). Improving security of q-SDH based digital signatures. Journal of Systems and Software, 84 (10), 1783-1790.


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.

Grant Number
Citation Information
Fuchun Guo, Yi Mu and Willy Susilo. "Improving security of q-SDH based digital signatures" (2011) p. 1783 - 1790
Available at: