Cryptology ePrint Archive: Report 2017/029

Bounded-Collusion Attribute-Based Encryption from Minimal Assumptions

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

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

Category / Keywords: attribute-based encryption, public-key encryption, bounded collusion, secret sharing

Original Publication (with minor differences): IACR-PKC-2017

Date: received 10 Jan 2017, last revised 30 May 2019

Contact author: david wilson at ll mit edu

Available format(s): PDF | BibTeX Citation

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

Version: 20190530:170107 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]