Cloud infrastructures, despite all their advantages and importance to the competitiveness of modern economies, raise fundamental questions related to the privacy, integrity, and security of offsite data storage and processing tasks. These questions are currently not answered satisfactorily by existing technologies. Furthermore, recent developments in the wake of the expansive and sometimes unauthorized government access to private and sensitive data raise major privacy and security concerns about data located in the cloud, especially when data is physically located, processed, or must transit outside the legal jurisdiction of its rightful owner. This is exacerbated by providers of cloud services that frequently move and process data without notice in ways that are detrimental to the users and their privacy. SafeCloud will re-architect cloud infrastructures to ensure that data transmission, storage, and processing can be (1) partitioned in multiple administrative domains that are unlikely to collude, so that sensitive data can be protected by design; (2) entangled with inter-dependencies that make it impossible for any of the domains to tamper with its integrity. These two principles (partitioning and entanglement) are thus applied holistically across the entire data management stack, from communication to storage and processing. Users will control the choice of non-colluding domains for partitioning and the tradeoffs between entanglement and performance, and thus will have full control over what happens to their data. This will make users less reluctant to manage their personal data online due to privacy concerns and will generate positive business cases for privacy-sensitive online applications such as the distributed cloud infrastructure and medical record storage platform that we address.