The extensive use of the Internet has been accompanied by the augmentation ofe-services, such as e-health. Particularly, the improvement in e-health has put amassive load of sensitive information in the hands of service providers and otherparties, where privacy risks might exist when accessing sensitive data stored inthe form of electronic patient records (EPRs). EPRs support efficient access topatient data by multiple healthcare providers and third party users, which willconsequently improve patient care. However, the sensitive nature of this datarequires access restrictions to only those 'who need to know'. How to achieve thiswithout compromising patient privacy remains an open issue that needs furtherconsideration. This thesis, therefore, addresses privacy problems with distributedEPRs and how to allow authorised users to access them with multiple levels ofidentity privacy preservations.The thesis investigates existing security solutions for achieving privacy preservingdistributed data access and analyses their strengths and weaknesses. Itthen proposes a novel method to support secure access to distributed EPRs withthree levels of patient identity privacy preservations, i.e., the 3LI2P version 1(3LI2Pv1) method. The idea of the method is to integrate a number of significantfeatures, which have not been considered in the related work, and thesefeatures are: (1) supporting three levels of controlled distributed EPR accessesby different legitimate user groups while preserving patient identity privacy; (2)making use of different digital credentials to support the three levels of access;(3) simplifying key management distribution; (4) optimising performance; and(5) supporting separation of duties among trusted third parties, ensuring accountability.The 3LI2Pv1 method makes use of three layers of pseudonyms to achieve these properties, i.e., each patient has multiple pseudonyms layered atthree levels. The method relies on a combined cryptographic primitives, symmetriccryptosystem, asymmetric cryptosystem and a hash function, to generatethese pseudonyms. The security properties and the performance of the 3LI2Pv1method are analysed, evaluated and compared with related work. The resultsfrom the comparison show that our 3LI2Pv1 method is better in terms of supportingthe requirements necessary to preserve a patient's identity privacy in adistributed setting at no significant additional costs. The thesis also proposes an enhanced version of the above method called the3LI2P version 2 (3LI2Pv2) method. This latter method enhances the 3LI2Pv1method in terms of reducing key management burden on central trusted thirdparty, enforcing the least access privilege principle, not only among users and central trusted third party, but also among health service providers who manage the patients' data, further improving performance, ensuring the integrity ofpatient pseudonyms, providing pseudonyms uniqueness and finally, facilitating amore ne-grained access control by introducing an additional linkable anonymousaccess sub-level. The 3LI2Pv2 method has been analysed in terms of securityand performance. Based on the 3LI2Pv2 method, the thesis introduces a novel3LI2Pv2 protocol. The protocol is designed specifically for the 3LI2Pv2 methodto facilitate different types of accesses, linkable access, Level-2 inter-HSP linkableanonymous access, Level-2 intra-HSP linkable anonymous access and anonymousaccess, and to allow different user groups to securely access distributed EPRs according to their privileges, without compromising the patient's privacy.The security properties of the 3LI2Pv2 protocol are formally verified using theCasper/FDR2 verification tool. To evaluate its performance, a prototype of the3LI2Pv2 protocol has been implemented using Java under two different settings,a single machine and distributed machines settings. Using these implementationsettings, performance evaluations of the protocol were conducted. The resultsfrom the evaluations (under both settings) confirmed that we have successfullybalanced between security and performance without compromising the patient'sprivacy.