### Realizing Hash-and-Sign Signatures under Standard Assumptions

Susan Hohenberger and Brent Waters

##### Abstract

Currently, there are relatively few instances of hash-and-sign'' signatures in the standard model. Moreover, most current instances rely on strong and less studied assumptions such as the Strong RSA and q-Strong Diffie-Hellman assumptions. 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.

Note: Using safe primes in the presentation.

##### Metadata
Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of paper that appeared in Eurocrypt 2009.
Keywords
signatures
Contact author(s)
susan @ cs jhu edu
History
2009-06-14: last of 4 revisions
2009-01-14: received
See all versions
Short URL
https://ia.cr/2009/028
License

CC BY

BibTeX

@misc{cryptoeprint:2009/028,
author = {Susan Hohenberger and Brent Waters},
title = {Realizing Hash-and-Sign Signatures under Standard Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2009/028},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/028}},
url = {https://eprint.iacr.org/2009/028}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.