Cryptology ePrint Archive: Report 2019/1479

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

Jongkil Kim and Willy Susilo and Fuchun Guo and 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.

Category / Keywords: public-key cryptography / pair encoding, non-monotonic access structure, attribute-based encryption, prime order groups, dual system encryption

Original Publication (with major differences): ACNS 2019
DOI:
10.1007/978-3-030-21568-2

Date: received 22 Dec 2019

Contact author: jongkil at uow edu au

Available format(s): PDF | BibTeX Citation

Version: 20191223:152942 (All versions of this report)

Short URL: ia.cr/2019/1479


[ Cryptology ePrint archive ]