Paper 2018/1190

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

Sanjit Chatterjee and Sayantan Mukherjee


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).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CT-RSA 2019
Predicate EncryptionAdaptive SecurityStandard ModelStatic AssumptionDeja QBilinear Pairing
Contact author(s)
sayantanm @ iisc ac in
2019-11-21: revised
2018-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjit Chatterjee and Sayantan Mukherjee},
      title = {Large Universe Subset Predicate Encryption Based on Static Assumption (without Random Oracle)},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1190},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.