**Embed-Augment-Recover: Function Private Predicate Encryption from Minimal Assumptions in the Public-Key Setting**

*Sikhar Patranabis and Debdeep Mukhopadhyay*

**Abstract: **We present a new class of public-key predicate encryption schemes that are provably function private in the standard model under well-known cryptographic assumptions, and assume predicate distributions satisfying realistic min-entropy requirements. More concretely, we present public-key constructions for identity-based encryption (IBE) and inner-product encryption (IPE) that are computationally function private in the standard model under a family of weaker variants of the DLIN assumption. Existing function private constructions in the public-key setting 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 $\lambda$, where $\lambda$ is the security parameter. Our constructions allow relaxing this min-entropy requirement to $\omega(\log\lambda)$, while achieving a computational notion of function privacy against probabilistic polynomial-time adversaries, which suffices for most real-world applications. Our constructions also avoid the need for strong assumptions such as indistinguishability obfuscation.

**Category / Keywords: **Predicate Encryption, Public-Key, Function Privacy, Computational Indistinguishability, Min-Entropy, Identity-Based Encryption, Inner-Product Encryption

**Date: **received 11 Apr 2017, last revised 18 Sep 2017

**Contact author: **sikhar patranabis at iitkgp ac in

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

**Note: **The paper is augmented with a revised related work section

**Version: **20170918:062155 (All versions of this report)

**Short URL: **ia.cr/2017/319

[ Cryptology ePrint archive ]