Predicate encryption (PE) that provides both the access control of ciphertexts and the privacy of ciphertexts is a new paradigm of public-key encryption. An important application of predicate encryption is a searchable encryption system in a cloud storage, where it enables a client to securely outsource its data to an untrusted cloud server and to search over it even without revealing a keyword itself. One practical issue of predicate encryption is to devise an efficient revocation method to revoke a user when the secret key of the user is compromised. Privacy preserving revocable predicate encryption (RPE) can provide not only revocation, but also the privacy of revoked users.
In this paper, we first define two new security models of privacy preserving RPE: the strongly full-hiding security and the weakly full-hiding security. The strongly full-hiding security provides the full privacy of ciphertexts against outside and inside adversaries, but the weakly full-hiding security only provides the full privacy of ciphertexts against an outside adversary who cannot decrypt the challenge ciphertext. Next, we propose two general RPE constructions from any inner product encryption (IPE) schemes, and prove their security. This first RPE scheme provides the strongly full-hiding security, but the size of ciphertexts is proportional to the number of users in the system. The second RPE scheme improves the efficiency of the first RPE scheme such that the size of ciphertexts is sublinear and the decryption algorithm is efficient, but it provides the weakly full-hiding security.