Paper 2017/319

Encrypt-Augment-Recover: Computationally Function Private Predicate Encryption in the Public-Key Setting

Sikhar Patranabis and Debdeep Mukhopadhyay

Abstract

We solve the open problem of constructing \emph{computationally function private} public-key predicate encryption schemes. Existing public-key constructions for predicate encryption satisfy a \emph{statistical} notion of function privacy, that was introduced for equality predicates by Boneh, Raghunathan and Segev in CRYPTO'13, and was generalized for subspace-membership predicates in ASIACRYPT'13. The secret-keys in these constructions are \emph{statistically indistinguishable} from random as long the underlying predicates are sampled from sufficiently unpredictable distributions. The alternative notion of computational function privacy, where the secret-keys are \emph{computationally indistinguishable} from random, has only been concretely realized in the private-key setting, to the best of our knowledge. \hspace*{5mm}In this paper, we present the first computationally function private constructions for public-key predicate encryption. Our framework for computational function privacy requires that a secret-key corresponding to a predicate sampled from a distribution with min-entropy super logarithmic in the security parameter $\lambda$, is \emph{computationally indistinguishable} from another secret-key corresponding to a uniformly and independently sampled predicate. Within this framework, we develop a novel approach, denoted as \emph{encrypt-augment-recover}, that takes an existing predicate encryption scheme and transforms it into a computationally function private one while retaining its original data privacy guarantees. Our approach leads to public-key constructions for identity-based encryption and inner-product encryption that are fully data private and computationally function private under a family of weaker variants of the DLIN assumption. Our constructions, in fact, satisfy an \emph{enhanced} notion of function privacy, requiring that an adversary learns nothing more than the minimum necessary from a secret-key, even given corresponding ciphertexts with attributes that allow successful decryption.

Note: The paper is being revised with the author details which were mistakenly omitted in the previous version.