The issue of empowering patients to be well informed with regards to their health records has been well accepted in the community, which is known as the Personal Health Record (PHR). PHR has been believed as the solution for better management of an individual’s health, and as the tool that will empower the patient in correlation with healthcare providers through the ability to provide his/her own medical history. In this work, we aim to take one step further by equipping patients with the ability to “control” the access to their PHR efficiently and easily, by incorporating the emerging cloud technology. Specifically, we aim to provide the patients with the luxury of using the power of the cloud to conduct the outsourced work efficiently. To realize this, we present the notion of online/offline ciphertext-policy attribute-based proxy re-encryption scheme, which is very useful primitive in empowering personal health records in cloud computing. We present such a notion as well as a set of security requirements. More specifically, we define two security models covering both outsider and insider attacks. Furthermore, we present a concrete construction of such a scheme, and prove that it is secure under the well known complexity assumptions and following our security models.