In this paper, we present a new approach for realizing hash-and-sign signatures in the standard model. In our approach, a signer associates each signature with an index i that represents how many signatures that signer has issued up to that point. Then, to make use of this association, we create simple and efficient techniques that restrict an adversary which makes q signature requests to forge on an index no greater than 2q. Finally, we develop methods for dealing with this restricted adversary.
Our approach requires that a signer maintains a small amount of state --- a counter of the number of signatures issued. We achieve two new realizations for hash-and-sign signatures respectively based on the RSA assumption and the Computational Diffie-Hellman assumption in bilinear groups.
Category / Keywords: public-key cryptography / signatures Publication Info: Full version of paper that appeared in Eurocrypt 2009. Date: received 12 Jan 2009, last revised 14 Jun 2009 Contact author: susan at cs jhu edu Available format(s): PDF | BibTeX Citation Note: Using safe primes in the presentation. Version: 20090614:184853 (All versions of this report) Discussion forum: Show discussion | Start new discussion