Patient Health Records (PHRs) shift the ownership of health data from health providers to patients. Such a shift poses important challenges from the data privacy point of view. Patients would like to be able to selectively reveal information to other stakeholders and, at the same time, be assured that their health information will not be used improperly once shared. Current PHR systems partially fail to satisfy these requirements. In this paper, we show that both requirements can be satisfied fully when adopting a novel cloud-based PHR system architecture.We expain the role of remote virtual machines in this architecture and use interaction models to reason about privacy implications. Finally, we evaluate MyPHRMachines, a prototypical imple...