Cryptology ePrint Archive: Report 2019/233

Unbounded Dynamic Predicate Compositions in Attribute-Based Encryption

Nuttapong Attrapadung

Abstract: We present several transformations that combine a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive composed predicates. Previous proposals for predicate compositions of this kind, the most recent one being that of Ambrona at Crypto'17, can be considered static (or partially dynamic), meaning that the policy (or its structure) that specifies a composition must be fixed at the setup. Contrastingly, our transformations are dynamic and unbounded: they allow a user to specify an arbitrary and unbounded-size composition policy right into his/her own key or ciphertext. We propose transformations for three classes of composition policies, namely, the classes of any monotone span programs, any branching programs, and any deterministic finite automata. These generalized policies are defined over arbitrary predicates, hence admitting modular compositions. One application from modularity is a new kind of ABE for which policies can be ``nested'' over ciphertext and key policies. As another application, we achieve the first fully secure completely unbounded key-policy ABE for non-monotone span programs, in a modular and clean manner, under the q-ratio assumption. Our transformations work inside a generic framework for ABE called symbolic pair encoding, proposed by Agrawal and Chase at Eurocrypt'17. At the core of our transformations, we observe and exploit an unbounded nature of the symbolic property so as to achieve unbounded-size policy compositions.

Category / Keywords: attribute-based encryption, predicate encryption, nested policy, automata, pair encoding, symbolic security, dynamic composition, full security, non-monotone span programs

Original Publication (with major differences): IACR-EUROCRYPT-2019

Date: received 27 Feb 2019, last revised 27 Feb 2019

Contact author: n attrapadung at aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20190228:190538 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]