You are looking at a specific version 20180619:160601 of this paper. See the latest version.

Paper 2016/861

Secure Stable Matching at Scale

Jack Doerner and David Evans and abhi shelat

Abstract

When a group of individuals and organizations wish to compute a stable matching---for example, when medical students are matched to medical residency programs---they often outsource the computation to a trusted arbiter in order to preserve the privacy of participants' preferences. Secure multi-party computation offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms have previously been considered infeasible for execution in a secure multi-party context on non-trivial inputs because they are computationally intensive and involve complex data-dependent memory access patterns. We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main improvements stem from designing new oblivious data structures that exploit the properties of the matching algorithms. We apply a similar strategy to scale the Roth-Peranson instability chaining algorithm, currently in use by the National Resident Matching Program. The resulting protocol is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 18 hours to complete an execution simulating the 2016 national resident match with more than 35,000 participants and 30,000 residency slots.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. 23rd ACM Conference on Computer and Communications Security (CCS)
DOI
10.1145/2976749.2978373
Keywords
Stable MatchingGale-ShapleyRoth-PeransonSecure ComputationRAM Secure ComputationMulti-party Computation
Contact author(s)
jhd3pa @ virginia edu
History
2018-06-19: revised
2016-09-10: received
See all versions
Short URL
https://ia.cr/2016/861
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.