Paper 2020/231

Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

Junichi Tomida and Nuttapong Attrapadung

Abstract

At Eurocrypt'19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner (including those that resolved some open problems at the time). However, his approach heavily relies on so-called q-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem. In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung. Our framework significantly expands an area of ABEs that are realizable from standard assumptions. This includes the following adaptively secure large-universe ABEs for Boolean formulae under MDDH. -- The first completely unbounded monotone key-policy (KP)/ciphertext-policy (CP) ABE. Previously, such ABE has been only recently proposed, but only for the KP and small-universe flavor (Kowalczyk and Wee, Eurocrypt'19). -- The first completely unbounded non-monotone KP/CP-ABE. Especially, our ABEs support a new type of non-monotonicity that subsumes previous two types of non-monotonicity, namely, by Ostrovsky et al. (CCS'07) and by Okamoto and Takashima (CRYPTO'10). -- The first non-monotone KP and CP-ABE with constant-size ciphertexts and secret keys, respectively. -- The first monotone KP and CP-ABE with constant-size secret keys and ciphertexts, respectively.