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

Abstract

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.