Weng et al. introduced the notion of conditional proxy re-encryption (or C-PRE, for short), whereby only the ciphertext satisfying one condition set by the delegator can be transformed by the proxy and then decrypted by delegatee. Nonetheless, they left an open problem on how to construct CCA-secure C-PRE schemes with anonymity. Fang et al. answered this question by presenting a construction of anonymous condi- tional proxy re-encryption (C-PRE) scheme without requiring random oracle. Nev- ertheless, Fang et al.'s scheme only satises the RCCA-security (which is a weaker variant of CCA-security assuming a harmless mauling of the challenge ciphertext is tolerated). Hence, it remains an open problem whether CCA-secure C-PRE schemes that satisfy both anonymity and full CCA-security can really be realized. Shao et al. introduced a new cryptographic primitive, called proxy re-encryption with keyword search (PRES), which is a combination of PRE and public key encryption with key- word search (PEKS), and they left an open problem on how to design an efficient unidirectional PRES scheme. In this paper, we answer the above open problems by proposing a new crypto- graphic primitive called conditional proxy re-encryption with keyword search (C- PRES), which combines C-PRE and PEKS. We note that there are subtleties in combining these two notions to achieve a secure scheme, and hence, the combination is not trivial. We propose a denition of security against chosen ciphertext attacks for C-PRES schemes with keyword anonymity, and thereafter present a scheme that satises the denition. The performance of our scheme outperforms Weng et al.'s construction, which has been regarded as the most efficient C-PRE scheme to date.