Bounded-Collusion Identity-Based Encryption from Semantically-Secure Public-Key Encryption: Generic Constructions with Short Ciphertexts

Stefano Tessaro; David A.  Wilson

Paper 2014/061

Bounded-Collusion Identity-Based Encryption from Semantically-Secure Public-Key Encryption: Generic Constructions with Short Ciphertexts

Stefano Tessaro and David A. Wilson

Abstract

Identity-based encryption (IBE) is a special case of public-key encryption where user identities replace public keys. Every user is given a corresponding secret key for decryp- tion, and encryptions for his or her identity must remain confidential even to attackers who learn the secret keys associated with other identities. Several IBE constructions are known to date, but their security relies on specific assumptions, such as quadratic residuosity, as well as different pairing-based and lattice-based assumptions. To circumvent the lack of generic constructions, Dodis et al. (EUROCRYPT ’02) introduced the notion of bounded-collusion IBE (BC-IBE), where attackers only learn secret keys of an a-priori bounded number t of identities. They provided a generic BC-IBE construction from any semantically-secure encryption scheme which, however, suffers from a ω(t) blow-up in ciphertext size. Goldwasser et al. (TCC 2012) recently presented a generic construction with no ciphertext-length blow-up. Their construction requires an underlying public-key scheme with a key homomorphism, as well as a hash-proof-style security definition that is strictly stronger than semantic security. This latter requirement in particular reduces the applicability of their construction to existing schemes. In this paper, we present the first generic constructions of BC-IBE from semantically-secure encryption schemes with no ciphertext-length blow-up. Our constructions require different degrees of key-homomorphism and malleability properties that are usually easy to verify. We provide concrete instantiations based on the DDH, QR, NTRU, and LWE assumptions. For all of these assumptions, our schemes present the smallest BC-IBE ciphertext size known to date. Our NTRU-based construction is particularly interesting, due to the lack of NTRU- based IBE constructions as well as the fact that it supports fully-homomorphic evaluation. Our results also yield new constructions of bounded CCA-secure cryptosystems.

Note: An extended abstract of this paper appears in the proceedings of PKC 2014. This is the full version.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in PKC 2014
Keywords: Identity-based encryption Bounded-CCA security
Contact author(s): tessaro @ cs ucsb edu
History: 2014-01-28: received
Short URL: https://ia.cr/2014/061
License: CC BY

BibTeX

@misc{cryptoeprint:2014/061,
      author = {Stefano Tessaro and David A.  Wilson},
      title = {Bounded-Collusion Identity-Based Encryption from Semantically-Secure Public-Key Encryption: Generic Constructions with Short Ciphertexts},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/061},
      year = {2014},
      url = {https://eprint.iacr.org/2014/061}
}