Paper 2017/061

Short Digital Signatures and ID-KEMs via Truncation Collision Resistance

Tibor Jager and Rafael Kurek


Truncation collision resistance is a simple non-interactive complexity assumption that seems very plausible for standard cryptographic hash functions like SHA-3. We describe how this assumption can be leveraged to obtain standard-model constructions of public-key cryptosystems that previously seemed to require a programmable random oracle. This includes the first constructions of identity-based key encapsulation mechanisms (ID-KEMs) and digital signatures over bilinear groups with full adaptive security and without random oracles, where a ciphertext or signature consists of only a single element of a prime-order group. We also describe a generic construction of ID-KEMs with full adaptive security from a scheme with very weak security ("selective and non-adaptive chosen-ID security"), and a similar generic construction for digital signatures.

Available format(s)
Publication info
Preprint. MINOR revision.
Identity-based encryptiondigital signaturesrandom oracle modelextremely lossy functionsprovable security
Contact author(s)
tibor jager @ upb de
2018-09-03: last of 5 revisions
2017-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tibor Jager and Rafael Kurek},
      title = {Short Digital Signatures and ID-KEMs via Truncation Collision Resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2017/061},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.