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.
Privacy-preserving Messaging and Search: A Collaborative Approach
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).