In an e-Health scenario, we study how the practitioners are authorized when they are requesting access to medical documents containing sensitive information. Consider the following scenario. A clinician wants to access and retrieve a patient’s Electronic Health Record (EHR), and this means that the clinician must acquire sufficient access right to access this document. As the EHR is within a collection of many other patients, the clinician would need to specify some requirements (such as a keyword) which match the patient’s record, as well as having a valid access right. The complication begins when we do not want the server to learn anything from this query (as the server might be outsourced to other place). To encompass this situation, we define a new cryptographic primitive called Certificate-Based Encryption with Keyword Search (CBEKS), which will be suitable in this scenario. We also specify the corresponding security models, namely computational consistency, indistinguishability against chosen keyword and ciphertext attacks, indistinguishability against keyword-guessing attacks and collusion resistance. We provide a CBEKS construction that is proven secure in the standard model with respect to the aforementioned security models.