Paper 2011/296

Short Signatures From Weaker Assumptions

Dennis Hofheinz, Tibor Jager, and Eike Kiltz

Abstract

We provide constructions of (m,1)-programmable hash functions (PHFs) for m >= 2. Mimicking certain programmability properties of random oracles, PHFs can, e.g., be plugged into the generic constructions by Hofheinz and Kiltz (J. Cryptol. 2011) to yield digital signature schemes from the strong RSA and strong q-Diffie-Hellman assumptions. As another application of PHFs, we propose new and efficient constructions of digital signature schemes from weaker assumptions, i.e., from the (standard, non-strong) RSA and the (standard, non-strong) q-Diffie-Hellman assumptions. The resulting signature schemes offer interesting trade-offs between efficiency/signature length and the size of the public-keys. For example, our q-Diffie-Hellman signatures can be as short as 200 bits; the signing algorithm of our Strong RSA signature scheme can be as efficient as the one in RSA full domain hash; compared to previous constructions, our RSA signatures are shorter (by a factor of roughly 2) and we obtain a considerable efficiency improvement (by an even larger factor). All our constructions are in the standard model, i.e., without random oracles.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Preliminary version appears in Proceedings of ASIACRYPT 2011. This is the full version.
Keywords
digital signaturesRSA assumptionq-DH assumptionprogrammable hash functions
Contact author(s)
eike kiltz @ rub de
History
2011-10-04: revised
2011-06-03: received
See all versions
Short URL
https://ia.cr/2011/296
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/296,
      author = {Dennis Hofheinz and Tibor Jager and Eike Kiltz},
      title = {Short Signatures From Weaker Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/296},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/296}},
      url = {https://eprint.iacr.org/2011/296}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.