Paper 2017/029

Bounded-Collusion Attribute-Based Encryption from Minimal Assumptions

Gene Itkis, Emily Shen, Mayank Varia, David Wilson, and Arkady Yerukhimovich


Attribute-based encryption (ABE) enables encryption of messages under access policies so that only users with attributes satisfying the policy can decrypt the ciphertext. In standard ABE, an arbitrary number of colluding users, each without an authorized attribute set, cannot decrypt the ciphertext. However, all existing ABE schemes rely on concrete cryptographic assumptions such as the hardness of certain problems over bilinear maps or integer lattices. Furthermore, it is known that ABE cannot be constructed from generic assumptions such as public-key encryption using black-box techniques. In this work, we revisit the problem of constructing ABE that tolerates collusions of arbitrary but a priori bounded size. We present an ABE scheme secure against bounded collusions that requires only semantically secure public-key encryption. Our scheme achieves significant improvement in the size of the public parameters, secret keys, and ciphertexts over the previous construction of bounded-collusion ABE from minimal assumptions by Gorbunov et al. (CRYPTO 2012). We also obtain bounded-collusion symmetric-key ABE (which requires the secret key for encryption) by replacing the public-key encryption with symmetric-key encryption, which can be built from the minimal assumption of one-way functions.

Note: Removed second scheme due to an error in the analysis

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2017
attribute-based encryptionpublic-key encryptionbounded collusionsecret sharing
Contact author(s)
david wilson @ ll mit edu
2019-05-30: revised
2017-01-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gene Itkis and Emily Shen and Mayank Varia and David Wilson and Arkady Yerukhimovich},
      title = {Bounded-Collusion Attribute-Based Encryption from Minimal Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/029},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.