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

**Category / Keywords: **cryptographic protocols / Predicate Encryption, Adaptive Security, Standard Model, Static Assumption, Deja Q, Bilinear Pairing

**Original Publication**** (with major differences): **CT-RSA 2019

**Date: **received 7 Dec 2018, last revised 21 Nov 2019

**Contact author: **sayantanm at iisc ac in

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20191121:221609 (All versions of this report)

**Short URL: **ia.cr/2018/1190

[ Cryptology ePrint archive ]