PEKSrand: Providing Predicate Privacy in Public-Key Encryption With Keyword Search

Recently, Shen, Shi, and Waters introduced the notion of predicate privacy, i.e., the property that t(x) reveals no information about the encoded predicate p, and proposed a scheme that achieves predicate privacy in the symmetric-key settings. In this paper, the authors propose two schemes. In the first scheme, they extend PEKS to support predicate privacy based on the idea of randomization. To the best of the knowledge, this is the first work that ensures predicate privacy in the public key settings without requiring interactions between the receiver and potential senders, the size of which may be very large.