Privacy-Preserving Messaging and Search: A Collaborative Approach*
Wed, Dec. 2
In a free society, people have the right to interact with public data without fear of retribution. However, today’s technological landscape enables large-scale monitoring by powerful entities (e.g., totalitarian governments); at worst, these entities may punish people for consuming or distributing objectionable content. This thesis considers two technical problems related to freedom of information: (1) anonymous message spreading and (2) privacy-preserving database searches. In the area of anonymous messaging, we present adaptive diffusion: a scalable, distributed messaging protocol with strong theoretical anonymity guarantees against global adversaries. In the area of private search, we present new algorithms for searching public databases without revealing one's query to the server, while meeting strict efficiency constraints. For both problems, we focus on distributed algorithms that harness cooperation and resource-sharing among privacy-conscious individuals. We analyze the performance of these algorithms theoretically and through simulation to show improvement over prior art.