AbstractPredicate 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 PE is a searchable encryption system in cloud storage, where it enables a client to securely outsource the search of a keyword on encrypted data without revealing the keyword to the cloud server. One practical issue of PE is to devise an efficient revocation method to revoke a user when the secret key of the user is compromised. Privacy preserving revocable PE (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 (FH) security and the weakly FH security. Next, we propose a general RPE construction from any PE scheme and prove its security in the weakly FH security model. Our generic RPE scheme is efficient because the number of ciphertext elements is not proportional to the number of users in a receiver set. Additionally, our RPE scheme can support polynomial‐size circuits if a recently proposed functional encryption scheme for polynomial‐size circuits is used as an underlying PE scheme. Copyright © 2014 John Wiley & Sons, Ltd.