Paper 2019/1479

A New Encoding Framework for Predicate Encryption with Non-Linear Structures in Prime Order Groups

Jongkil Kim, Willy Susilo, Fuchun Guo, Joonsang Baek, and Nan Li


We present an advanced encoding framework for predicate encryption (PE) in prime order groups. Our framework captures a wider range of adaptively secure PE schemes such as non-monotonic attribute-based encryption by allowing PE schemes to have more flexible structures. Prior to our work, frameworks featuring adaptively secure PE schemes in prime order groups require strong structural restrictions on the schemes. In those frameworks, exponents of public keys and master secret keys of PE schemes, which are also referred to as common variables, must be linear. In our work, we introduce a modular framework which includes non-linear common variables in PE schemes. First, we formalize non-linear structures which can appear in PE by improving Attrapadung's pair encoding framework (Eurocrypt'14). Then, we provide a generic compiler that features encodings under our framework to PE schemes in prime order groups. Particularly, the security of our compiler is proved by introducing a new technique which decomposes common variables into two types and makes one of them be shared between semi-functional and normal spaces on processes of the dual system encryption to mitigate the linear restriction. As instances of our new framework, we introduce new attribute-based encryption schemes supporting non-monotonic access structures, namely non-monotonic ABE, in prime order groups. We introduce adaptively secure non-monotonic ABE schemes having either short ciphertexts (if KP-ABE) or short keys (if CP-ABE) for the first time. Additionally, we introduce the first non-monotonic ABE schemes supporting both adaptive security and multi-use of attributes property in prime order groups.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision.ACNS 2019
pair encodingnon-monotonic access structureattribute-based encryptionprime order groupsdual system encryption
Contact author(s)
jongkil @ uow edu au
2019-12-23: received
Short URL
Creative Commons Attribution


      author = {Jongkil Kim and Willy Susilo and Fuchun Guo and Joonsang Baek and Nan Li},
      title = {A New Encoding Framework for Predicate Encryption with Non-Linear Structures in Prime Order Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1479},
      year = {2019},
      doi = {10.1007/978-3-030-21568-2},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.