People/Web Search Calendar Emergency Info A-Z Index UVA Email University of Virginia

Computer Science Colloquia

Monday, July 27, 2015
Ben Terner
Advisor: abhi shelat
Attending Faculty: Mohammad Mahmoody (Chair) and David Evans

1:30 PM, Rice Hall, Rm. 204

Master's Thesis Presentation
Stable Matching with PCF Version 2, an Etude in Secure Computation

ABSTRACT

The classic stable-matching algorithm of Gale and Shapley and subsequent variants by, e.g., Roth and Abdulkadiroglu et al., have been used successfully in a number of real-world scenarios, including the assignment of US medical school graduates to residency programs and students in New York, Norway, and Singapore to high schools and universities. One shortcoming of the Gale-Shapley family of matching algorithms is susceptibility to strategic manipulation by the participants. The commonly used paradigm to mitigate this shortcoming, employing a trusted third party to compute matchings explicitly, is outdated, expensive, and in some scenarios, impossible. This makes stable matching a natural problem for secure, multiparty computation (SMPC).

We use Portable Circuit Format (PCF), a compiler and interpreter for Yao's garbled circuit protocols, to produce the first feasible, privacy-preserving application for stable matching. In doing so, we improve the theoretical bounds for stable matching constructions, develop global optimizations for PCF circuits, and improve garbling techniques used by PCF.  We also analyze variants of stable matching that are used in real-world scenarios. Experiments show that after aggressive circuit optimization, our protocols achieve good performance for matchings with hundreds of participants.