Short Signatures with a Tighter Security Reduction Without Random Oracles
Fuchun Guo, Y. Mu, Willy Susilo · The Computer Journal · 2010
The recent work by Hofheinz and Kiltz (Crypto 2008) has demonstrated that it is feasible to generate a short signature with <320 bits and 80-bit security without the need of random oracles. The authors also showed that the signature length can be reduced to 230 bits if no more than 230 signatures are generated. In this paper, we present three novel short signature schemes with a comparable signature length. Although our schemes can be considered as variants of Hofheinz and Kiltz's schemes, ours can be proved with a much tighter security reduction without random oracles. Our first scheme offers a 270-bit short signature length for 80-bit security without using random oracles and can be tightly reduced to the q-strong Diffie–Hellman problem. Using a stateful signing approach in our second scheme, we show how to further shorten the signature length to 191 bits. Our idea can also be applied to construct short RSA-based signatures with a tight security reduction to the strong RSA problem without random oracles. We note that the 80-bit security defined in all short signature schemes without random oracles is associated with loose reductions or strong assumptions. We compare our schemes with the Boneh–Boyen short signature scheme (Eurocrypt 2004) and the Hofheinz–Kiltz short signature scheme by taking security reductions into account. We show that with the same assumptions, our schemes offer the shortest signatures and achieve the same concrete security.