Paper 2008/536

Predicate Privacy in Encryption Systems

Emily Shen, Elaine Shi, and Brent Waters

Abstract

Predicate encryption is a new encryption paradigm which gives the secret key owner fine-grained control over access to encrypted data. The secret key owner can generate tokens corresponding to predicates. An encryption of a plaintext x can be decrypted using a token corresponding to a predicate f if the plaintext satisfies the predicate, i.e., f(x) = 1. Prior work on public-key predicate encryption has focused on the notion of plaintext privacy, the property that ciphertexts reveal no information about the encrypted plaintext. In this paper, we consider a new notion called predicate privacy, the property that tokens reveal no information about the encoded query predicate. Predicate privacy is inherently impossible to achieve in the public-key setting and has therefore received little attention in prior work. In this work, we consider predicate encryption in the symmetric-key setting and present a symmetric-key predicate encryption scheme which supports inner product queries. We prove that our scheme achieves both plaintext privacy and predicate privacy.

Note: Elaine Shi (eshi@parc.com) Emily Shen (eshen@csail.mit.edu)