Paper 2018/1190

Large Universe Subset Predicate Encryption Based on Static Assumption (without Random Oracle)

Sanjit Chatterjee and Sayantan Mukherjee

Abstract

In a recent work, Katz et al. (CANS'17) generalized the notion of Broadcast Encryption to define Subset Predicate Encryption (SPE) that emulates \emph{subset containment} predicate in the encrypted domain. They proposed two selective secure constructions of SPE in the small universe settings. Their first construction is based on $q$-type assumption while the second one is based on DBDH. % which can be converted to large universe using random oracle. Both achieve constant size secret key while the ciphertext size depends on the size of the privileged set. They also showed some black-box transformation of SPE to well-known primitives like WIBE and ABE to establish the richness of the SPE structure. This work investigates the question of large universe realization of SPE scheme based on static assumption without random oracle. We propose two constructions both of which achieve constant size secret key. First construction $\mathsf{SPE}_1$, instantiated in composite order bilinear groups, achieves constant size ciphertext and is proven secure in a restricted version of selective security model under the subgroup decision assumption (SDP). Our main construction $\mathsf{SPE}_2$ is adaptive secure in the prime order bilinear group under the symmetric external Diffie-Hellman assumption (SXDH). Thus $\mathsf{SPE}_2$ is the first large universe instantiation of SPE to achieve adaptive security without random oracle. Both our constructions have efficient decryption function suggesting their practical applicability. Thus the primitives like WIBE and ABE resulting through black-box transformation of our constructions become more practical.

Note: The security argument of the second SPE construction in our previous version had a small error which is addressed in this version. See Section 5.1 and the proof of Theorem 2 (Lemma 5 and Lemma 7).