Private, Distributed, and Scalable Content Providers

In this thesis I will show that, by leveraging efficient data structures and algorithms for indexing and secure computation, we can create practical systems for anonymous and private search, communication, and content distribution. I will improve and extend existing work in private search, which only addresses the problem where a client stores his own data encrypted on a server and wishes to be able to search his records remotely without revealing the their content. I do so by addressing a broader scenario, in which one or more servers store their own data, and a number of users wish to be able to issue queries across these records, without the server learning about the types of queries users are running, and without users learning anything about the remote databases besides the results of their searches. I also improve upon the field of anonymous communication systems, where prior systems focused on addressed communication in a unicast setting. I will discuss how we can create anonymous communication systems that work on a publish-subscribe basis, allowing communication to reach many people while solving the issue of how to establish communication without prior relationships. Next, I will discuss anonymous credential systems, and how to make them feasible for real-world scenarios. These systems can be useful for anonymously enforcing policies and managing privileges on a per-user basis. Our final challenge is to provide a scalable anonymous communication system that can deliver our queries while maintaining our privacy requirements. I will do this using a publish-subscribe architecture. I will show how all of these advancements can be accomlished by leveraging Bloom Filters, Onion Routing, Re-routable Encryption, and Yao Garbled Circuits to create anonymity preserving systems that operate in real time.