Paper 2018/190

New Lower Bounds on Predicate Entropy for Function Private Public-Key Predicate Encryption

Sikhar Patranabis and Debdeep Mukhopadhyay


We present function private public-key predicate encryption schemes from standard cryptographic assumptions, that achieve new lower bounds on the min-entropy of underlying predicate distributions. Existing function private predicate encryption constructions in the public-key setting can be divided into two broad categories. The first category of constructions are based on standard assumptions, but impose highly stringent requirements on the min-entropy of predicate distributions, thereby limiting their applicability in the context of real-world predicates. For example, the statistically function private constructions of Boneh, Raghunathan and Segev (CRYPTO'13 and ASIACRYPT'13) are inherently restricted to predicate distributions with min-entropy roughly proportional to the security parameter $\lambda$. The second category of constructions mandate more relaxed min-entropy requirements, but are either based on non-standard assumptions (such as indistinguishability obfuscation) or are secure in the generic group model. In this paper, we affirmatively bridge the gap between these categories by presenting new public-key constructions for identity-based encryption, hidden-vector encryption, and subspace-membership encryption~(a generalization of inner-product encryption) that are both data and function private under variants of the well-known DBDH, DLIN and matrix DDH assumptions, while relaxing the min-entropy requirement on the predicate distributions to $\omega(\log\lambda)$. In summary, we establish that the minimum predicate entropy necessary for any meaningful notion of function privacy in the public-key setting, is in fact, sufficient, for a fairly rich class of predicates.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Predicate EncryptionPublic-KeyFunction PrivacyComputational IndistinguishabilityMin-EntropyIdentity-Based EncryptionHidden-Vector EncryptionInner-Product EncryptionSubspace-Membership Encryption
Contact author(s)
sikhar patranabis @ iitkgp ac in
2018-05-08: last of 3 revisions
2018-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sikhar Patranabis and Debdeep Mukhopadhyay},
      title = {New Lower Bounds on Predicate Entropy for Function Private Public-Key Predicate Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/190},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.