The average costs of data leakage are steadily on the rise. Especially in healthcare, the disclosure of sensitive information may have unfavorable consequences for the patient. As a consequence, several data security and access control mechanisms have been introduced, ranging from data encryption to intrusion detection or role-based access control, doing a great work in protecting sensitive information. However, the majority of these concepts are centrally controlled by administrators who are a major threat to the patients’ privacy. Apart from administrators, other internal persons, such as hospital staff members, may exploit their access rights to snoop around in private health data. This work presents PERiMETER, a security protocol for data privacy that is strictly controlled by the data owner. It integrates pseudonymization and encryption to create a methodology that uses pseudonyms as access control mechanism, protects secret cryptographic keys by a layer-based security model, and provides privacy-preserving querying.