Stable Matching with PCF Version 2, and Etude in Secure Computation

The classic stable-matching algorithm of Gale and Shapley and subsequent variants by, e.g., 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). Secure multiparty computation allows two or more mutually distrustful parties to evaluate a joint function on their inputs without revealing more information about the inputs than each player can derive from his own input and output.
We use Portable Circuit Format (PCF), a compiler and interpreter for Yao’s garbled circuit protocols, to produce the first feasible, privacy-preserving protocol 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 scale with good performance for matchings with hundreds of participants.