Paper 2011/296

Short Signatures From Weaker Assumptions

Dennis Hofheinz, Tibor Jager, and Eike Kiltz


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.

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


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.