Document Type

Journal Article

Publication Details

Guo, F., Mu, Y. & Susilo, W. (2011). Short signatures with a tighter security reduction without random oracles. The Computer Journal, 54 (4), 513-524.


The recent work by Hofheinz and Kiltz (Crypto 2008) has demonstrated that it is feasible to generatea short signature with <320 bits and 80-bit security without the need of random oracles. The authorsalso showed that the signature length can be reduced to 230 bits if no more than 230 signatures aregenerated. In this paper, we present three novel short signature schemes with a comparable signaturelength. Although our schemes can be considered as variants of Hofheinz and Kiltz’s schemes, ourscan be proved with a much tighter security reduction without random oracles. Our first scheme offersa 270-bit short signature length for 80-bit security without using random oracles and can be tightlyreduced to the q-strong Diffie–Hellman problem. Using a stateful signing approach in our secondscheme, we show how to further shorten the signature length to 191 bits. Our idea can also be appliedto construct short RSA-based signatures with a tight security reduction to the strong RSA problemwithout random oracles. We note that the 80-bit security defined in all short signature schemeswithout random oracles is associated with loose reductions or strong assumptions.We compare ourschemes with the Boneh–Boyen short signature scheme (Eurocrypt 2004) and the Hofheinz–Kiltzshort signature scheme by taking security reductions into account. We show that with the sameassumptions, our schemes offer the shortest signatures and achieve the same concrete security.