Privacy and Integrity in the Untrusted Cloud

Cloud computing has become increasingly popular because it offers users the illusion of having infinite computing resources, of which they can use as much as they need without having to worry about how those resources are provided. It also provides greater scalability, availability, and reliability than users could achieve with their own resources. Unfortunately, adopting cloud computing has required users to cede control of their data to cloud providers, and a malicious provider could compromise the datas confidentiality and integrity. Furthermore, the history of leaks, breaches, and misuse of customer information at providers has highlighted the failure of government regulation and market incentives to fully mitigate this threat. Thus, users have had to choose between trusting providers or forgoing cloud computings benefits entirely. This dissertation aims to overcome this trade-off. We present two systems, SPORC and Frientegrity, that enable users to benefit from cloud deployment without having to trust the cloud provider. Their security is rooted not in the providers good behavior but in the users cryptographic keys. In both systems, the provider only observes encrypted data and cannot deviate from correct execution without detection. Moreover for cases when the provider does misbehave, SPORC introduces a mechanism also applicable to Frientegrity, that enables users to recover. It allows users to switch to a new provider and repair any inconsistencies that the providers misbehavior may have caused. SPORC is a framework for building a wide variety of user-facing applications from collaborative word processing and calendaring to email and instant messaging with an untrusted provider. It allows concurrent, low-latency editing of shared state, permits disconnected operation, and supports dynamic access control even in the presence of concurrency. Frientegrity extends SPORCs model to online social networking.