In this dissertation, we construct two systems that protect privacy by splitting trust among multiple parties, so that the failure of any one, whether benign or malicious, does not cause a catastrophic privacy failure for the system as a whole. The first system, called Prio, allows a company to collect aggregate statistical data about its users without learning any individual user's personal information. The second, called Riposte, is a system for metadata-hiding communication that allows its users to communicate over an insecure network without revealing who is sending messages to whom. Both systems defend against malicious behavior using zero-knowledge proofs on distributed data, a cryptographic tool that we develop from a new type of probabilistically checkable proof.
The two systems that we construct maintain their security properties in the face of an attacker who can control the entire network, an unlimited number of participating users, and any proper subset of the servers that comprise the system. These systems split trust in the sense that, as long as an attacker cannot compromise all of the participating servers, the system provides "best-possible" protection of the confidentiality of user data. Through the design, implementation, and deployment of these systems, we show that it is possible for us to enjoy the benefits of modern computing while protecting the privacy of our data.