While the use of Personal Health Records (PHRs) in a cloud computing environment brings benefits, it also raises concerns. One of the major concerns is how to prevent patients' data managed by a cloud provider (i.e., a third-party) from being revealed to unauthorised entities, including the cloud provider. One way to address this concern is to protect data by using an Attribute Based Encryption (ABE) based solution, in which data is encrypted before it is uploaded to the cloud provider. As part of the solution, data is first encrypted by using a symmetric key, which is then protected by using a pair of keys: a public and a private key. The public key is used for encrypting the symmetric key, and the private key is used for decrypting the symmetric key. To access data, a user needs to acquire the private key. Existing work on controlling the access of PHRs in a cloud environment largely focuses on how to make the solutions more fine-grained or how to strike the balance between data access granularity and efficiency. However, there is little work on ensuring how to securely distribute a private key in an ABE based PHRs access control system. This thesis addresses the issue by proposing a multi-level approach to private key distribution in a Ciphertext-Policy ABE (CP-ABE) based access control solution. This multi-level approach is inspired by our observation that patients' data may not have the same level of sensitivity, and to optimise the trade-off between privacy protection and costs (i.e., computational and communication), the level of access control should be tailored based on the data sensitivity levels. We have implemented these ideas by designing and evaluating a novel 3-Level Access Control Framework (3LAC) that combines the Shamir's Secret Sharing scheme with a CP-ABE based access control model, in which to access more sensitive data a user needs to acquire more shares, and for the acquisition of each share, there is an authentication process. In addition, we have proposed a Separation-of-Duty (SoD) approach, in which users' attributes are classified into two groups based on their importance. The important attributes (high-weight), and the less important attributes (low-weight). Depending on whether a user's revoked attribute is high-weight or low-weight, then only the private key containing the high-weight or low-weight attributes needs to be regenerated. In this way, we can further reduce the overhead costs. A prototype has been built to evaluate the performance of the 3LAC Framework and the SoD approach. The results of the evaluation demonstrate that the 3LAC Framework balances the performance according to the data sensitivity levels as compared with a fixed-level approach, and that the SoD approach improves the attributes revocation process.