Implementation and Evaluation of Privacy-Preserving Protocols

Full textClick to download.
CitationPhD Thesis, Yale University Computer Science Department, 2010.
AuthorFelipe Saint-Jean


Computers and networks have become essential tools for many daily activities, including commerce, education, social interaction, and political engagement. Massive amounts of sensitive data are transmitted over networks and stored in web-accessible databases, and thus privacy of these data has become a top priority. Decades of research in cryptography and security have resulted in an elegant theory that shows, in principle, how to perform almost any computational task in a privacy-preserving manner, but there is a wide gap between theory and practice: Currently, most people and organizations have no straightforward way to safeguard the privacy of their sensitive data in realistic networked environments. In the interest of bridging this gap, we design and implement protocols to enhance privacy in four scenarios: web search, security-alert sharing, database querying, and survey computation. We evaluate our protocols and implementations with respect to various natural criteria, including effectiveness, efficiency, and usability. Our principle contributions include:

-We introduce PWS, a Firefox plug-in that enhances privacy in web search by minimizing the information that is sent from the user's machine to the search engine. PWS protects users against attacks that involve active components and timing information, to which more general web- browsing privacy tools are vulnerable. In a study of ease of installation and use, PWS compares favorably with the widely used TPTV bundle.

- We design, implement, and analyze a threshold-union protocol that allows networks to share security-alert data in a consensus-private manner, i.e., one in which an anomaly discovered at one network is only revealed if it is discovered at t-1 other networks, where t is the threshold. Our protocol achieves entropic security, accommodates transient contributors, and is significantly more scalable than the earlier protocol of Kissner and Song.

- We implement a computationally secure protocol for symmetric, private information retrieval that uses oblivious transfer in an essential way. Our implementation is fast enough for medium- sized databases but not for large databases.

- Motivated by the CRA Taulbee survey of faculty salaries, we use the FairPlay platform of Malkhi et al. to build a highly usable system for privacy-preserving survey computation.

Back to publications
Back to previous page