To design our signature, we employ the known generic construction of fully-secure signatures from weakly-secure signatures and a chameleon hash. We then introduce a new proof technique for reasoning about weakly-secure signatures. This technique enables the simulator to predict a prefix of the message on which the adversary will forge and to use knowledge of this prefix to embed the challenge. This technique has wider applications beyond RSA.
We also use it to provide an entirely new analysis of the security of the Waters signatures: the only short, stateless signatures known to be secure under the Computational Diffie-Hellman assumption in the standard model.
Category / Keywords: public-key cryptography / Publication Info: This is the full version of the paper in CRYPTO 2009. Date: received 14 Jun 2009, last revised 11 Mar 2010 Contact author: bwaters at cs utexas edu Available format(s): PDF | BibTeX Citation Note: Added reference to more efficient chameleon hash functions. Version: 20100311:151656 (All versions of this report) Short URL: ia.cr/2009/283