Cryptology ePrint Archive: Report 2017/061

Short Digital Signatures and ID-KEMs via Truncation Collision Resistance

Tibor Jager and Rafael Kurek

Abstract: 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.

Category / Keywords: Identity-based encryption, digital signatures, random oracle model, extremely lossy functions, provable security

Date: received 27 Jan 2017, last revised 3 Sep 2018

Contact author: tibor jager at upb de

Available format(s): PDF | BibTeX Citation

Version: 20180903:103008 (All versions of this report)

Short URL: ia.cr/2017/061