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

Recently, Shen, Shi, and Waters introduced the notion of predicate privacy, and proposed a scheme that achieves predicate privacy in the symmetric-key settings. In this paper, we propose two schemes. In the first scheme, we extend PEKS to support predicate privacy based on the idea of randomization. To the best of our 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. Moreover, we identify a new type of attacks against PEKS, i.e., statistical guessing attacks. Accordingly, we introduce a new notion called statistics privacy, i.e., the property that predicate privacy is preserved even when the statistical distribution of keywords is known. The second scheme we proposed makes a tradeoff between statistics privacy and storage efficiency (of the delegate). Compared to PEKS, both schemes introduce reasonable communication and computation overheads and can be smoothly deployed in existing systems.