Paper 2016/861

Secure Stable Matching at Scale

Jack Doerner, David Evans, and abhi shelat


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 23rd ACM Conference on Computer and Communications Security (CCS)
Stable MatchingGale-ShapleyRoth-PeransonSecure ComputationRAM Secure ComputationMulti-party Computation
Contact author(s)
jhd3pa @ virginia edu
2018-06-19: revised
2016-09-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jack Doerner and David Evans and abhi shelat},
      title = {Secure Stable Matching at Scale},
      howpublished = {Cryptology ePrint Archive, Paper 2016/861},
      year = {2016},
      doi = {10.1145/2976749.2978373},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.