International Association for Cryptologic Research

International Association
for Cryptologic Research


Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

Nuttapong Attrapadung
Junichi Tomida
DOI: 10.1007/978-3-030-64840-4_14
Search ePrint
Search Google
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. As for applications, we obtain various ABEs that are the first such instantiations of their kinds from standard assumptions. These include the following adaptively secure \emph{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 \emph{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. At the core of our framework lies a new \emph{partially symmetric} design of the core 1-key 1-ciphertext oracle component called Key Encoding Indistinguishability, which exploits the symmetry so as to obtain compositions.
Video from ASIACRYPT 2020
  title={Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Nuttapong Attrapadung and Junichi Tomida},