Toward Practical Secure Stable Matching
Authors: M. Sadegh Riazi (University of California, San Diego), Ebrahim M. Songhori (Rice University), Ahmad-Reza Sadeghi (TU Darmstadt), Thomas Schneider (TU Darmstadt), Farinaz Koushanfar (University of California, San Diego)
Volume: 2017
Issue: 1
Pages: 62–78
DOI: https://doi.org/10.1515/popets-2017-0005
Abstract: The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on Yao’s garbled circuit protocol and Oblivious RAM (ORAM). Our scheme can securely compute a stable match for 8k pairs four orders of magnitude faster than the previously best known method. We achieve this by introducing a compact and efficient sub-linear size circuit. We even further decrease the computation cost by three orders of magnitude by proposing a novel technique to avoid unnecessary iterations in the SM algorithm. We evaluate our implementation for several problem sizes and plan to publish it as open-source.
Keywords: privacy-preserving, stable matching, garbled circuit, secure function evaluation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
